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

Аннотация

/!\ TODO

Концепция

Лекции

примерный почасовой план

  1. Интуитивное понятие алгоритма. Свойства алгоритмов.
  2. Пример исполнителя (программируемый калькулятор): данные, команды, последовательное, условное и циклическое выполнение.
  3. Алгоритм как преобразование слов из заданного алфавита. Нормальные алгоритмы Маркова.
  4. Машина Тьюринга. Тезис Тьюринга и принцип нормализации, их обоснование.
  5. Алгоритмически неразрешимые проблемы.
  6. Неразрешимость проблем самоприменимости, останова и эквивалентности алгоритмов.
  7. Характеристика алгоритмических языков. Понятие трансляции. Компилируемые и интерпретируемые языки. Понятие исполнителя.
  8. Алфавит, синтаксис и семантика алгоритмического языка. Описание синтаксиса языка с помощью металингвистических формул (БНФ) и синтаксических диаграмм.
  9. История Python. ИКС и неформальное использование Python как калькулятора.
  10. Константы-конструкторы основных скалярных объектов. Операции над объектами. Интерпретация выражения: конструирование и удаление объектов.
  11. Основные типы последовательностей. Индексирование и секционирование. Множественный оператор именования, распаковка последовательностей.
  12. Ссылки на объекты: имена; ссылки из составных объектов. Счётчик ссылок. Идентификаторы объектов и их сравнение.
  13. Условный оператор. Блок операторов. Вложенные операторы.
  14. Оператор цикла с условием. Каноническая схема цикла.
  15. Старшинство операций. Логические операции. Нулевой объект типа.
  16. Функции: задание и оператор вызова. Контекст выполнения, глобальное и локальное пространства имён, их перекрытие.
  17. Оформление исходного кода: комментарии, строки документации, договорённости об именовании. Модернизация языка Python сообществом.
  18. Пространство имён объекта: поля и методы объекта.
  19. Методы последовательностей. Использование последовательностей в качестве стека.
  20. Цикл с итерируемым объектом. Циклические конструкторы объектов.
  21. Строковые методы. Конкатенация и разбиение строк.
  22. Модуль как контейнер имён. Использование модуля. Стандартные модули. Файл как модуль. Строки документации.
  23. Файловый ввод-вывод. Сериализация.

  24. Взаимодействие с ОС: потоки ввода-вывода, параметры командной строки, /!\ …

  25. Понятие вычислительной сложности алгоритмов в худшем случае и в среднем. Поиск и бинарный поиск в упорядоченных последовательностях.
  26. Рекурсия. Достоинства, недостатки, критерий применения в Python.
  27. Алгоритмы поиска с возвратами (backtracking), реализация их с помощью рекурсии. Замещение рекурсии стеком контекстов.
  28. Методы сортировки, оптимальные оценки числа сравнений и перемещений при сортировке.
  29. Задача хеширования. Открытое и закрытое хеширование. Требования к функции расстановки.
  30. Хешируемые объекты Python. Словари. Методы словарей.
  31. Множества, байтовые массивы. Константные (хешируемые) варианты. Операции над множествами.
  32. Позиционные и именованные параметры функции, значение по умолчанию. Упаковка и распаковка параметров функции.
  33. Функции с произвольным количеством и именами параметров. Словари-пространства глобальных и локальных имён.
  34. Генераторы: выражения-генераторы, повторно входимые функции (функции-генераторы). Работа цикла с итерируемым объектом.
  35. Класс как конструктор пространства имён. Экземпляр класса: динамические поля и поля класса. Методы. Вызов метода. Строки документации.
  36. Спецметоды. Реализация операций над объектами путём задания спецметодов.

/!\ TODO: что ещё должно быть: выбрать и подсунуть в нужное место Ещё:

  1. Моделирование списков. Однонаправленные, двунаправленные и циклические списки. Заглавное звено.
  2. Двоичные (бинарные) деревья. Обход дерева с использованием стека, очереди и рекурсии.
  3. Деревья поиска (сравнений), алгоритмы поиска, вставки и удаления элементов.
  4. Куча
  5. Замыкание транзитивного бинарного отношения.
  6. Моделирование многомерных массивов.
  7. Исключения как средство управления потоком вычислений