DEV-PY111. Базовые алгоритмы и структуры данных на языке Python
Длительность дисциплины: 48 ак.ч.
Аннотация
Целью реализации модуля «DEV-PY111. Базовые алгоритмы и структуры данных на языке Python» является освоение слушателями базовых алгоритмов решения вычислительных задач, а также приобретение практических навыков эффективного применения этих алгоритмов при работе с различными структурами данных на языке Python.
Знания и умения, полученные в результате изучения
В результате освоения программы обучающийся должен уметь:
• грамотно формировать структуру текста программы;
• выполнять декомпозицию задачи;
• корректно и эффективно использовать алгоритмы и структуры на языке Python;
• выполнять декомпозицию сложных задач;
• решать практические задачи по корректному использованию языковых и программных средств, позволяющих реализовать простые консольные программы.
• создавать и обрабатывать итерируемые объекты;
• создавать функции генераторов;
В результате освоения программы обучающийся должен знать:
• базовые понятия алгоритмизации и процедурного программирования;
• основные алгоритмы работы с различными структурами данных;
• О-нотацию и правила вычисления;
• итерационные алгоритмы;
• рекурсию и рекурсивные алгоритмы;
• основы динамического программирования;
• алгоритмы работы с графами и деревьями;
• алгоритмы сортировки.
• принципы работы с итерируемыми объектами;
• способы создания выражений и функций генераторов;
В результате освоения программы обучающийся должен приобрести практический опыт:
• написания эффективных консольных программ на базе языка программирования 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. Промежуточная аттестация
Практические занятия Зачет