Программа курса «Алгоритмы и алгоритмические языки» |
Программа курса «Алгоритмы и алгоритмические языки»
1 курс, 2-й поток (107-112 группы)
Лектор – В. Н. Пильщиков
ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
Интуитивное определение алгоритмов, свойства алгоритмов. Блок-схемы.
Уточнение понятия алгоритма, алгоритм как преобразование слов. Применимость и неприменимость алгоритма к слову.
Машина Тьюринга. Схема построения композиции машин Тьюринга. Тезис Тьюринга и его обоснование.
Нормальные алгоритмы Маркова. Принцип нормализации и его обоснование.
Алгоритмически неразрешимые проблемы: определение и примеры (проблемы самоприменимости, останова и эквивалентности алгоритмов). Доказательство неразрешимости проблемы самоприменимости алгоритмов.
Модельная ЭВМ (эта тема не выносится на экзамен).
ЯЗЫК ПАСКАЛЬ (стандартная версия)
Понятие о метаязыках. Метаязыки для описания синтаксиса алгоритмических языков: металингвистические формулы (БНФ), синтаксические диаграммы.
Алфавит, идентификаторы, служебные слова и имена, стандартные имена.
Типы данных: определение, назначение и классификация. Переменные, раздел переменных. Константы, раздел констант.
Числовые типы (целый и вещественный), запись чисел, операции и стандартные функции, арифметические выражения. Оператор присваивания.
Логический тип, операции и стандартные функции, логические выражения.
Символьный тип, операции и стандартные функции.
Структура Паскаль-программы, заголовок программы, блок.
Процедуры ввода и вывода.
Классификация операторов Паскаля. Составной, пустой и условный операторы. Оператор перехода, раздел меток.
Оператор цикла. Понятие о структурном программировании.
Раздел типов. Описание нестандартных типов. Перечислимые типы, операции и стандартные функции. Оператор варианта. Ограниченные типы.
Регулярные типы (массивы), типы индексов, индексированные переменные. Упакованные массивы, многомерные массивы. Строковые типы, дополнительные возможности для работы со строками.
Процедуры и функции, их назначение. Раздел процедур и функций, описание процедур и функций. Правило локализации. Оператор процедуры и указатель функций. Передача параметров по значению и по ссылке. Побочные эффекты функций. Параметры-функции и параметры-процедуры.
Рекурсивные функции и процедуры. Опережающие описания. Алгоритмы поиска с возвратами, их реализация с помощью рекурсии.
Комбинированные типы (записи), обозначение поля. Оператор присоединения.
Множественные типы, операции над множествами, выражения множественных типов.
Файловые типы, режимы работы с файлами, операции над файлами. Текстовые файлы, дополнительные возможности для работы с ними. Внутренние и внешние файлы.
Программирование сверху вниз. Тестирование программ: цель тестирования, стратегии черного и белого ящиков, методы составления тестов. Отладка программ.
Ссылочные типы, динамические переменные, переменные с указателем, операции над ссылками.
ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
Списки (однонаправленные): определение, описание на языке Паскаль, реализация основных операций (поиск, вставка и удаление). Другие варианты списков.
Стек: определение, векторное и списковое представления, реализация операций.
Очередь: определение, векторное и списковое представления, реализация операций.
Двоичные деревья: определение, описание на языке Паскаль; алгоритмы просмотра деревьев. Деревья поиска, реализация операций поиска, вставки и удаления.
Таблицы; операции поиска по ключу и вставки. Понятие оценки сложности алгоритмов (в худшем случае и в среднем). Оценка сложности оптимального алгоритма поиска.
Последовательные таблицы (неупорядоченные и упорядоченные), реализация операций бинарного поиска по ключу и вставки. Оценки сложности этих операций.
Представление таблиц в виде деревьев поиска (таблицы-деревья); оценки сложности операций поиска по ключу и вставки. АВЛ-деревья: определение, оценка сложности поиска в АВЛ-деревьях (совершенные деревья, деревья Фибоначчи), алгоритм вставки в АВЛ-дерево.
Перемешанные таблицы, закрытое хеширование (метод линейных проб) и открытое хеширование (метод цепочек), оценки сложности операций. Функции расстановки.
ОСНОВНАЯ ЛИТЕРАТУРА
1. Любимский Э.З., Мартынюк В.В., Трифонов Н.П. Программирование. – М.: Наука, 1980.
2. Корухова Л.С., Шура-Бура М.Р. Введение в алгоритмы. – М.: ВМК МГУ, 1997.
3. Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. Машины Тьюринга и алгоритмы Маркова. Решение задач. – М.: МГУ, 2006.
4. Абрамов В.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль. – М.: Наука, 1988.
5. Йенсен К., Вирт Н. Паскаль. Руководство для пользователя. – М.: «Компьютер», 1993.
6. Вирт Н. Алгоритмы и структуры данных. – СПб.: «Невский диалект», 2001.
7. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. – М.: «Вильямс», 2001.
8. Иванников В.П., Корухова Л.С., Пильщиков В.Н. Курс «Алгоритмы и алгоритмические языки». Варианты письменного экзамена. – М.: МГУ, 2007.