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

В билетах будут вопросы как из первого, так и из второго семестра. Сначала каждому студенту будут предложены 15 простых задач по темам их обеих семестров (системы счисления, перестановки, деревья, графы). Для допуска к экзамену необходимо решить 10 любых задач из этого списка. Студент, решивший 10 задач, имеет право на оценку «удовлетворительно» автоматом. Студент, решивший все 15 задач, имеет право на оценку «хорошо» автоматом. Студент, решивший менее 10 задач, до экзамена не допускается.

I семестр

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

II семестр

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