Алгоритмы программирования и структуры данных

1. Оценка времени работы алгоритмов
2. Алгоритмы сортировки, основанные на сравнении (сортировка слиянием, быстрая сортировка, нижняя оценка на время работы алгоритмов сортировки)
3. Алгоритмы сортировки с линейным временем выполнения (сортировка подсчетом, цифровая сортировка, карманная сортировка)
4. Элементарные структуры данных (стек, очередь, связанные списки)
5. Алгоритмы, основанные на двоичной куче (сортировка кучей, очередь с приоритетами)
6. Введение в алгоритмы поиска (двоичный поиск в отсортированном массиве, двоичное дерево поиска)
7. Сбалансированные деревья поиска (обзор сбалансированных деревьев, АВЛ-дерево, Splay-дерево)
8. Хеширование (хеш-таблицы с закрытой и открытой адресацией)
9. Введение в поиск подстрок (простейший алгоритм поиска подстрок, алгоритм Рабина-Карпа)
10. Поиск подстрок (алгоритм Кнута-Морриса-Пратта, Z-функция, алгоритм Бойера-Мура)

Каждая тема предполагает изучение в течение одной недели. На каждой неделе выдаются задания по программированию, предполагающие самостоятельную реализацию изучаемых в курсе алгоритмов и структур данных.

В курсе имеется два типа дедлайна (предельного срока выполнения оценивающих мероприятий):

• мягкий дедлайн, при котором необходимо выполнить все оценивающие мероприятия текущей недели до ее завершения;
• жесткий дедлайн, при котором на выполнение оценивающих мероприятий после мягкого дедлайна дополнительно выделяется еще две недели, по окончании которых доступ к соответствующим мероприятиям закрывается.

Результаты обучения

• Умение анализировать и реализовывать базовые алгоритмы программирования и структуры данных
• Навыки проектирования и разработки средств реализации прикладных информационных технологий
• Навыки разработки алгоритмов для проведения экспериментальных исследований в области информатики

Формат

В состав курса входят видеолекции, опросы по материалам лекций и практические задания по программированию, предполагающие самостоятельную реализацию изучаемых в курсе алгоритмов и структур данных на одном из предложенных современных языков программирования. Курс рассчитан на десять недель. Средняя недельная нагрузка на обучающегося - 14 часов. Общая трудоемкость курса составляет четыре зачетных единицы.

Требования

Для успешного освоения курса необходимы знание основ дискретной математики, умение писать программы среднего размера на объектно-ориентированном языке программирования.

Сертификат

• Сертификат выдается при достижении не менее 60% от максимального количества баллов по курсу.