Различия между версиями 25 и 26
Версия 25 от 2015-05-11 20:20:57
Размер: 14691
Редактор: FrBrGeorge
Комментарий:
Версия 26 от 2015-05-11 22:37:49
Размер: 14843
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 40: Строка 40:
|| Что преобразуем? || Данные || Атрибуция данных (произвольное обращение к определённым данным из программы)|| || Что преобразуем? || Данные || Референция данных (произвольное обращение к определённым данным из программы)||
Строка 42: Строка 42:
|| Что как преобразуем? || Управление || Изменение свойств исполнителя на основании свойств данных (управляемая данными атрибуция/команды/выбор команды)|| || Что как преобразуем? || Управление || Изменение свойств исполнителя на основании свойств данных (управляемая данными референция/команды/выбор команды)||
Строка 81: Строка 81:
 1. … <!> TODO
 1. … <!> TODO
 1. … <!>
 1. … <!>
Строка 84: Строка 84:
 1.#10 История Python. Интерпретатор командной строки.
 1. Неформальное введение в Python. Использование Python как калькулятора.
 1.#11 История Python. Интерпретатор командной строки. Использование Python в качестве калькулятора.
 1. Неформальное введение в Python. Работа со справочным материалом.
Строка 87: Строка 87:
 1.#12 Константы-конструкторы основных скалярных объектов. Операции над объектами. Интерпретация выражения: конструирование и удаление объектов.
===
Возможности ЯП Python ===
 1.#13 Константы-конструкторы основных скалярных объектов. Операции над объектами. Интерпретация выражения: конструирование и удаление объектов. Референция объекта с помощью идентификатора.
Строка 90: Строка 89:
 1. Ссылки на объекты: имена; ссылки из составных объектов. Счётчик ссылок. Идентификаторы объектов и их сравнение.
Строка 93: Строка 91:
 1. Функции: задание и оператор вызова. Контекст выполнения, глобальное и локальное пространства имён, их перекрытие.
=== Возможности ЯП Python ===
 1. Ссылки на объекты: имена; ссылки из составных объектов. Счётчик ссылок. Идентификаторы объектов и их сравнение.
Строка 94: Строка 95:
 1. Функции: задание и оператор вызова. Контекст выполнения, глобальное и локальное пространства имён, их перекрытие.

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

Аннотация

/!\ TODO

Концепция

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

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

  1. Введение в теорию алгоритмов. Алгоритмические языки.
    • Теоретическая база алгоритмизации и примеры реализующих её формализмов
  2. Обзор языка программирования и исполнителя Pyton
    • Одно занятие, посвящённое поверхностному знакомству с языком и интерпретатором командной строки
  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. Функции: задание и оператор вызова. Контекст выполнения, глобальное и локальное пространства имён, их перекрытие.

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

  1. Ссылки на объекты: имена; ссылки из составных объектов. Счётчик ссылок. Идентификаторы объектов и их сравнение.
  2. Старшинство операций. Логические операции. Нулевой объект типа.
  3. Оформление исходного кода: комментарии, строки документации, договорённости об именовании. Модернизация языка Python сообществом.
  4. Пространство имён объекта: поля и методы объекта.
  5. Методы последовательностей. Использование последовательностей в качестве стека.
  6. Цикл с итерируемым объектом. Циклические конструкторы объектов.
  7. Строковые методы. Конкатенация и разбиение строк.
  8. Модуль как контейнер имён. Использование модуля. Стандартные модули. Файл как модуль. Строки документации.
  9. Файловый ввод-вывод. Сериализация.
  10. Взаимодействие с ОС: потоки ввода-вывода, параметры командной строки, /!\

  11. Понятие вычислительной сложности алгоритмов в худшем случае и в среднем. Поиск и бинарный поиск в упорядоченных последовательностях.
  12. Рекурсия. Достоинства, недостатки, критерий применения в Python.
  13. Алгоритмы поиска с возвратами (backtracking), реализация их с помощью рекурсии. Замещение рекурсии стеком контекстов.
  14. Методы сортировки, оптимальные оценки числа сравнений и перемещений при сортировке.
  15. Задача хеширования. Открытое и закрытое хеширование. Требования к функции расстановки.
  16. Хешируемые объекты Python. Словари. Методы словарей.
  17. Множества, байтовые массивы. Константные (хешируемые) варианты. Операции над множествами.
  18. Позиционные и именованные параметры функции, значение по умолчанию. Упаковка и распаковка параметров функции.
  19. Функции с произвольным количеством и именами параметров. Словари-пространства глобальных и локальных имён.
  20. Генераторы: выражения-генераторы, повторно входимые функции (функции-генераторы). Работа цикла с итерируемым объектом.
  21. Класс как конструктор пространства имён. Экземпляр класса: динамические поля и поля класса. Методы. Вызов метода. Строки документации.
  22. Спецметоды. Реализация операций над объектами путём задания спецметодов.


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

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

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