C.Ю.Соловьев
ВМК МГУ имени М.В.Ломоносова; 1 курс, 2-й поток
 
Алгоритмы и алгоритмические языки

Консультация (Соловьев) Время: 14 января 2023, 14:00, аудитория П5

Порядок проведения экзамена:
Часть 1. Письменное задание: 1 час, 2 или 4 задачи
Часть 2. Устный опрос
Экзаменационные вопросы по теоретической части курса А+АЯ
  1. Понятия задачи и алгоритма
  2. Свойства алгоритмов
  3. Словесная запись алгоритма
  4. Блок-схемы для записи алгоритмов
  5. Понятия: алфавит, слово, длина слова
  6. Область применимости алгоритма
  7. Компоненты машины Тьюринга
  8. Свойство детерминированности программы для машины Тьюринга
  9. Соглашения об использовании машин Тьюринга
  10. Композиции алгоритмов
  11. Тезис Тьюринга
  12. Универсальная машина Тьюринга
  13. Нормальные алгоритмы Маркова
  14. Применимость правила к слову
  15. Выполнение нормального алгоритма Маркова
  16. Достаточные условия применимости нормального алгоритма Маркова
  17. Самоприменимые и несамоприменимые алгоритмы
  18. Алгоритмически неразрешимые задачи
  19. Оперативная память и процессор компьютера
  20. Форматы хранения чисел в оперативной памяти
  21. Компьютерные операции с нормализованными числами
  22. Система команд компьютера
  23. Регистры процессора
  24. Порядок исполнения машинных команд
  25. Программирование в кодах, мнемокод, ассемблер
  26. Алгоритмические языки высокого уровня
  27. Алфавит, синтаксис, семантика и прагматика АЯ высокого уровня
  28. Формулы Бэкуса-Наура
  29. Синтаксические диаграммы
  30. Синтаксис целых и вещественных чисел
  31. Синтаксис идентификаторов
  32. Структура ПАСКАЛЬ-программ
  33. Синтаксис и семантика оператора присваивания
  34. Понятие "Переменная"
  35. Типы данных в языке ПАСКАЛЬ
  36. Целый тип данных
  37. Вещественный тип данных
  38. Преобразования real -> integer и integer -> real
  39. Арифметические выражения
  40. Булевский тип данных
  41. Булевские выражения
  42. Операции над булевскими выражениями
  43. Приоритеты операций в булевских выражениях
  44. Символьный тип данных
  45. Свойства множества значений символьного типа
  46. Преобразования char -> integer и integer -> char
  47. ПАСКАЛЬ-программа как строка
  48. Комментарии в ПАСКАЛЬ-программе
  49. Раздел меток ПАСКАЛЬ-программы
  50. Раздел переменных ПАСКАЛЬ-программы
  51. Оператор ввода
  52. Оператор вывода
  53. Составной оператор
  54. Пустой оператор
  55. Раздел типов ПАСКАЛЬ-программы
  56. Условный оператор
  57. Оператор перехода
  58. Оператор цикла с предусловием
  59. Оператор цикла с постусловием
  60. Операторы цикла с параметром
  61. Структурное программирование
  62. Раздел констант ПАСКАЛЬ-программы
  63. Раздел типов ПАСКАЛЬ-программы
  64. Перечислимые типы данных
  65. Оператор варианта
  66. Ограниченные типы данных
  67. Задание регулярного типа данных
  68. Значения регулярного типа данных
  69. Переменные с индексами
  70. Строки (стандарт ISO)
  71. Заголовок ПАСКАЛЬ-программы
  72. Раздел процедур и функций ПАСКАЛЬ-программы
  73. Описание процедуры
  74. Оператор процедуры
  75. Параметры-значения и параметры-переменные
  76. Принцип локализации
  77. Функции в языке ПАСКАЛЬ
  78. Описание функции
  79. Вызовы функций
  80. Локальные и глобальные переменные
  81. Побочные эффекты
  82. Рекурсивные процедуры и функции
  83. Предописания процедур и функций
  84. Определение секции формальных параметров
  85. Параметры-процедуры и параметры-функции
  86. Комбинированные типы данных
  87. Задание комбинированного типа данных
  88. Селекторы полей переменных комбинированного типа
  89. Операции с записями
  90. Оператор присоединения
  91. Правило разрешения конфликтов имен в операторе присоединения
  92. Множественные типы данных
  93. Операции множественного типа
  94. Отношения множественного типа
  95. Файловые типы данных
  96. Задание файлового типа данных
  97. Файловые операции
  98. Буферные переменные файлов
  99. Операции put и get
  100. Текстовые файлы
  101. Тип данных text в языке ПАСКАЛЬ
  102. Ссылочные типы данных
  103. Переменная с указателем
  104. Операции new и dispose
  105. Переменные в языке Паскаль
  106. Нисходящее программирование
  107. Отладка программ
  108. Тестирование программ
  109. Полнота набора тестов
  110. Понятие сложности алгоритма
  111. Структуры данных
  112. Однонаправленные списки
  113. Циклические списки
  114. Двунаправленные списки
  115. Очереди
  116. Стеки
  117. Таблицы
  118. Таблицы с неупорядоченными элементами
  119. Операции для таблиц с неупорядоченными элементами
  120. Таблицы с упорядоченными элементами
  121. Операции для таблиц с упорядоченными элементами
  122. Оценки сложности операций для таблиц с упорядоченными и неупорядоченными элементами
  123. Хеш-таблицы
  124. Хеш-функции
  125. Открытое хеширование
  126. Операции с элементами при открытом хешировании
  127. Закрытое хеширование
  128. Операции с элементами при закрытом хешировании
  129. Бинарные деревья с корнем
  130. Терминология бинарных деревьев
  131. Деревья поиска
  132. Операции поиска и вставки вершин в деревьях поиска
  133. Операция удаления вершины в дереве поиска
  134. Высота дерева
  135. Оценки сложности операций для деревьев поиска
  136. Идеально сбалансированные деревья
  137. Оценки сложности операций для идеально сбалансированных деревьев
  138. AVL-деревья
  139. Высота AVL-дерева
  140. Правила корректировки AVL-деревьев
  141. Операция включения вершины в AVL-дерево
Коллоквиум: 107 группа: 8 \ 9 \ 2
108 группа: 4 \ 5 \ 7 \ 4
109 группа: 7 \ 3 \ 6 \ 1
110 группа: 8 \ 2 \ 7 \ 1
111 группа: 5 \ 3 \ 7 \ 3
112 группа: 3 \ 7 \ 2 \ 4

  Презентации:
Лекция No.01   Лекция No.02   Лекция No.03   Лекция No.04   Лекция No.05  
Лекция No.06 Лекция No.07 Лекция No.08 Лекция No.09 Лекция No.10
Лекция No.11 Лекция No.12 Лекция No.13 Лекция No.14 Лекция No.15
Методические материалы:
1. Программа курса
2. Программирование в машинных кодах
3. Примеры-1
4. Примеры-2
5. Пример "большой" программы
6. Нисходящее программирование
7. Ссылочные типы
  8. Структуры данных
 9. Очереди и стеки
10. Деревья поиска
11. AVL-деревья
12. Таблицы
13. Хеш-таблицы
14. Динамические страницы
•  Учебно-методический комплекс "Алгоритмы и алгоритмические языки"
•  Методические материалы М.О.Проскурни

Программа курса


Тема 1. АЛГОРИТМЫ
1. Вводная часть
2. Интуитивное определение алгоритмов (понятие алгоритма, примеры алгоритмов, свойства алгоритмов)
3. Неформальные способы записи алгоритмов (словесная запись, блок-схемы)
4. Необходимость и способы уточнения понятия алгоритма (символы и слова )

Тема 2. МАШИНА ТЬЮРИНГА
1. Машина Тьюринга (структура, такт работы, запись программы, правила выполнения программы, применимость и неприменимость алгоритма к слову, соглашения для сокращения записи программы)
2. Возможности МТ (композиция, разветвление и повторение МТ)
3. Тезис Тьюринга

Тема 3. НОРМАЛЬНЫЕ АЛГОРИТМЫ МАРКОВА
1. Нормальные алгоритмы Маркова (операция подстановки и формулы подстановки, запись НАМ, два вида стрелок, правила выполнения, тезис Маркова)
2. Алгоритмически неразрешимые проблемы (определение алгоритмически разрешимых и неразрешимых задач, понятия записи алгоритма и самоприменимости, теорема об алгоритмической неразрешимости проблемы самоприменимости)

Тема 4. МОДЕЛЬНАЯ ЭВМ
1. Структура ЭВМ (схема, устройства ввода и вывода, внутренняя и внешняя память, центральный процессор)
2. Оперативная память: ячейки, адреса ячеек, размер ячеек.
3. Машинное представление данных: представление целых и вещественных чисел, о точности представления целых и вещественных чисел, представление символьной информации.
4. Машинная программа. Смысл и формат трехадресных команд. Система команд.
5. Пример машинной программы.

Тема 5. АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ. МЕТАЯЗЫКИ
1. Об алгоритмических языках (достоинства и недостатки машинного языка, алгоритмические языки высокого уровня и их достоинства, разнообразие АЯ, трансляция с АЯ)
2. Металингвистические формулы (БНФ) (основные понятия БНФ, рекурсивные формулы, расширение БНФ)
3. Синтаксические диаграммы (правила перевода БНФ --> синтаксические диаграммы)
4. Запись целых и вещественных чисел в Паскале

Тема 6. ЯЗЫК ПАСКАЛЬ. ЧИСЛОВЫЕ ТИПЫ
1. Алфавит, идентификаторы (синтаксис и назначение идентификаторов, служебные слова, стандартные имена и просто имена)
2. Типы данных. Переменные (перечень всех типов данных Паскаля, стандартные типы; переменные и типы данных, контроль за использованием переменных; синтаксис раздела переменных)
3. Числовые типы данных
   3.1 Целый тип (запись целых чисел, описание переменных целого типа, операции над целыми числами, стандартные функции для целых чисел, maxint)
   3.2 Вещественный тип (запись вещественных чисел, описание вещественных переменных, операции и стандартные функции для вещественных чисел)
   3.3 Арифметические выражения (тип выражения, тип результата, правила записи арифметических выражений, правила вычисления выражений и определения их типа)
4. Оператор присваивания (синтаксис, семантика и прагматика оператора присваивания)

Тема 7. ЛОГИЧЕСКИЙ И СИМВОЛЬНЫЙ ТИПЫ
1. Логический (булевский) тип (высказывания в логике, запись условий в виде высказываний, простые логические выражения: константы, переменные и их описание, отношения, стандартные функции odd, succ и pred); логические операции (not, and, or) и их свойства; логические выражения (синтаксис "на пальцах") и правила их вычисления; оператор присваивания)
2. Символьный тип (запись символов, набор символов и их упорядоченности, описание переменных, операции, стандартные функции (ord, chr, succ, pred), символьные выражения, оператор присваивания)
3. Процедуры ввода (процедура read: синтаксис и семантика, допустимые типы параметров ввода, буфер ввода и возможность досрочного ввода, readln)

Тема 8. ПРОГРАММА. ОПЕРАТОРЫ
1. Процедуры вывода (процедура write, три формы параметра вывода: e, e:n, e:n:m, вывод целых, логических и символьных данных, особенности вывода вещественных чисел, процедура writeln)
2. Паскаль-программа (структура программы, синтаксис и назначение заголовка, раздела описаний и раздела операторов, правила выполнения программы, правила расстановки пробелов и перевода строк)
3. Операторы (классификация всех операторов: пустой оператор, составной оператор, условный оператор, оператор перехода, метки, раздел меток)

Тема 9. ОПЕРАТОР ЦИКЛА. СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ
1. Оператор цикла: с предусловием (while), с постусловием (repeat), с параметром (for), ограничения на for-цикл
2. Как сделать программу понятной: комментарии, структурная запись, структурное программирование.

Тема 10. ПЕРЕЧИСЛИМЫЕ И ОГРАНИЧЕННЫЕ ТИПЫ
1. Константы (их отличие от переменных, раздел описания констант, стандартные константы: maxint, true, false)
2. Раздел типов (раздел описания типов, переименование типов, два варианта описания переменных нестандартных типов: с заданием имени для нового типа или с использованием безымянного типа)
3. Перечислимые типы (конструктор ПТ, нумерация и упорядоченность имен в ПТ, стандартные функции и операции для ПТ: ord, succ, pred, сравнение, присваивание, for-цикл) 3
4. Оператор варианта (синтаксис и семантика оператора case)
5. Ограниченные типы (особенности присваивание переменным ОТ, отличие этих переменных от переменных базового типа)

Тема 11. РЕГУЛЯРНЫЕ ТИПЫ (МАССИВЫ)
1. Простые массивы (перечень сложных типов Паскаля; понятие массива, переменных с индексами, отличие x1 от x[1], описание регулярных типов (РТ), присваивание массивов, об именной идентичности РТ)
2. Упакованные массивы
3. Многомерные массивы (матрицы = массив массивов, доступ к строкам и элементам матриц, возможное сокращение описания).
4. Строки (определение, тип строки, строки-константы, сравнение строк равной длины, вывод строк)

Тема 12. ПРОЦЕДУРЫ
1. Назначение процедур (формальные и фактические параметры, параметры-значения и параметры-переменные)
2. Описание процедур (синтаксис, назначение заголовка и тела, возможные сокращения в описании формальных параметров)
3. Принцип локализации (понятие о вложенных блоках и области видимости имени/метки; принцип локализации, глобальные и локальные имена процедуры)
4. Оператор процедуры (синтаксис)

Тема 13. ФУНКЦИИ
1. Передача параметров по значению и по ссылке
2. Функции (отличие функций от процедур, синтаксис описания функции и указателя функции)
3. Побочные эффекты функций

Тема 14. РЕКУРСИВНЫЕ ФУНКЦИИ
1. Рекурсивные функции и процедуры (особенности вычисления рекурсивных функций и их описания, рекурсия и циклы предварительные описания)
2. Алгоритмы поиска (перебора) с возвратами и их рекурсивная реализация
3. Параметры-функции и параметры-процедуры

Тема 15. КОМБИНИРОВАННЫЕ И МНОЖЕСТВЕННЫЕ ТИПЫ
1. Комбинированные типы (отличие записей от массивов, описание КТ и переменных-записей, присваивание записей, обозначение поля)
2. Оператор присоединения (простейший и общий вариант оператора, конфликт имен)
3. Множественные типы (особенности множеств в Паскале: конечность, однотипность, описание МТ и переменных-множеств, оператор присваивания для множеств, операции над множествами: отношения, объединение, пересечение, разность)

Тема 16. ФАЙЛОВЫЕ ТИПЫ
1. Файлы (базовый тип, маркер, буферная переменная, отличие от массивов, описание ФТ и переменных-файлов, запрет присваивания файлов, режимы работы с файлами, операции в режиме чтения: reset, eof, get, read и в режиме записи: rewrite, put, write)
2. Текстовые файлы (стандартный тип text, деление текстов на строки, понятие "конец строки", операции для работы со строками: eoln, readln, writeln)
3. Внутренние и внешние файлы

Тема 17. ПРОГРАММИРОВАНИЕ СВЕРХУ ВНИЗ. ТЕСТИРОВАНИЕ. ОТЛАДКА
1. Программирование сверху вниз (достоинства и недостатки)
2. Тестирование (правильная программа, понятие теста и тестирования программы, цель тестирования, методы тестирования)
3. Отладка

Тема 18. ССЫЛОЧНЫЕ ТИПЫ. СПИСКИ
1. Ссылочные типы (понятие ссылки и динамической переменной, графическое изображение ссылок, описание ссылочных типов и ссылочных переменных, пустая ссылка nil, операции над ссылками)
2. Динамические структуры данных
3. Списки (графическое изображение, описание типа списоков, проблема косвенной рекурсии в описании типов)

Тема 19. СТЕК. ОЧЕРЕДЬ
1. Варианты списков (однонаправленные списки без заглавного и с заглавным звеном, циклические списки, двунаправленные списки): достоинства и недостатки
2. Стек (определение, векторное представление стека и реализация операций, списковое представление и реализация операций)
3. Очередь (определение, списковое представление и реализация операций векторное представление и реализация операций)

Тема 20. ДВОИЧНЫЕ (БИНАРНЫЕ) ДЕРЕВЬЯ
1. Определение, представление (понятия вершины, ветви, корня, листьев двоичные деревья и их описание в Паскале)
2. Просмотр дерева
3. Деревья поиска (сравнений) (определение, реализация операций построения дерева по заданной последовательности элементов, поиск, вставка и удаление)

Тема 21. ПОСЛЕДОВАТЕЛЬНЫЕ ТАБЛИЦЫ
1. Таблицы (= набор записей + операция поиска по ключу)
2. Оценка сложности алгоритмов (оценка в худшем случае и в среднем; оптимальный алгоритм поиска и его оценка в худшем случае)
3. Последовательные таблицы (неупорядоченные таблицы, поиск и вставка, оценки сложности) (упорядоченные таблицы, бинарный поиск и вставка, оценки сложности)
4. Сортировка: постановка задачи, наилучшие оценки методов сортировки по числу сравнений и перестановок

Тема 22. ТАБЛИЦЫ-ДЕРЕВЬЯ
1. Таблицы-деревья (оценки сложности для поиска и вставки, выровненные деревья)
2. АВЛ-деревья (понятия уровня вершины и высоты (глубины) дерева, определение АВЛ-дерева, дерева и высотой дерева Фибоначчи, алгоритм вставки в АВЛ-дерево)

Тема 23. ПЕРЕМЕШАННЫЕ ТАБЛИЦЫ (ХЭШ-ТАБЛИЦЫ)
1. Основная идея (ключ --> адрес, функция расстановки (ФР), вставка в таблицу с учетом ФР)
2. Закрытое хеширование (метод линейных проб) (основной принцип, первичная и вторичная ФР, реализация операций вставки и поиска)
3. Открытое хеширование (метод цепочек) (основная идея, операции поиска и вставки, оценки)
4. Функции расстановки
5. Программирование динамических страниц в сети Интернет.

Основная литература
  1. Абрамов В.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль. - М.: КНОРУС, 2011.
  2. Белов В.В., Чистякова В.И. Алгоритмы и структуры данных. - М.: КУРС: ИНФРА-М, 2017.
  3. Вирт Н. Алгоритмы и структуры данных. - СПб.: Невский диалект, 2008.
  4. Круз Р. Структуры данных и проектирование программ. - М.: БИНОМ. Лаборатория знаний, 2008.
  5. Любимский Э.З., Мартынюк В.В., Трифонов Н.П. Программирование. - М.: Наука, 1980.
  6. Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. Машина Тьюринга и алгоритмы Маркова. - М.: МГУ, 2016.

Вопросы?