Вопросы для подготовки к дифференцированному зачёту

Вопросы для подготовки к дифференцированному зачёту

Теория алгоритмов

Группы: 503с.

Перестановки. Инверсии. Инверсионный алгоритм перебора перестановок Перестановки. Инверсии. Алгоритм Дейкстры генерации перестановок (по алфавиту).  Перестановки. Инверсии. Алгоритмы Кнута генерации перестановок. Перестановки. Инверсии. Рекурсивный алгоритм перебора перестановок Прямой и бинарный поиск в массиве. Анализ и сравнение эффективности. Алгоритмы поиска подстроки в строке: прямой и Бойера-Мура. Сравнительный анализ. Общая постановка задачи сортировки. Параметры оценки эффективности алгоритмов сортировки. Наилучшие и наихудшие оценки их эффективности Методы сортировки вставками: простыми, бинарными, метод Шелла. Оценки эффективности. Методы сортировки обменом. «Пузырек» и «Шейкер» сортировка. Быстрая сортировка. Сортировка выбором: простая и пирамидальная. Сравнительный анализ эффективности методов сортировки Методы сортировки слиянием. Методы сортировки файлов. Рекурсия как общий метод сведения задачи к самой  себе.  Примеры рекурсивных формул,  данных,  алгоритмов. Правила задания рекурсии: рекурсивный переход, условия выхода. Сложность вычислительных алгоритмов. Методы оценки сложности. Классификация алгоритмов по сложности. Метод динамического программирования на примере решения одной из задач. Разновидности списков: статические, динамические, одно/двусвязные, циклические, упорядоченные, иерархические. Операции над списками. Алгоритмы поиска и включения для списков, анализ их эффективности. Классические модели динамических структур данных: стек, очередь, дек. Основные операции, способы реализации. Примеры применения. Абстрактные типы данных. Куча. Операции над кучей. Реализация на массиве. Очередь с приоритетами Алгоритм перевода выражения из инфиксной формы в постфиксную. Вычисление на стеке. Граф как форма представления отношения. Типы графов. Смежность и инцидентность. Пути и маршруты Представление графов в ЭВМ. Матрицы смежности, инцидентности. Динамическая структура со списками дуг. Табличное представление. Сравнение различных способов представления Поиск пути по графу. Алгоритм транзитивного замыкания, его эффективность. Топологическая сортировка. Реализация с помощью иерархических списков. Топологическая сортировка. Реализация с помощью матрицы смежности. Топологическая сортировка. Реализация методом поиска в глубину. Алгоритм Дейкстры поиска минимального пути от одного источника. Поиск всех минимальных путей в графе. Алгоритм Флойда. Дерево как частный вид ациклического графа. Основные определения. Классификация обходов деревьев. Инфиксный, префиксный и постфиксный порядки обхода деревьев. Рекурсивная реализация. Обход дерева в ширину. Реализация с помощью очереди. Классические задачи на деревьях: обработка арифметических выражений, связь с обходом деревьев. Левое/правое скобочное представление деревьев Представление дерева списком прямых предков Деревья двоичного поиска: назначение, представление, алгоритмы вставки и поиска элементов, оценки их эффективности. Бинарный поиск по массиву и дереву. Условие осуществимости. Сортировка включением в дерево бинарного поиска. Сбалансированные деревья поиска. Алгоритм включения в сбалансированное дерево двоичного поиска. Обходы графа. Обход всех вершин графа методом поиска в глубину.  Каркас графа (остовное дерево). Построение каркаса методом поиска в глубину. Помеченные графы и их каркасы. Задача построения минимального каркаса. Алгоритм Краскала Помеченные графы и их каркасы. Задача построения минимального каркаса. Алгоритм Прима. Двусвязность. Алгоритм поиска в графе двусвязных компонент и точек сочленения. Классические переборные задачи. Коммивояжер, рюкзак, устойчивые бракосочетания. Способы их решения (обзорно). Классические переборные задачи. Задача коммивояжера. Алгоритмы с возвратом — обход шахматной доски конем. Алгоритмы с возвратом — задача о ферзях. Нахождение оптимальной выборки. Задача о рюкзаке. Задача об устойчивых браках. Задача о раскраске графа (раскраска вершин). Примеры эвристического и переборного алгоритмов решения. Примеры задач, сводимых к раскраске. Задачи о лабиринтах. Сведение их к модельным задачам на графах. Эйлеров граф. Способ определения эйлерова цикла. Задачи, сводимые к эйлеровым циклам. Гамильтоновы циклы. Поиск всех гамильтоновых циклов в графе. Задачи, сводимые к гамильтоновым циклам.