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