Список экзаменационных вопросов

I семестр

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

II семестр

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