## page was renamed from Python/PythonBaseCourseAlternative
= Алгоритмы и алгоритмические языки =

''текст содержит несколько поясняющих комментариев, для их показа надо нажать «<<GetText(Comments)>>» в начале или в конце страницы''

== Аннотация ==

/!\ TODO общее описание

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

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

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

Практическую поддержку курсу обеспечивает «Практикум на ЭВМ». Основные цели практикума:
 * практическое изучение алгоритмического языка Python;
 * приобретение навыков разработки, тестирования и отладки программ для ЭВМ;
 * приобретение практического опыта работы на ЭВМ, в системах программирования.

Практикум включает в себя:
 * аудиторные семинарские занятия, направленные на закрепление лекционного теоретического материала и разбор дополнительного;
 * лабораторные занятия в компьютерном зале, предназначенные для постановки практических навыков и приёмов программирования;
 * выполнение домашних заданий с обязательной проверкой решений в системе проверки домашних заданий /* EJudge или похожие */ .

{{{#!wiki comment
Замечания:
 1. У всех уже есть компьютеры и/или планшеты
  * ⇒ С выполнением домашнего задания проблемы не в отсутствии ресурсов, а в неунифицированности окружений на разных устройствах
   * ⇒ Устроить отдельное занятие (часть занятия) по установке и использованию Python и какого-нибудь IDE (да хоть [[http://geany.org|Geany]])
   * ⇒ Неплохо предоставить доступ к унифицированному окружению, что-то вроде [[https://www.pythonanywhere.com/|PythonAnywhere]], либо ориентироваться на полностью броузерные средства, наподобие [[http://www.brython.info/index.html|Brython]]
 1. Современному первокруснику проще написать текст в текстовом редакторе, чем на доске/бумажке
  * ⇒ семинарские занятия, посвящённые практическим вопросам, надо превращать в лабораторные
   * Возможно, стоит использовать какое-то ПО для демонстрации
  * ⇒ В классах должно быть унифицированное окружение (как для ВМШ)
 1. С проверкой Д/З отлично справляется [[https://ejudge.cs.msu.ru/|EJudge]]
  * К каждой задаче нужны тесты
  * В код смотреть всё равно надо
}}}

== Лекции ==
''примерный почасовой план''

=== Введение в теорию алгоритмов. Алгоритмические языки ===
 1. Интуитивное понятие алгоритма: преобразование данных исполнителем на основании команд. Свойства алгоритмов.
 {{{#!wiki comment
Требования к данным/командам/исполнителю:
|| '''Задача''' || '''Сущность''' || '''Свойство исполнителя''' ||
|| Что преобразуем? || Данные || Референция данных (произвольное обращение к определённым данным из программы)||
|| Как преобразуем? || Команды || Правила выполнения самих команд и выбора команд для выполнения из набора (программы) ||
|| Что как преобразуем? || Управление || Зависимость свойств исполнителя от свойств данных (управляемая данными референция/команды/выбор команды)||
Не все требования должны быть 100% реализованы, но в какой-то мере должны.
 }}}
 1. Программируемый калькулятор: данные, команды, последовательное, условное и циклическое выполнение.
 {{{#!wiki comment
''Дано'': калькулятор. Понимает числа, 4 действия арифметики и = (не
стековый). Имеет кнопки M+ и MR.

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

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

 1. Хранения команд, чтобы сам вычислял.
  * Есть несколько вариантов
  * Допустим, команды — это кнопки калькулятора. Хранятся и выполняются
   подряд.
 1. Хранения входных и выходных данных (или ввода и вывода их), а также промежуточнЫХ результатОВ вычислений
  * Есть много вариантов!
  * Допустим, заведём и пронумеруем ячейки с данными, в которых будем всё хранить (перед началом записывать, после конца — считывать) а ещё сделаем операции M+ и MR двухместными (второй параметр — номер ячейки).
 1. Вычисления не всего (подряд), а только соответствующие куски формулы
  * Есть очень много вариантов! Например, раскрашивание команд и выполнение только команд одного цвета. Но непонятно, как организовать.
  * Воспользуемся готовым решением: перенумеруем ячейки команд и сделаем команду перехода
 1. Вычисления не всегда, а только если некоторые свойства данных этого требуют
  * Есть много вариантов!
  * Допустим, введём команды вычисления свойств данных (например, сравнения) и команды условного перехода
 1. Обращения к ячейке, номер которой надо ещё вычислить
  * Есть много вариантов! Например, косвенная адресация.
  * Так как номера команд и номера ячеек уже есть, введём команды самомодификации кода (вычислить номер ячейки, записать этот номер внутрь команды).
 1. Вычислять одну и ту же формулу, пока данные не приобретут желаемые свойства
  * Есть много вариантов, но у нас уже есть готовое решение: условный переход, ничего придумывать не надо.
 }}}
 1. Алгоритм как преобразование слов из заданного алфавита. Нормальные алгоритмы Маркова.
 1. Машина Тьюринга. Тезис Тьюринга и принцип нормализации, их обоснование.
 1. Алгоритмически неразрешимые проблемы.
 1. Неразрешимость проблем самоприменимости, останова и эквивалентности алгоритмов.
 1. … /!\
 1. Характеристика алгоритмических языков. Понятия исполнителя и трансляции. Компилируемые и интерпретируемые языки.
 1. Алфавит, синтаксис и семантика алгоритмического языка. Описание синтаксиса языка с помощью металингвистических формул (БНФ) и синтаксических диаграмм.
<<Anchor(Basic)>>
=== Основы ЯП Python ===
 1.#11 Константы-конструкторы основных скалярных объектов. Операции над объектами. Интерпретация выражения: конструирование и удаление объектов. Именование объектов, оператор связывания.
 1. Основные типы последовательностей. Индексирование и секционирование. Множественный оператор связывания, распаковка последовательностей.
 1. Логические выражения. Условный оператор. Блок операторов. Вложенные операторы.
 1. Оператор цикла с условием. Каноническая схема цикла. Оператор цикла с последовательностью. /* Клауза `else` в цикле. Пример: успешный/неуспешный поиск */
 1. Функции: задание и оператор вызова. Контекст выполнения, глобальное и локальное пространства имён, их перекрытие.
 1. Оформление кода. Строки документации, комментарии, соглашение об именах.  Модернизация языка Python сообществом.
 1. (!) Понятие вычислительной сложности алгоритмов в худшем случае и в среднем. Поиск и бинарный поиск в упорядоченных последовательностях.
 1. (!) Методы сортировки, оптимальные оценки числа сравнений и перемещений при сортировке.
 1. Стандартные модули. Основные функции стандартных модулей `math`, `random`, `os`, `sys` и т. п.
 1. Конструирование пространства имён: модули и классы. Экземпляры классов.
 1. Интерактивный и файловый ввод-вывод. Параметры командной строки.
 1. (!) Рекурсия. Достоинства, недостатки, критерий применения в Python.
=== Возможности ЯП Python ===
 1.#25 Референция объектов: имена и ссылки из составных объектов. Счётчик ссылок. Идентификаторы объектов и их сравнение.
 1. Старшинство операций. Логические операции. Нулевой объект типа.
 1. Скалярные типы данных. /!\ Что ещё?
 1. Пространство имён объекта: поля и методы объекта. /* Функция `dir()`. Первый параметр метода. */
 1. Методы последовательностей. Использование последовательностей в качестве стека. /* `collections.deque` и очереди */
 1. (!) Алгоритмы поиска с возвратами (backtracking), реализация их с помощью рекурсии. Замещение рекурсии стеком контекстов.
 1. Строковые методы. Байтовые массивы.
 1. (!) Z-функция, π-функция и поиск подстроки
 1. Исключения как средство управления потоком вычислений
 1. (!) Задача хеширования. Открытое и закрытое хеширование. Требования к функции расстановки.
 1. Хешируемые объекты Python. Словари. Методы словарей. /* Хешируемые (константные) варианты множеств и т. п. */
 1. (!) Моделирование многомерных массивов. Модуль `array`. /* Ссылка на `numpy` */
 1. Множества и операции с ними. Циклические конструкторы различных объектов.
 1. Позиционные и именованные параметры функции, значение по умолчанию. Упаковка и распаковка параметров функции.
 1. Функции с произвольным количеством и именами параметров. Словари-пространства глобальных и локальных имён.
 1. (!) Двоичные (бинарные) деревья. Обход дерева с использованием стека, очереди и рекурсии.
 1. (!) Деревья поиска (сравнений), алгоритмы поиска, вставки и удаления элементов.
 1. Генераторы: выражения-генераторы, повторно входимые функции (функции-генераторы). Работа цикла с итерируемым объектом.
 1. Спецметоды. Реализация операций над объектами путём задания спецметодов.
=== Дополнительные главы ===
/!\ TODO: что ещё должно/может быть: выбрать нужное и подсунуть в нужное место
 1. `eval() / exec()`
 1. (!) Куча
 1. (!) Замыкание транзитивного бинарного отношения.
 1. Сериализация и бинарные данные
 1. Элементы функционального программирования.
 1. Объектное планирование в разработке программ. ООП.
 1. Наследование и полиморфизм
 1. Полезные модули
 !. Внутреннее устройство исполнителя: байт-код, стек-машина, словари имён и т. п.
 1. Ещё, см., например [[Lectures/PythonIntro|курс для Московской Биржи]]
== Практикум ==
/!\ '''TODO''' Видимо, стоит темы практикума прямо в лекциях задачать
 1. Интерпретатор командной строки. Использование Python в качестве калькулятора.
 1. Неформальное введение в Python. Работа со справочным материалом.

…

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