Алгоритмы и структуры данных
Курс будет доступен с 15 февраля.
Содержание курса
Тема 1.1. Программирование структур. Способы представления структур данных. Массивы. Списки. Множества. Стеки. Очереди. Классы памяти и организация программ. Локализация объектов. Глобальные объекты. Динамическая память. Внешние объекты. Деревья. Определение дерева. Корень, узлы. Trie-деревья. Прохождение деревьев.
Тема 1.2. Алгоритмы сортировки. Внутренние сортировки. Сортировка в массивах. Обобщение известных методов сортировки вставками, обменом, выбором. Сортировка элементов массива методом подсчета. Анализ алгоритмов сортировок массивов. Быстрая сортировка. Бинарная пирамидальная сортировка. Анализ эффективности алгоритмов. Внешние сортировки. Простое слияние. Естественное слияние. Улучшенные методы сортировки: многофазная и каскадная сортировки.
Быстрый поиск: бинарный и последовательный поиски в массивах. Дихотомия.
Тема 1.3. Графы. Задачи поиска. Графы. Понятие графа. Представление графа в памяти компьютера. Поиск в графе. Поиск в ширину. Поиск в глубину. Деревья. Нахождение каркаса минимального веса. Задача Прима-Краскала. Поиск кратчайшего пути на графе. Алгоритм Дейкстры. Методы поиска на графах. Определение остовных деревьев.
Раздел 2. Алгоритмы обработки данных
Тема 2.1. Перебор с возвратом. Общая схема. Пример задачи о расстановке ферзей. Динамическое программирование. Примеры задач (треугольник, степень числа). Метод ветвей и границ.
Метод решета.
Тема 2.2. Важные алгоритмы. Жадные алгоритмы. В-деревья. Хеширование. Теория сложности алгоритмов: NP-полные и NP-трудные задачи.
Результаты освоения курса
Выпускник знает:
способы программирования нелинейных структур данных и их представление в памяти компьютера;
постановку и алгоритмы задач поиска и сортировки в массивах, поиска на графах (Прима-Краскала, Дейкстры и т.д.);
теоретические основы и приемы программирования перебора с возвратом;
Умеет:
при решении конкретной задачи профессионально грамотно сформулировать задачу программирования, составить и оценить алгоритм решения, реализовать его в данной языковой среде, выполнить необходимое тестирование или верификацию построенной программы
Владеет и (или) имеет опыт деятельности:
навыками: практического программирования конкретных задач из различных предметных областей в определенной языковой среде
Содержание курса
Тема 1.1. Программирование структур. Способы представления структур данных. Массивы. Списки. Множества. Стеки. Очереди. Классы памяти и организация программ. Локализация объектов. Глобальные объекты. Динамическая память. Внешние объекты. Деревья. Определение дерева. Корень, узлы. Trie-деревья. Прохождение деревьев.
Тема 1.2. Алгоритмы сортировки. Внутренние сортировки. Сортировка в массивах. Обобщение известных методов сортировки вставками, обменом, выбором. Сортировка элементов массива методом подсчета. Анализ алгоритмов сортировок массивов. Быстрая сортировка. Бинарная пирамидальная сортировка. Анализ эффективности алгоритмов. Внешние сортировки. Простое слияние. Естественное слияние. Улучшенные методы сортировки: многофазная и каскадная сортировки.
Быстрый поиск: бинарный и последовательный поиски в массивах. Дихотомия.
Тема 1.3. Графы. Задачи поиска. Графы. Понятие графа. Представление графа в памяти компьютера. Поиск в графе. Поиск в ширину. Поиск в глубину. Деревья. Нахождение каркаса минимального веса. Задача Прима-Краскала. Поиск кратчайшего пути на графе. Алгоритм Дейкстры. Методы поиска на графах. Определение остовных деревьев.
Раздел 2. Алгоритмы обработки данных
Тема 2.1. Перебор с возвратом. Общая схема. Пример задачи о расстановке ферзей. Динамическое программирование. Примеры задач (треугольник, степень числа). Метод ветвей и границ.
Метод решета.
Тема 2.2. Важные алгоритмы. Жадные алгоритмы. В-деревья. Хеширование. Теория сложности алгоритмов: NP-полные и NP-трудные задачи.
Результаты освоения курса
Выпускник знает:
способы программирования нелинейных структур данных и их представление в памяти компьютера;
постановку и алгоритмы задач поиска и сортировки в массивах, поиска на графах (Прима-Краскала, Дейкстры и т.д.);
теоретические основы и приемы программирования перебора с возвратом;
Умеет:
при решении конкретной задачи профессионально грамотно сформулировать задачу программирования, составить и оценить алгоритм решения, реализовать его в данной языковой среде, выполнить необходимое тестирование или верификацию построенной программы
Владеет и (или) имеет опыт деятельности:
навыками: практического программирования конкретных задач из различных предметных областей в определенной языковой среде