Алгоритмы и алгоритмические языки
Экзамен: 1 семестр
- Понятие алгоритма, его
основные свойства.
- Понятия Вычислительного
процесса и исполнителя. Их взаимосвязь
с понятием алгоритма.
- Алгоритм и вычислительный
процесс как конструктивные объекты
и их основные свойства.
- Понятия потенциальной
осуществимости алгоритма и потенциальной разрешимости
проблем (на примерах). Представление о сложности
алгоритма.
- Представление о данных и
действиях в алгоритме. Понятие
применимости алгоритма.
- Основные понятия теории
алгоритмов: область применимости, вычислимая
функция, перечислимое множество, разрешимое множество. Понятие
конструктивного объекта.
- Понятие алгоритмической
системы и ее основные параметры.
- Машины Тьюринга как
уточнение понятия алгоритма: определение, примеры,
композиция МТ, сложность алгоритмов.
Тезис Тьюринга.
- Нормальные алгоритмы
Маркова, как уточнение понятия алгоритма: определение,
примеры, композиция НАМ, сложность алгоритмов. Тезис Маркова.
- Построение алгоритмов из
алгоритмов: основные правила композиции и их свойства;
формулировка основной теоремы.
- Существование
универсальных вычислителей: на примере
универсальной машины
Тьюринга.
- Понятие Алгоритмической
проблемы и представление об алгоритмической разрешимости;
доказательство существования алгоритмически неразрешимых
проблем.
- Взаимосвязь алгоритмически
равносильных Алгоритмических систем; зависимость
разрешимости алгоритмической проблемы
от алгоритмической системы.
- Представление о языке
программирования. Понятие синтаксиса и способы его
описания. Представление о семантике.
- Концепция данных в языке
Pascal.
- Синтаксис и семантика
Выражения в языке Pascal.
- Оператор присваивания и
составной оператор.
- Операторы выбора.
- Операторы цикла.
- Тип INTEGER: основные свойства
и операции.
- Тип REAL: основные свойства и
операции.
- Тип BOOLEAN: основные свойства
и операции.
- Тип CHAR: основные свойства и
операции.
- Перечислимый и
ограниченный типы данных: основные свойства и операции.
- Регулярный типы данных:
основные свойства и операции.
- Тип множество и
комбинированный типы данных: основные
свойства и операции.
- Понятие процедуры и ее
назначение в языках программирования. Синтаксис и
семантика определения процедуры в языке Pascal.
- Понятие процедуры и ее
назначение в языках программирования. Синтаксис и
семантика оператора процедуры, способы передачи
параметров в процедуру в языке Pascal.
- Понятие функции и ее
назначение в языках программирования. Синтаксис и
семантика определения функции в языке Pascal. Понятие
побочного эффекта.
- Понятие функции и ее
назначение в языках программирования. Синтаксис и
семантика оператора функции. Способы передачи параметров
функции.
- Представление о рекурсии,
применение рекурсии в определении процедуры.
Применение рекурсии в алгоритмах с возвратом (на примере задачи о
ходе коня).
- Представление о рекурсии.
Косвенная рекурсия. Взаимосвязь итерации и
рекурсии.
- Тип файл. Операции над
файлами. Операции ввода/вывода в Pascal▓е.
- Концепция имени в языке
программирования Pascal.
- Основные этапы разработки
программ: на примере разработки программы поиска
пути в лабиринте (задача об Ариадне и Тезее).
- Ссылочный тип данных.
Основные свойства и операции.
- Абстрактные Структуры
Данных: дерево, бинарное дерево, сбалансированное
дерево, граф - определение, способы
представления, операции над ними.
- Абстрактные Структуры
Данных: Строка, Стек, Очередь, Таблица - определения,
способы представления, операции.
- Понятие Структуры Данных
Хранения (СДХ). Проблема отображения АСД на
СДХ. Представление АСД-строка, АСД-дерево, АСД-таблица в
векторной памяти.
- Проблема отображение АСД на
СДХ. Представление АСД-строка и АСД-стек с помощью списковых
структур.
- Проблема отображения АСД на
СДХ. Представление АСД-граф с помощью списковых структур.
- Последовательные
неупорядоченные таблицы (векторное представление) и
операции над ними. Реализация и оценка сложности операций
вставки и поиска.
- Последовательные
неупорядоченные таблицы (списковое представление) и
операции над ними. Реализация и оценка сложности операций
вставки и поиска.
- Таблицы как деревья
сравнений (векторное представление) и операции над
ними. Реализация и оценка сложности операций вставки и
поиска.
- Таблицы как деревья
сравнений (списковое представление) и операции над
ними. Оценка сложности операций вставки и поиска.
Теорема Хиббарда о средней длине поиска. Случай
сбалансированного дерева: понятия балансировки и
разбалансировки деревьев.
- Таблицы как деревья
сравнений (списковое представление) и операции над
ними. Реализация и оценка сложности операций вставки и
поиска. Представление о балансировке и
разбалансировке деревьев.
- Таблицы с прямым доступом.
Применение функции перемешивания при
работе с таблицами. Методы разрешения коллизий - функции
повторного перемешивания. Требования к функции
перемешивания. Оценка числа сравнений при поиске и
включении.
- Таблицы с прямым доступом.
Применение функции перемешивания при
работе с таблицами. Методы разрешения коллизий - метод
сцепления. Требования к функции перемешивания.
Оценка числа сравнений при поиске и включении.
- Сортировка - постановка
задачи. Характеристики методов сортировки.
Сортировки линейным выбором, линейным
выбором с обменом: метод,
реализация и оценка сложности.
- Сортировки обменом -
стандартный обмен, просеивание: метод, реализация и оценка
сложности.
- Сортировки обменом -
сортировка Шелла: метод, реализация и оценка сложности.
- Использование структуры в
сортировке: турнирная не минимальная по памяти
сортировка - метод, реализация и оценка сложности.
- Использование структуры в
сортировке: турнирная, минимальная по памяти
сортировка Флойда - метод, реализация и оценка
сложности.
- Быстрая сортировка: метод,
реализация и оценка сложности.
- Сортировка методом больших
степеней: метод и оценка сложности. Сортировка
методом слияния: метод, реализация и оценка сложности.
[Назад в кладовку] - [На первую страницу]