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

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

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

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

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

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

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

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

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

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

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