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

Концепция

1. Введение в теорию алгоритмов
   • В основном без изменений
   • Организовать практику по МТ и НАМ
   • Увеличить в объёме тему УМ, организовать практику и построить обучение второго семестра на этой базе (примерно наполовину)
2. Алгоритмические языки. Язык Python
   • Выделить тематические составляющие и построить большую часть курса аналогично
   • Использовать классы как конструкторы пространства имён (строго без ООП)
   • Подробно описывать достаточное подмножество языка, остальное тезисно (спецкурс? 4-й семестр?)

   • 

3. Динамические структуры данных
   • «Динамические структуры данных» — это не «то, что можно сконструировать», а «то, что удобно использовать в алгоритмах» ⇒ конструируем сами, изучаем, некоторые берём готовые
   • Возможно, хватит для большего числа алгоритмов

Сравнительная таблица

TODO Часть 1. Введение в теорию алгоритмов

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

Часть 2. Алгоритмические языки. Язык Паскаль

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

Часть 3. Динамические структуры данных

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

Третья