Вопросы к экзамену по курсу «методы программирования» (годовой курс)

1 часть: вопросы первого курса

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

2 часть: вопросы второго курса

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