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

Курс знакомит слушателей с базовыми структурами данных и алгоритмами, знание которых необходимо для эффективного решения разнообразных задач программирования. Авторы курса занимаются поиском и подготовкой одаренных в области информатики и программирования студентов и школьников. Под их руководством студенческие команды многократно становились чемпионами России по программированию, чемпионами мира и Европы.

О курсе

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

Цель курса - получение базовых знаний об основных алгоритмах и структурах данных, используемых для хранения и поиска информации.В курсе используется система автоматического тестирования программ, обеспечивающая объективную оценку корректности выполнения заданий по программированию.

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

Прохождение курса «Алгоритмы программирования и структуры данных» позволит существенно повысить продуктивность и конкурентоспособность слушателей при разработке программного обеспечения.

Формат

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

Информационные ресурсы

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

1. Кормен T., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — М.: Вильямс, 2012.
2. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. — М. : Вильямс, 2007.
3. Онлайн-конспекты лекций по дискретной математике, алгоритмам и структурам данных, читаемых на кафедре компьютерных технологий Университета ИТМО.

Требования

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

• Java: версия 8 (ссылка для скачивания на сайте Oracle)
• C, C++: MinGW версии 5.1 (для Windows, для Linux можно использовать GCC аналогичной версии), а также Microsoft Visual Studio C++ 2013 (скачать Visual Studio Express можно здесь).
• C#: Microsoft Visual Studio C# 2013 (скачать Visual Studio Express можно здесь).
• Python: версия 3.5 (ссылка для скачивания на сайте python.org)
• Scala: версия 2.11 (ссылка для скачивания на сайте scala-lang.org)
• Kotlin: версия 1.0 (ссылки на инструкции по установке компилятора, плагинов в IntelliJ IDEA и в Eclipse).

Программа курса

В курсе рассматриваются следующие темы:

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

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

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

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

• Умение анализировать и реализовывать базовые алгоритмы программирования и структуры данных (РО-1);
• Навыки проектирования и разработки средств реализации прикладных информационных технологий (РО-2);
• Навыки разработки алгоритмов для проведения экспериментальных исследований в области информатики (РО-3).

Формируемые компетенции

• 09.03.02 Информационные системы и технологии
  1. Способность к проектированию базовых и прикладных информационных технологий (ПК-11)
  2. Способность разрабатывать средства реализации информационных технологий (алгоритмические) (ПК-12)
  3. Готовность участвовать в постановке и проведении экспериментальных исследований (ПК-23)