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

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

Лектор — В. П. Иванников, 1-ый поток 2001 г. (cм. источник).

Часть 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.