DEV-PY111. Базовые алгоритмы и структуры данных на языке Python

---

Курсы, обеспечивающие достаточный начальный уровень знаний

• DEV-PY100. Основы процедурного программирования на языке Python
• DEV-PY110. Основы разработки WEB приложений на языке Python
• DEV-PY200. Объектно-ориентированное программирование на языке Python

Тема 1. Введение в алгоритмы и структуры данных. О-нотация. Простые структуры данных
1.1    Введение в алгоритмы и структуры данных   
    Обзор курса.
    Введение в алгоритмы и структуры данных
1.2    О-нотация.    
    О большое, о малое, омега, константы.
    Правила вычисления, список сравнения (…O(logn) < O(n) < O(nlogn)…)
1.3    Простые структуры данных   
    Стек, очередь, очередь с приоритетами.
    Список, двунаправленный список.
    «Стоимость» операций на вышеперечисленных структурах с точки зрения О-нотации.
Практические занятия   
1.    Работа со стеком.
2.    Работа со списками
3.    Проверка корректности скобочной последовательности.

Тема 2. Создание и обработка итерируемых объектов
3.1    Итераторы   
    Обзор итерируемых объектов.
    Объект iterator и методы работы с ним.
3.2    Функциональные преобразования списков   
    Функциональные преобразования списков.
    Функции map, filter.
3.3    Выражения-генераторы   
    Выражения-генераторы списков/словарей/множеств (назначение, создание, использование)
3.4    Функции генераторы.    
    Расширенные возможности использования функций.
    Назначение, особенности написания и использования функций генераторов.
Практические занятия   
1.    Исследование свойств объекта iterator
2.    Создание функций генераторов

Тема 3. Итерационные алгоритмы. Рекурсия и рекурсивные алгоритмы.
3.1    Итерационные алгоритмы и применение   
    Итерационные алгоритмы и их применение.
    Линейный поиск.
    Бинарный поиск.
3.2    Рекурсия и рекурсивные алгоритмы   
    Рекурсия и рекурсивные алгоритмы.
    Проблемы рекурсии, подсчет вычислительной сложности.
Практические занятия   
1.    Вычисление факториала числа.
2.    Вычисление числа Фибоначчи.

Тема 4. Алгоритмы сортировки
4.1    Введение в алгоритмы сортировки   
    Задача алгоритмов сортировки, характеристики, свойства сортировок.
4.2    Основные алгоритмы сортировки   
    Сортировка пузырьком, слиянием, быстрая сортировка Хоара.
    Вычислительная сложность сортировок в лучшем, худшем, среднем случае.
    Используемая память.
    Сравнение и применение.
Практические занятия   
1.    Реализация сортировки пузырьком.
2.    Реализация сортировки слиянием.
3.    Реализация быстрой сортировки Хоара.

Тема 5. Динамическое программирование
5.1    Динамическое программирование   
    Основы динамического программирования.
    Классические задачи на последовательности, одномерную и двумерную динамику.
Практические занятия   
1.    Задача о возможных прыжках мальчика.
2.    Задача о платной лестнице.
3.    Задача о перемещении ракеты по двумерному полю.

Тема 6. Графы и деревья.
6.1    Графы и их свойства.   
    Связность, направленность, веса ребер.
    Способы представления графов, матрицы смежности и инцидентности, список ребер.
    Алгоритмы на графах: поиск в ширину и в глубину.
6.2    Деревья и их свойства   
    Алгоритмы на деревьях.
    Виды деревьев, применение, вычислительная сложность операций.
Практические занятия   
1.    Поиск кратчайшего пути
2.    Операции на деревьях

Тема 7. Промежуточная аттестация
Практические занятия    Зачет