Алгоритмы и алгоритмические языки

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

Лектор — В. Н. Пильщиков, 2-ой поток 2006 г. (см. источник).

Элементы теории алгоритмов

• Интуитивное определение алгоритмов, свойства алгоритмов. Блок-схемы.
• Уточнение понятия алгоритма, алгоритм как преобразование слов. Применимость и неприменимость алгоритма к слову.
• Машина Тьюринга. Схема построения композиции машин Тьюринга. Тезис Тьюринга и его обоснование.
• Нормальные алгоритмы Маркова. Принцип нормализации и его обоснование.
• Алгоритмически неразрешимые проблемы: определение и примеры (проблемы самоприменимости, останова и эквивалентности алгоритмов). Доказательство неразрешимости проблемы самоприменимости алгоритмов.
• Модельная ЭВМ (эта тема не выносится на экзамен).

Язык Паскаль (стандартная версия)

• Понятие о метаязыках. Метаязыки для описания синтаксиса алгоритмических языков: металингвистические формулы (БНФ), синтаксические диаграммы.
• Алфавит, идентификаторы, служебные слова и имена, стандартные имена.
• Типы данных: определение, назначение и классификация. Переменные, раздел переменных. Константы, раздел констант.
• Числовые типы (целый и вещественный), запись чисел, операции и стандартные функции, арифметические выражения. Оператор присваивания.
• Логический тип, операции и стандартные функции, логические выражения.
• Символьный тип, операции и стандартные функции.
• Структура Паскаль-программы, заголовок программы, блок.
• Процедуры ввода и вывода.
• Классификация операторов Паскаля. Составной, пустой и условный операторы. Оператор перехода, раздел меток.
• Оператор цикла. Понятие о структурном программировании.
• Раздел типов. Описание нестандартных типов. Перечислимые типы, операции и стандартные функции. Оператор варианта. Ограниченные типы.
• Регулярные типы (массивы), типы индексов, индексированные переменные. Упакованные массивы, многомерные массивы. Строковые типы, дополнительные возможности для работы со строками.
• Процедуры и функции, их назначение. Раздел процедур и функций, описание процедур и функций. Правило локализации. Оператор процедуры и указатель функций. Передача параметров по значению и по ссылке. Побочные эффекты функций. Параметры-функции и параметры-процедуры.
• Рекурсивные функции и процедуры. Опережающие описания. Алгоритмы поиска с возвратами, их реализация с помощью рекурсии.
• Комбинированные типы (записи), обозначение поля. Оператор присоединения.
• Множественные типы, операции над множествами, выражения множественных типов.
• Файловые типы, режимы работы с файлами, операции над файлами. Текстовые файлы, дополнительные возможности для работы с ними. Внутренние и внешние файлы.
• Программирование сверху вниз. Тестирование программ: цель тестирования, стратегии черного и белого ящиков, методы составления тестов. Отладка программ.
• Ссылочные типы, динамические переменные, переменные с указателем, операции над ссылками.

Динамические структуры данных

• Списки (однонаправленные): определение, описание на языке Паскаль, реализация основных операций (поиск, вставка и удаление). Другие варианты списков.
• Стек: определение, векторное и списковое представления, реализация операций.
• Очередь: определение, векторное и списковое представления, реализация операций.
• Двоичные деревья: определение, описание на языке Паскаль; алгоритмы просмотра деревьев. Деревья поиска, реализация операций поиска, вставки и удаления.
• Таблицы; операции поиска по ключу и вставки. Понятие оценки сложности алгоритмов (в худшем случае и в среднем). Оценка сложности оптимального алгоритма поиска.
• Последовательные таблицы (неупорядоченные и упорядоченные), реализация операций бинарного поиска по ключу и вставки. Оценки сложности этих операций.
• Представление таблиц в виде деревьев поиска (таблицы-деревья); оценки сложности операций поиска по ключу и вставки. АВЛ-деревья: определение, оценка сложности поиска в АВЛ-деревьях (совершенные деревья, деревья Фибоначчи), алгоритм вставки в АВЛ-дерево.
• Перемешанные таблицы, закрытое хеширование (метод линейных проб) и открытое хеширование (метод цепочек), оценки сложности операций. Функции расстановки.

Основная литература

• Э. З. Любимский, В. В. Мартынюк, Н. П. Трифонов. Программирование. — М.: Наука, 1980.
• Л. С. Корухова, М. Р. Шура-Бура. Введение в алгоритмы. — М.: ВМК МГУ, 1997.
• В. Г. Абрамов, Н. П. Трифонов, Г. Н. Трифонова. Введение в язык Паскаль. — М.: Наука, 1988.
• К. Йенсен, Н. Вирт. Паскаль. Руководство для пользователя. — М.: «Компьютер», 1993.
• Н. Вирт. Алгоритмы и структуры данных. — СПб.: «Невский диалект», 2001.
• А. Ахо, Д. Хопкрофт, Д. Ульман. Структуры данных и алгоритмы. — М.: «Вильямс», 2001.
• В. П. Иванников, Л. С. Корухова, В. Н. Пильщиков. Письменный экзамен по курсу «Алгоритмы и алгоритмические языки». — М.: ВМК МГУ, 2002.