Основы алгоритмизации и алгоязыки

Кафедра информатики и автоматизации научных исследований

Специальность: Прикладная информатика

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

Содержание

1. УПРАВЛЯЮЩИЕ СТРУКТУРЫ. Понятие программы и алгоритма. Свойства алгоритмов. Блок – схема. Управляющие структуры: цикл, ветвление, цепочка. Комбинация базовых структур. Свойства базовых структур. Свойства цепочки, альтернативы, цикла. Верификация программ. Правила верификации. Антецедент и консеквент инструкции. Типы данных.
2. СПИСКИ. Линейные списки. Стек, очередь, дек. Структурные схемы. Представление линейных списков в памяти. Связанное распределение и его применение к стекам, очередям. Алгоритм топологической сортировки. Циклические списки. Алгоритмы сложения и умножения многочленов. Списки с двумя связями. Массивы и ортогональные списки.
3. ДЕРЕВЬЯ. Представление деревьев. Алгоритм перехода от дерева общего вида и бинарному. Прошитое дерево. Прохождение или обход деревьев. Алгоритмы прохождения деревьев. Приложение методов обхода к задачам преобразования алгебраических формул. Высота дерева. Подобие и эквивалентность деревьев.
4. ГРАФЫ. Представление графов. Остовные деревья. Алгоритмы нахождения минимального дерева остова. Поиск в глубину на графе. Алгоритм транзитивного замыкания. Алгоритмы поиска расстояний между вершинами графа. Алгоритм поиска критического пути. Алгоритм раскраски графа.
5. РЕКУРСИЯ. Свойства рекурсивных алгоритмов. Примеры рекурсивных алгоритмов: Ханойская башня, поиск экстремума функции.
6. ХЕШИРОВАНИЕ. Понятие хеширования. Основные приемы хеширования. Построение хеш-функции. Коллизии. Алгоритмы разрешения коллизий.
7. УПРАВЛЕНИЕ ТАБЛИЦАМИ. Операции поиска и включения. Дихотомический поиск. Двоичные деревья поиска.
8. СОРТИРОВКА. Внутренняя сортировка. Внешняя сортировка. Частичная сортировка. Алгоритмы сортировки.

Отчетность

Семестр 1: Зач
Семестр 2: Экз