Алгоритмы и алгоритмические языки

Экзамен: 1 семестр

  1. Понятие алгоритма, его основные свойства.
  2. Понятия Вычислительного процесса и исполнителя. Их взаимосвязь с понятием алгоритма.
  3. Алгоритм и вычислительный процесс как конструктивные объекты и их основные свойства.
  4. Понятия потенциальной осуществимости алгоритма и потенциальной разрешимости проблем (на примерах). Представление о сложности алгоритма.
  5. Представление о данных и действиях в алгоритме. Понятие применимости алгоритма.
  6. Основные понятия теории алгоритмов: область применимости, вычислимая функция, перечислимое множество, разрешимое множество. Понятие конструктивного объекта.
  7. Понятие алгоритмической системы и ее основные параметры.
  8. Машины Тьюринга как уточнение понятия алгоритма: определение, примеры, композиция МТ, сложность алгоритмов. Тезис Тьюринга.
  9. Нормальные алгоритмы Маркова, как уточнение понятия алгоритма: определение, примеры, композиция НАМ, сложность алгоритмов. Тезис Маркова.
  10. Построение алгоритмов из алгоритмов: основные правила композиции и их свойства; формулировка основной теоремы.
  11. Существование универсальных вычислителей: на примере универсальной машины Тьюринга.
  12. Понятие Алгоритмической проблемы и представление об алгоритмической разрешимости; доказательство существования алгоритмически неразрешимых проблем.
  13. Взаимосвязь алгоритмически равносильных Алгоритмических систем; зависимость разрешимости алгоритмической проблемы от алгоритмической системы.
  14. Представление о языке программирования. Понятие синтаксиса и способы его описания. Представление о семантике.
  15. Концепция данных в языке Pascal.
  16. Синтаксис и семантика Выражения в языке Pascal.
  17. Оператор присваивания и составной оператор.
  18. Операторы выбора.
  19. Операторы цикла.
  20. Тип INTEGER: основные свойства и операции.
  21. Тип REAL: основные свойства и операции.
  22. Тип BOOLEAN: основные свойства и операции.
  23. Тип CHAR: основные свойства и операции.
  24. Перечислимый и ограниченный типы данных: основные свойства и операции.
  25. Регулярный типы данных: основные свойства и операции.
  26. Тип множество и комбинированный типы данных: основные свойства и операции.
  27. Понятие процедуры и ее назначение в языках программирования. Синтаксис и семантика определения процедуры в языке Pascal.
  28. Понятие процедуры и ее назначение в языках программирования. Синтаксис и семантика оператора процедуры, способы передачи параметров в процедуру в языке Pascal.
  29. Понятие функции и ее назначение в языках программирования. Синтаксис и семантика определения функции в языке Pascal. Понятие побочного эффекта.
  30. Понятие функции и ее назначение в языках программирования. Синтаксис и семантика оператора функции. Способы передачи параметров функции.
  31. Представление о рекурсии, применение рекурсии в определении процедуры. Применение рекурсии в алгоритмах с возвратом (на примере задачи о ходе коня).
  32. Представление о рекурсии. Косвенная рекурсия. Взаимосвязь итерации и рекурсии.
  33. Тип файл. Операции над файлами. Операции ввода/вывода в Pascal▓е.
  34. Концепция имени в языке программирования Pascal.
  35. Основные этапы разработки программ: на примере разработки программы поиска пути в лабиринте (задача об Ариадне и Тезее).
  36. Ссылочный тип данных. Основные свойства и операции.
  37. Абстрактные Структуры Данных: дерево, бинарное дерево, сбалансированное дерево, граф - определение, способы представления, операции над ними.
  38. Абстрактные Структуры Данных: Строка, Стек, Очередь, Таблица - определения, способы представления, операции.
  39. Понятие Структуры Данных Хранения (СДХ). Проблема отображения АСД на СДХ. Представление АСД-строка, АСД-дерево, АСД-таблица в векторной памяти.
  40. Проблема отображение АСД на СДХ. Представление АСД-строка и АСД-стек с помощью списковых структур.
  41. Проблема отображения АСД на СДХ. Представление АСД-граф с помощью списковых структур.
  42. Последовательные неупорядоченные таблицы (векторное представление) и операции над ними. Реализация и оценка сложности операций вставки и поиска.
  43. Последовательные неупорядоченные таблицы (списковое представление) и операции над ними. Реализация и оценка сложности операций вставки и поиска.
  44. Таблицы как деревья сравнений (векторное представление) и операции над ними. Реализация и оценка сложности операций вставки и поиска.
  45. Таблицы как деревья сравнений (списковое представление) и операции над ними. Оценка сложности операций вставки и поиска. Теорема Хиббарда о средней длине поиска. Случай сбалансированного дерева: понятия балансировки и разбалансировки деревьев.
  46. Таблицы как деревья сравнений (списковое представление) и операции над ними. Реализация и оценка сложности операций вставки и поиска. Представление о балансировке и разбалансировке деревьев.
  47. Таблицы с прямым доступом. Применение функции перемешивания при работе с таблицами. Методы разрешения коллизий - функции повторного перемешивания. Требования к функции перемешивания. Оценка числа сравнений при поиске и включении.
  48. Таблицы с прямым доступом. Применение функции перемешивания при работе с таблицами. Методы разрешения коллизий - метод сцепления. Требования к функции перемешивания. Оценка числа сравнений при поиске и включении.
  49. Сортировка - постановка задачи. Характеристики методов сортировки. Сортировки линейным выбором, линейным выбором с обменом: метод, реализация и оценка сложности. 
  50. Сортировки обменом - стандартный обмен, просеивание: метод, реализация и оценка сложности.
  51. Сортировки обменом - сортировка Шелла: метод, реализация и оценка сложности.
  52. Использование структуры в сортировке: турнирная не минимальная по памяти сортировка - метод, реализация и оценка сложности.
  53. Использование структуры в сортировке: турнирная, минимальная по памяти сортировка Флойда - метод, реализация и оценка сложности.
  54. Быстрая сортировка: метод, реализация и оценка сложности.
  55. Сортировка методом больших степеней: метод и оценка сложности. Сортировка методом слияния: метод, реализация и оценка сложности.
 

[Назад в кладовку] - [На первую страницу]