14691
Комментарий:
|
14843
|
Удаления помечены так. | Добавления помечены так. |
Строка 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
- Познакомить с алгоритмами и структурами данных, используемыми при решении типовых задач
Курс состоит из пяти неравных по объёму тематических разделов:
- Введение в теорию алгоритмов. Алгоритмические языки.
- Теоретическая база алгоритмизации и примеры реализующих её формализмов
- Обзор языка программирования и исполнителя Pyton
- Одно занятие, посвящённое поверхностному знакомству с языком и интерпретатором командной строки
- Основы ЯП Python
- Базовый набор операторов и структур данных, необходимых для того, чтобы составлять и изучать алгоритмы
- Возможности ЯП Python
- Достаточно полное описание исполнителя и подмножества ЯП, достаточного для эффективного програмиорвания
- Алгоритмы и структуры данных.
- Классические алгоритмы и структуры данных, в них используемые
Темы последнего раздела идут не отдельно в конце семестра, а появляются после изучения подходящей конструкции ЯП или приёма программирования.
Лекции
примерный почасовой план План содержит несколько поясняющих комментариев, для их показа надо нажать «Комментарии» в начале или в конце страницы.
Введение в теорию алгоритмов. Алгоритмические языки
- Интуитивное понятие алгоритма: преобразование данных исполнителем на основании команд. Свойства алгоритмов.
- Программируемый калькулятор: данные, команды, последовательное, условное и циклическое выполнение.
- Алгоритм как преобразование слов из заданного алфавита. Нормальные алгоритмы Маркова.
- Машина Тьюринга. Тезис Тьюринга и принцип нормализации, их обоснование.
- Алгоритмически неразрешимые проблемы.
- Неразрешимость проблем самоприменимости, останова и эквивалентности алгоритмов.
- Характеристика алгоритмических языков. Понятия исполнителя и трансляции. Компилируемые и интерпретируемые языки.
- Алфавит, синтаксис и семантика алгоритмического языка. Описание синтаксиса языка с помощью металингвистических формул (БНФ) и синтаксических диаграмм.
…
…
Обзор языка программирования и исполнителя Pyton
- История Python. Интерпретатор командной строки. Использование Python в качестве калькулятора.
- Неформальное введение в Python. Работа со справочным материалом.
Основы ЯП Python
- Константы-конструкторы основных скалярных объектов. Операции над объектами. Интерпретация выражения: конструирование и удаление объектов. Референция объекта с помощью идентификатора.
- Основные типы последовательностей. Индексирование и секционирование. Множественный оператор именования, распаковка последовательностей.
- Условный оператор. Блок операторов. Вложенные операторы.
- Оператор цикла с условием. Каноническая схема цикла.
- Функции: задание и оператор вызова. Контекст выполнения, глобальное и локальное пространства имён, их перекрытие.
Возможности ЯП Python
- Ссылки на объекты: имена; ссылки из составных объектов. Счётчик ссылок. Идентификаторы объектов и их сравнение.
- Старшинство операций. Логические операции. Нулевой объект типа.
- Оформление исходного кода: комментарии, строки документации, договорённости об именовании. Модернизация языка Python сообществом.
- Пространство имён объекта: поля и методы объекта.
- Методы последовательностей. Использование последовательностей в качестве стека.
- Цикл с итерируемым объектом. Циклические конструкторы объектов.
- Строковые методы. Конкатенация и разбиение строк.
- Модуль как контейнер имён. Использование модуля. Стандартные модули. Файл как модуль. Строки документации.
- Файловый ввод-вывод. Сериализация.
Взаимодействие с ОС: потоки ввода-вывода, параметры командной строки, …
- Понятие вычислительной сложности алгоритмов в худшем случае и в среднем. Поиск и бинарный поиск в упорядоченных последовательностях.
- Рекурсия. Достоинства, недостатки, критерий применения в Python.
- Алгоритмы поиска с возвратами (backtracking), реализация их с помощью рекурсии. Замещение рекурсии стеком контекстов.
- Методы сортировки, оптимальные оценки числа сравнений и перемещений при сортировке.
- Задача хеширования. Открытое и закрытое хеширование. Требования к функции расстановки.
- Хешируемые объекты Python. Словари. Методы словарей.
- Множества, байтовые массивы. Константные (хешируемые) варианты. Операции над множествами.
- Позиционные и именованные параметры функции, значение по умолчанию. Упаковка и распаковка параметров функции.
- Функции с произвольным количеством и именами параметров. Словари-пространства глобальных и локальных имён.
- Генераторы: выражения-генераторы, повторно входимые функции (функции-генераторы). Работа цикла с итерируемым объектом.
- Класс как конструктор пространства имён. Экземпляр класса: динамические поля и поля класса. Методы. Вызов метода. Строки документации.
- Спецметоды. Реализация операций над объектами путём задания спецметодов.
TODO: что ещё должно быть: выбрать и подсунуть в нужное место Ещё:
- Моделирование списков. Однонаправленные, двунаправленные и циклические списки. Заглавное звено.
- Двоичные (бинарные) деревья. Обход дерева с использованием стека, очереди и рекурсии.
- Деревья поиска (сравнений), алгоритмы поиска, вставки и удаления элементов.
- Куча
- Замыкание транзитивного бинарного отношения.
- Моделирование многомерных массивов.
- Исключения как средство управления потоком вычислений