Курс: Алгоритмы и структуры данных

Продолжительность курса: 40 ак. ч.

Описание курса:
Фундаментальный курс «прокачивает» базовые знания computer science. Дает понимание, как работает язык программирования и действуют применяемые в коде команды и решения. На примере языка С студенты смогут «пощупать» механизмы, которые лежат в основе современных фреймворков. Курс дает знания, отличающие программиста от «юзера», пишущего код.

Аудитория:
• Программисты
• Разработчики

Необходимая подготовка:
• Базовые знания computer science

Результат обучения:
После изучения слушатель будет уметь:
• Владеть основами программирования на языке C;
• Знать структуры данных и алгоритмы, которые лежат в основе их работы;
• Владеть общими подходами и полезными методиками для решения сложных задач;
• использовать инструменты оценки сложности решаемых задач;
• Создавать консольные программы на языке C в среде разработки QT;
• Создавать программы, используя собственные алгоритмы;
• Создавать собственные структуры данных: стеки, списки, деревья и др.;
• Оценивать производительность программ;
• Использовать «незащищенный» режим работы с памятью, основанный на указателях;
• Динамически выделять и освобождать память;
• Использовать рекурсию.

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

Модуль 1. Простые алгоритмы
• Введение в C. Структуры. Алгоритмы.

Модуль 2. Асимптотическая сложность алгоритма. Рекурсия
• Асимптотическая сложность алгоритма. Рекурсивный перебор. Ханойская башня.

Модуль 3. Поиск в массиве. Простые сортировки
• Поиск в одномерном массиве. Интерполяционный поиск. Сортировка массива.

Модуль 4. Динамическое программирование. Поиск возвратом
• Наибольшая общая подпоследовательность. Динамическое программирование. Поиск с возвратом. Задача о восьми ферзях

Модуль 5. Динамические структуры данных
• Стек, очередь. Создание стека с использованием массива. Динамические структуры данных.

Модуль 6. Деревья
• Двоичные деревья поиска. Хеш-функция. MD5. Хеш-таблицы.

Модуль 7. Графы. Алгоритмы на графах.
• Графы, обход графа в ширину и глубину. Волновой алгоритм. «Жадные алгоритмы».

Модуль 8. Сложные сортировки
• Сортировка Хоара (Quick sort). Пирамидальная сортировка (Heap sort) Сортировка слиянием (Merge sort). Сортировка подсчетом (CountingSort). Алгоритм со списком (pigeonhole sorting). Блочная сортировка.