Алгоритмы и алгоритмические языки
Предполагается адаптация курса на базе Паскаля, в котором сохранить структуру изложения, а темы адаптировать к Питону. При необходимости добавить / преобразовать / удалить подтемы.
Концепция
- Введение в теорию алгоритмов
- В основном без изменений
- Организовать практику по МТ и НАМ
- Увеличить в объёме тему УМ, организовать практику и построить обучение второго семестра на этой базе (примерно наполовину)
- Алгоритмические языки. Язык Python
- Выделить тематические составляющие и построить большую часть курса аналогично
- Использовать классы как конструкторы пространства имён (строго без ООП)
- Подробно описывать достаточное подмножество языка, остальное тезисно (спецкурс? 4-й семестр?)
- Динамические структуры данных
- «Динамические структуры данных» — это не «то, что можно сконструировать», а «то, что удобно использовать в алгоритмах» ⇒ конструируем сами, изучаем, некоторые берём готовые
- Возможно, хватит времени для большего числа алгоритмов
К лекциям прилагаются задания в EJudge.
Сравнительная таблица
В таблице для краткости используются урезанные формулировки, полные версии см. в PascalAAL. Курс Паскаля |
Курс Питона |
Замечания |
Часть 1. Введение в теорию алгоритмов |
Интуитивное понятие алгоритма. Свойства алгоритмов. |
|
|
Алгоритм как преобразование слов из заданного алфавита. МТ. НАМ |
|
|
Композиция алгоритмов, тезис Тьюринга |
|
|
Алгоритмически неразрешимые проблемы |
|
|
Модельная ЭВМ |
|
|
Часть 2. Алгоритмические языки. Язык Паскаль |
АЯ, синтаксис, семантика, прагматика. БНФ |
|
|
|| Структура ЯП Паскаль и программы ||
- Язык Паскаль (стандартная версия). Алфавит, служебные слова и стандартные имена. Структура программы: заголовок программы и блок, разделы описаний и операторов. Типы данных, их классификация. Переменные и константы, разделы переменных и констант. Стандартные простые типы (числовые, логический, символьный). Выражения. Оператор присваивания. Стандартные процедуры ввода-вывода. Операторы, их классификация. Пустой, составной и условный операторы. Оператор перехода, раздел меток. Операторы цикла. Способы повышения наглядности программы: комментарии, структурная запись программ, структурное программирование. Нестандартные типы данных, раздел типов. Перечислимые и ограниченные типы. Оператор варианта. Процедуры и функции. Формальные и фактические параметры. Локализация имен и меток. Способы передачи параметров. Побочные эффекты функций. Параметры-функции и параметры-процедуры. Рекурсивные процедуры и функции. Итерация и рекурсия. Алгоритмы поиска с возвратами (backtracking), реализация их с помощью рекурсии. Сложные типы данных. Массивы, строки. Записи; оператор присоединения. Множества. Файлы, текстовые файлы, внешние и внутренние файлы. Динамические переменные. Ссылочные типы данных. Методы разработки программы (пошаговая детализация и др.). Тестирование и отладка программ.
Часть 3. Динамические структуры данных
- Списки. Представление списков и реализация основных операций на ними в языке Паскаль. Варианты списков (с заглавным звеном, циклические, двунаправленные). Стек, очередь. Векторное и списковое представления их, реализация операций на ними. Двоичные (бинарные) деревья. Обход дерева с использованием стека, очереди и рекурсии. Деревья поиска (сравнений), алгоритмы поиска, вставки и удаления элементов. Таблицы, операция поиска по ключу. Последовательные таблицы (неупорядоченные и упорядоченные). Понятие о (временнóй) оценке сложности алгоритмов в худшем случае и в среднем. Оценка сложности оптимального алгоритма поиска по ключу. Бинарный поиск в упорядоченных таблицах. Методы сортировки, оптимальные оценки числа сравнений и перемещений при сортировке. Представление таблиц в виде деревьев поиска (сравнений), оценки сложности поиска по ключу в таких таблицах. АВЛ-деревья, оценки сложности поиска, алгоритм вставки. Перемешанные таблицы (хэш-таблицы). Функции расстановки. Устранение коллизий методами закрытого хеширования (линейных проб) и открытого хеширования (цепочек).
Третья