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

текст содержит несколько поясняющих комментариев, для их показа надо нажать «Комментарии» в начале или в конце страницы

Аннотация

TODO общее описание

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

Курс состоит из четырёх неравных по объёму тематических разделов:

1. Введение в теорию алгоритмов. Алгоритмические языки.
   • Теоретическая база алгоритмизации и примеры реализующих её формализмов
2. Основы ЯП Python
   • Термины и понятия; базовый набор операторов и структур данных, необходимых для того, чтобы составлять и изучать алгоритмы
3. Возможности ЯП Python
   • Подмножество ЯП, достаточное для эффективного программирования; семантика работы исполнителя

4. Алгоритмы и структуры данных.

   • Классические алгоритмы и структуры данных, в них используемые

Темы последнего раздела идут не отдельно в конце семестра, а появляются после изучения подходящей конструкции ЯП или приёма программирования. Помечены значком .

Практическую поддержку курсу обеспечивает «Практикум на ЭВМ». Основные цели практикума:

• практическое изучение алгоритмического языка Python;
• приобретение навыков разработки, тестирования и отладки программ для ЭВМ;
• приобретение практического опыта работы на ЭВМ, в системах программирования.

Практикум включает в себя:

• аудиторные семинарские занятия, направленные на закрепление лекционного теоретического материала и разбор дополнительного;
• лабораторные занятия в компьютерном зале, предназначенные для постановки практических навыков и приёмов программирования;

• выполнение домашних заданий с обязательной проверкой решений в системе проверки домашних заданий EJudge или похожие .

Лекции

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

Введение в теорию алгоритмов. Алгоритмические языки

1. Интуитивное понятие алгоритма: преобразование данных исполнителем на основании команд. Свойства алгоритмов.

   Требования к данным/командам/исполнителю:

   Задача	Сущность	Свойство исполнителя
   Что преобразуем?	Данные	Референция данных (произвольное обращение к определённым данным из программы)
   Как преобразуем?	Команды	Правила выполнения самих команд и выбора команд для выполнения из набора (программы)
   Что как преобразуем?	Управление	Зависимость свойств исполнителя от свойств данных (управляемая данными референция/команды/выбор команды)

   Не все требования должны быть 100% реализованы, но в какой-то мере должны.

2. Программируемый калькулятор: данные, команды, последовательное, условное и циклическое выполнение.

   Дано: калькулятор. Понимает числа, 4 действия арифметики и = (не стековый). Имеет кнопки M+ и MR.

   Надо: превратить его в компьютер, который может что хочешь арифметическое посчитать. То, что мы сами можем на калькуляторе посчитать, но без нас, самостоятельно.

   Чего не хватает?

   1. Хранения команд, чтобы сам вычислял.
      • Есть несколько вариантов
      • Допустим, команды — это кнопки калькулятора. Хранятся и выполняются
        • подряд.
   2. Хранения входных и выходных данных (или ввода и вывода их), а также промежуточнЫХ результатОВ вычислений
      • Есть много вариантов!
      • Допустим, заведём и пронумеруем ячейки с данными, в которых будем всё хранить (перед началом записывать, после конца — считывать) а ещё сделаем операции M+ и MR двухместными (второй параметр — номер ячейки).
   3. Вычисления не всего (подряд), а только соответствующие куски формулы
      • Есть очень много вариантов! Например, раскрашивание команд и выполнение только команд одного цвета. Но непонятно, как организовать.
      • Воспользуемся готовым решением: перенумеруем ячейки команд и сделаем команду перехода
   4. Вычисления не всегда, а только если некоторые свойства данных этого требуют
      • Есть много вариантов!
      • Допустим, введём команды вычисления свойств данных (например, сравнения) и команды условного перехода
   5. Обращения к ячейке, номер которой надо ещё вычислить
      • Есть много вариантов! Например, косвенная адресация.
      • Так как номера команд и номера ячеек уже есть, введём команды самомодификации кода (вычислить номер ячейки, записать этот номер внутрь команды).
   6. Вычислять одну и ту же формулу, пока данные не приобретут желаемые свойства
      • Есть много вариантов, но у нас уже есть готовое решение: условный переход, ничего придумывать не надо.
3. Алгоритм как преобразование слов из заданного алфавита. Нормальные алгоритмы Маркова.
4. Машина Тьюринга. Тезис Тьюринга и принцип нормализации, их обоснование.
5. Алгоритмически неразрешимые проблемы.
6. Неразрешимость проблем самоприменимости, останова и эквивалентности алгоритмов.

7. …

8. Характеристика алгоритмических языков. Понятия исполнителя и трансляции. Компилируемые и интерпретируемые языки.
9. Алфавит, синтаксис и семантика алгоритмического языка. Описание синтаксиса языка с помощью металингвистических формул (БНФ) и синтаксических диаграмм.

Основы ЯП Python

11. Константы-конструкторы основных скалярных объектов. Операции над объектами. Интерпретация выражения: конструирование и удаление объектов. Именование объектов, оператор связывания.
12. Основные типы последовательностей. Индексирование и секционирование. Множественный оператор связывания, распаковка последовательностей.
13. Логические выражения. Условный оператор. Блок операторов. Вложенные операторы.

14. Оператор цикла с условием. Каноническая схема цикла. Оператор цикла с последовательностью. Клауза else в цикле. Пример: успешный/неуспешный поиск

15. Функции: задание и оператор вызова. Контекст выполнения, глобальное и локальное пространства имён, их перекрытие.
16. Оформление кода. Строки документации, комментарии, соглашение об именах. Модернизация языка Python сообществом.

17. Понятие вычислительной сложности алгоритмов в худшем случае и в среднем. Поиск и бинарный поиск в упорядоченных последовательностях.

18. Методы сортировки, оптимальные оценки числа сравнений и перемещений при сортировке.

19. Стандартные модули. Основные функции стандартных модулей math, random, os, sys и т. п.

20. Конструирование пространства имён: модули и классы. Экземпляры классов.
21. Интерактивный и файловый ввод-вывод. Параметры командной строки.

22. Рекурсия. Достоинства, недостатки, критерий применения в Python.

Возможности ЯП Python

25. Референция объектов: имена и ссылки из составных объектов. Счётчик ссылок. Идентификаторы объектов и их сравнение.
26. Старшинство операций. Логические операции. Нулевой объект типа.

27. Скалярные типы данных. Что ещё?

28. Пространство имён объекта: поля и методы объекта. Функция dir(). Первый параметр метода.

29. Методы последовательностей. Использование последовательностей в качестве стека. collections.deque и очереди

30. Алгоритмы поиска с возвратами (backtracking), реализация их с помощью рекурсии. Замещение рекурсии стеком контекстов.

31. Строковые методы. Байтовые массивы.

32. Z-функция, π-функция и поиск подстроки

33. Исключения как средство управления потоком вычислений

34. Задача хеширования. Открытое и закрытое хеширование. Требования к функции расстановки.

35. Хешируемые объекты Python. Словари. Методы словарей. Хешируемые (константные) варианты множеств и т. п.

36. Моделирование многомерных массивов. Модуль array. Ссылка на numpy

37. Множества и операции с ними. Циклические конструкторы различных объектов.
38. Позиционные и именованные параметры функции, значение по умолчанию. Упаковка и распаковка параметров функции.
39. Функции с произвольным количеством и именами параметров. Словари-пространства глобальных и локальных имён.

40. Двоичные (бинарные) деревья. Обход дерева с использованием стека, очереди и рекурсии.

41. Деревья поиска (сравнений), алгоритмы поиска, вставки и удаления элементов.

42. Генераторы: выражения-генераторы, повторно входимые функции (функции-генераторы). Работа цикла с итерируемым объектом.
43. Спецметоды. Реализация операций над объектами путём задания спецметодов.

Дополнительные главы

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

1. eval() / exec()

2. Куча

3. Замыкание транзитивного бинарного отношения.

4. Сериализация и бинарные данные
5. Элементы функционального программирования.
6. Объектное планирование в разработке программ. ООП.
7. Наследование и полиморфизм
8. Полезные модули !. Внутреннее устройство исполнителя: байт-код, стек-машина, словари имён и т. п.

9. Ещё, см., например курс для Московской Биржи

Практикум

TODO Видимо, стоит темы практикума прямо в лекциях задачать

1. Интерпретатор командной строки. Использование Python в качестве калькулятора.
2. Неформальное введение в Python. Работа со справочным материалом.

…

Семестровый проект: простейший эмулятор МТ, НАМ, ПК и т.п.