Программа курса лекций «Алгоритмы и алгоритмические языки» для студентов 1
курса. 2001/2002 учебный год
Лектор – профессор В. П. Иванников.


Часть 1. Алгоритмы
- Алгоритмы. Основные свойства алгоритмов.
- Машина Тьюринга. Тезис Тьюринга.
- Диаграммы Тьюринга. Примеры машин Тьюринга.
- Варианты машин Тьюринга.
- Машины Тьюринга. Неразрешимость проблемы останова.
- Машина Маркова. Тезис Маркова. Примеры машин Маркова.
- Композиция машин Маркова.
- Машины Маркова. Неразрешимость проблемы самоприменимости.
Часть 2. Алгоритмические языки. Язык Паскаль
- Синтаксис и семантика языка. Синтаксические диаграммы. Примеры.
- Имена и числа.
- Простые типы данных.
- Перечислимые и ограниченные типы данных.
- Регулярный, комбинированный и множественный типы данных.
- Файловый тип данных. Программа игры в лото.
- Операторы: составной, выбирающий, цикла, присоединения.
- Рекуррентные соотношения и итерации. Программирование рекуррентных соотношений.
- Процедуры и функции. Способы передачи параметров.
- Локализация имен. Коллизии.
- Итерации и рекурсии. Примеры рекурсивных и итеративных программ.
- Ссылочный тип данных.
- Структура программы.
Часть 3. Структуры данных
- Абстрактные структуры. Отношения.
- Графы, деревья, линейные деревья(списки).
- Стек. Отображение на линейную и списковую памяти.
- Очередь. Отображение на линейную и списковую памяти.
- Внутренние таблицы. Операции с последовательными таблицами в
векторной памяти. Оценки сложности.
- Таблицы, организованные как деревья сравнений. Деревья Фибоначчи.
- Деревья. Определение. Способы обхода дерева. Рекурсивные процедуры обхода деревьев.
- Деревья двоичного поиска. Процедуры поиска, вставки и удаления элемента для дерева двоичного поиска.
- Сбалансированные деревья. Характеристика различных видов сбалансированных деревьев (совершенные деревья, деревья Фибоначчи, АВЛ-деревья, 2-3 деревья, понятие красно-черных деревьев)
- АВЛ-деревья. Поиск. Оценка сложности.
- АВЛ-деревья. Включение. Оценка сложности.
- 2-3 деревья. Вставка элемента в 2-3 дерево. Удаление элемента из 2-3 дерева.
- Перемешанные таблицы. Поиск. Оценка сложности.
- Перемешанные таблицы. Включение и исключение. Коллизии.
- Поиск с возвращением. Задача расстановки ферзей.
- Метод решета. Решето Эратосфена.
- Метод разделяй и властвуй. Быстрая сортировка.
Литература
- М. Минский. Вычисления и автоматы. М.: «Мир», 1971.
- Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. МЦНМО, 1999.
- Н. Вирт. Алгоритмы + структуры данных = программы. М.: «Мир», 1985.
- К. Йенсен, Н. Вирт. Паскаль. Руководство для пользователя. М.: «Финансы и статистика», 1989.
- В. Г. Абрамов, Н. П. Трифонов, Г. Н. Трифонова. Введение в язык Паскаль. М.: «Наука», 1988.
- Д. Кнут. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. М.: Издательский дом «Вильямс», 2000.
- Д. Кнут. Искусство программирования для ЭВМ. Т.2. Сортировка и поиск. М.: Издательский дом «Вильямс», 2000.
- Г. Лорин. Сортировка и системы сортировки. М.: «Наука», 1983.
- М. Сибуя, Т. Ямомото. Алгоритмы обработки данных. М.: «Мир», 1986.
- П. Холл. Вычислительные структуры. Введение в нечисленное программирование. М.: «Мир», 1978.
- Э. З. Любимский, В. В. Мартынюк, Н. П. Трифонов. Программирование. М.: «Наука», 1980.
- А. Ахо, Д. Хопкрофт, Д. Ульман. Структуры данных и алгоритмы. М.: Издательский дом «Вильямс», 2000.
Скачать
- Текст программы курса (zip-архив файла в формате WinWord97: http)
- Текст программы курса (zip-архив txt-файла в кодировке Win-1251: http)

