Различия между версиями 37 и 38
Версия 37 от 2015-05-15 12:30:57
Размер: 15286
Редактор: FrBrGeorge
Комментарий:
Версия 38 от 2015-05-15 12:34:23
Размер: 15387
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 122: Строка 122:
Ещё:
Строка 130: Строка 129:
 1. Ещё, см., например [[Lectures/PythonIntro|курс для Московской Биржи]]

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

Аннотация

/!\ TODO

Концепция

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

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

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

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

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

Лекции

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

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

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

  1. Интуитивное понятие алгоритма: преобразование данных исполнителем на основании команд. Свойства алгоритмов.
  2. Программируемый калькулятор: данные, команды, последовательное, условное и циклическое выполнение.
  3. Алгоритм как преобразование слов из заданного алфавита. Нормальные алгоритмы Маркова.
  4. Машина Тьюринга. Тезис Тьюринга и принцип нормализации, их обоснование.
  5. Алгоритмически неразрешимые проблемы.
  6. Неразрешимость проблем самоприменимости, останова и эквивалентности алгоритмов.
  7. Характеристика алгоритмических языков. Понятия исполнителя и трансляции. Компилируемые и интерпретируемые языки.
  8. Алфавит, синтаксис и семантика алгоритмического языка. Описание синтаксиса языка с помощью металингвистических формул (БНФ) и синтаксических диаграмм.
  9. /!\

  10. /!\

Обзор языка программирования и исполнителя Pyton

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

Основы ЯП Python

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

  5. Функции: задание и оператор вызова. Контекст выполнения, глобальное и локальное пространства имён, их перекрытие.
  6. Оформление кода. Строки документации, комментарии, соглашение об именах. Модернизация языка Python сообществом.
  7. (!) Понятие вычислительной сложности алгоритмов в худшем случае и в среднем. Поиск и бинарный поиск в упорядоченных последовательностях.

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

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

  10. Конструирование пространства имён: модули и классы. Экземпляры классов.
  11. Интерактивный и файловый ввод-вывод. Параметры командной строки.
  12. (!) Рекурсия. Достоинства, недостатки, критерий применения в Python.

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

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

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

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

  6. Строковые методы. Байтовые массивы.
  7. (!) Z-функция, π-функция и поиск подстроки

  8. Исключения как средство управления потоком вычислений
  9. (!) Задача хеширования. Открытое и закрытое хеширование. Требования к функции расстановки.

  10. Хешируемые объекты Python. Словари. Методы словарей.

  11. (!) Моделирование многомерных массивов. Модуль array.

  12. Множества и операции с ними. Циклические конструкторы различных объектов.
  13. Позиционные и именованные параметры функции, значение по умолчанию. Упаковка и распаковка параметров функции.
  14. Функции с произвольным количеством и именами параметров. Словари-пространства глобальных и локальных имён.
  15. (!) Двоичные (бинарные) деревья. Обход дерева с использованием стека, очереди и рекурсии.

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

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

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

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

  1. eval() / exec()

  2. (!) Куча

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

  4. Сериализация и бинарные данные
  5. Элементы функционального программирования.
  6. Объектное планирование в разработке программ. ООП.
  7. Наследование и полиморфизм
  8. Ещё, см., например курс для Московской Биржи

Python/PythonBaseCourse (последним исправлял пользователь FrBrGeorge 2015-07-21 15:51:23)