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

Аннотация

TODO

Концепция

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

Лекции

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

18. Взаимодействие с ОС: файловый ввод-вывод, …

19. Понятие вычислительной сложности алгоритмов в худшем случае и в среднем. Поиск и бинарный поиск в упорядоченных последовательностях.
20. Рекурсия. Достоинства, недостатки, критерий применения в Python. Замещение рекурсии стеком контекстов.
21. Методы сортировки, оптимальные оценки числа сравнений и перемещений при сортировке.
22. Задача хеширования. Открытое и закрытое хеширование. Требования к функции расстановки.
23. Хешируемые объекты Python. Словари. Методы словарей.
24. Множества, байтовые массивы. Константные (хешируемые) варианты. Операции над множествами.
25. Упаковка и распаковка параметров функции. Функции с произвольным количеством и именами параметров. Словари-пространства глобальных и локальных имён.
26. Генераторы: выражения-генераторы, повторно входимые функции (функции-генераторы). Работа цикла с итерируемым объектом.
27. Модуль как контейнер имён. Использование модуля. Стандартные модули. Файл как модуль. Строки документации.
28. Класс как конструктор пространства имён. Экземпляр класса: динамические поля и поля класса. Методы. Вызов метода. Строки документации.
29. Спецметоды. Реализация операций над объектами путём задания спецметодов.

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

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