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

Аннотация

TODO

Концепция

• Цели курса:
  • Заложить основы алгоритмического мышления
  • Дать эффективный язык описания алгоритмов и структур данных
  • Дать универсальный инструмент программирования
• Задачи курса:
  • Познакомить с основами теории алгоритмов
  • Привить представление об ЭВМ как алгоритмическом исполнителе команд, и о языке программирования как о формализации таких команд
  • Развить навыки составления алгоритмов и отлаживания программ на языке Python3
  • Познакомить с алгоритмами и структурами данных, используемыми при решении типовых задач

Лекции

TODO Расписать по часам или по парам

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

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

1. (алгоритмические языки) Оформление исходного кода: комментарии, строки документации, договорённости об именовании. Модернизация языка (PEP-ы).
2. (алгоритмы) Понятие вычислительной сложности алгоритмов в худшем случае и в среднем. Поиск и бинарный поиск в упорядоченных последовательностях.
3. (типы данных) Множества, байтовые массивы. Константные (хешируемые) варианты. Операции над множествами.
4. (алгоритмы) Эффективность операций над структурами данных. Индексация в последовательностях и индексация в массивах. Эффективность итераторов в последовательностях.
5. (алгоритмы) Моделирование списков. Двунаправленные и циклические списки. Моделирование графов. Деревья.
6. (алгоритмы) Двоичные (бинарные) деревья. Обход дерева с использованием стека, очереди и рекурсии. Деревья поиска (сравнений), алгоритмы поиска, вставки и удаления элементов.
7. (алгоритмы) Сбалансированные деревья, их свойства. Вставка и удаление элементов.
8. (алгоритмы) Куча
9. (алгоритмы) Замыкание транзитивного бинарного отношения.
10. (типы данных) Моделирование многомерных массивов.
11. (операторы) Исключения как средство управления потоком вычислений