Теория алгоритмов

2020-2021 учебный год

Практические занятия


Вопросы к экзамену

1. Интуитивное понятие алгоритм. Теорема К.Гёделя. Задачи теории алгоритмов. 
2. Характеристика алгоритма. Универсальные исполнители. 
3. Машина Тьюринга. Тезис Чёрча-Тьюринга. Строгое определение алгоритма. 
4. Пример программы для машины Тьюринга. 
5. Машина Поста. Пример программы. 
6. Нормальные алгорифмы Маркова. 
7. Вычислимые и невычислимые функции. 
8. Алгоритмически неразрешимые задачи. Примеры таких задач. 
9. Сложность вычислений. Временная и пространственная сложность алгортима. 
Примеры определения временной сложности. 
10. Асимптотическая сложность алгоритма. Виды асимптотической сложности. 
11. Определение асимптотической сложности алгоритмов поиска. 
12. Определение асимптотической сложности алгоритмов сортировки. 
13. Доказательство правильности программ. Методы доказательного 
программирования. Пример алгоритма Евклида. 
14. Примеры доказательства правильности программ с применением 
инварианта цикла. 
15. Доказательное программирование. Спецификации. Корректность 
и надежность программ.
16. Основы теории графов. Взвешенный граф. Матрица смежности. 
Весовая матрица. Задача коммивояжера.
17. Жадные алгоритмы. Задача Прима-Крускала. 
18. Алгоритм Дейкстры поиска кратчайшего маршрута на графе. 
19. Динамическое программирование. 
20. Поиск оптимального решения. 
21. Определение количества решений методом динамического программирования.
22. Основы теории структуры данных дерево. 
23. Деревья поиска. Обход дерева.
24. Вычисление арифметических выражений с помощью структуры дерево.
25. Моделирование структуры дерево с помощью связанных структур.
26. Моделирование структуры дерево на Паскале.
27. Структуры данных. Сравнение с реляционными таблицами. 
Массивы структур. Файлы структур. 
28. Целочисленная арифметика. Алгоритм нахождения простых чисел.
29. Алгоритмы работы с "длинными" числами.
30. Сортировка массива структур с помощью указателей.
31. Алгоритмы работы с динамическими массивами.
32. Алгоритмы работы со стеком и очередью.

Практические задания

Практические задания на "3"

  1. Доказать, что после выполнения следующей программы значения переменных a и b меняются местами: b:= a + b; a:= b - a; b:= b - a.
  2. Доказать или опровергнуть правильность программы для выбора максимального из трех значений, записанных в переменных a, b и c.
  3. Доказать, что алгоритм Евклида вычисляет наибольший общий делитель (НОД) двух натуральных чисел.
  4. Реализовать алгоритм быстрого возведения в степень, основанный на использовании операций возведения в квадрат и умножения. Найти инвариант цикла в данном алгоритме.
  5. В следующей задаче определить инвариант цикла. Двое играют в игру: перед ними лежат в ряд N + 1 камней, сначала N белых, и в конце цепочки - один черный. За один ход каждый может взять от 1 до 3 камней. Проигрывает тот, кто берет черный камень.
  6. Составьте программу, которая запрашивает ввод с клавиатуры матрицы смежности графа, сохраняет ее в двумерном массиве, выводит массив на экран и сохраняет его в текстовый файл 1.txt. Двумерный массив нужно вывести на экра в виде матрицы смежности с обозначением имен вершин графа. В текстовом файле каждое число должно быть записано в отдельной строке. Вторая часть программы тоже самое должна делать с весовой матрицей графа и записывать ее в текстовый файл 2.txt.
  7. Составьте программу, которая читает из файла 1.txt матрицу смежности графа, записывает ее в двумерный массив, а массив выводит на экран в виде матрицы смежности с обозначением имен вершин. В текстовом файле каждое число должно быть записано в отдельной строке. Вторая часть программы должна делать то же самое с весовой марице графа, которая хранится в файле 2.txt.
  8. Задача Прима-Крускала. Весовая матрица графа хранится в файле 2.txt. Прочитать ее и записать в двумерный массив, который вывести на экран в виде матрицы смежности с обозначением имен вершин. Решить для этой матрицы задачу Прима-Крускала.
  9. Напишите программу, в которой объявлена таблица в форме массива записей. Запись содержит три поля: автор - author, название - title, количество - count. Программа должна запрашивать ввод с клавиатуры данных, записывать их в массив и выводить на экран в виде таблицы с выравниванием по левому краю в первых двух столбцах и по правому краю - в третьем.
  10. В планарном текстовом редакторе, например Leafpad, создайте текстовый файл, в которым должны содержаться данные о книгах в отдельных строках для каждого поля записи. Запись содержит три поля: автор - author, название - title, количество - count. Программ должн читать данные из текстового файла, записывать их в массив и выводить на экран в виде таблицы с выравниванием по левому краю в первых двух столбцах и по правому краю - в третьем.
  11. Данные о книгах читаются из текстового файла и записываются в типизированный файл. Запись содержит три поля: автор - author, название - title, количество - count. Программ должн читать данные из текстового файла, записывать их в массив и выводить на экран в виде таблицы с выравниванием по левому краю в первых двух столбцах и по правому краю - в третьем.
  12. Вычислите временную сложность алгоритма T(n) для задачи: найти сумму первых трех элементов массива при n не меньше 3. Зависит ли сложность алгоритма от размера массива?
  13. Вычислите временную сложность алгоритма T(n) для задачи: найти сумму всех элементов массива.
  14. Вычислите временную сложность алгоритма T(n) для задачи: отсортировать все элементы массива по возрастанию методом выбора.
  15. Найти вычислительную сложность алгоритма решения следующей задачи методом линейного поиска. Дан массив, в котором элементы расположены в произвольном порядке. Найти в нем заданное значение x или сообщить, что его нет.
  16. Найти вычислительную сложность алгоритма решения следующей задачи методом двоичного поиска, или дихотомии. Дан массив, в котором элементы упорядочены по возрастанию. Найти в нем заданное значение x или сообщить, что его нет.
  17. Определите асимптотическую сложность алгоритма, который сортирует одномерный массив размера n методом "пузырька".
  18. Определите асимптотическую сложность алгоритма решения следующей задачи. Все значения исходного массива размером n находятся в интервале от 1 до некоторого значения MAX, выполнить сортировку этого массива методом подсчета.
  19. Решите задачу с помощью машины Тьюринга. На ленте записано число в двоичной системе счисления. Каретка находится где-то над числом. Требуется увеличить число на единицу.
  20. Запишите нормальный алгорифм Маркова для следующей задачи. Дана последовательность символов "муха", с помощю подстановок привести ее к последовательности "слон".
  21. Запишите нормальный алгорифм Маркова для следующей задачи. Удалить из строки, состоящей из букв a и b, первый символ. Например, строка abba должна быть преобразована в bba.

Практические задания на "4"

  1. *Составьте программы для машины Тьюринга, которые увеличивают и уменьшают на единицу число, записанное в десятичной системе счисления.
  2. *Составьте программу для машины Тьюринга, которая складывает два числа в двоичной системе, разделенные на ленте знаком “+”.
  3. *Составьте программы для машины Тьюринга, которые выполняют сложение и вычитание двух чисел в десятичной системе счисления.
  4. *Предложите программу для машины Тьюринга и начальное состояние ленты, при котором эта программа зацикливается.
  5. *Составьте программу для машины Тьюринга, которая уменьшает двоичное число на 1.
  6. *Напишите программу для машины Поста, которая увеличивает (уменьшает) число в единичной системе счисления на единицу. Каретка расположена слева от числа.
  7. *Напишите программу для машины Поста, которая складывает два числа в единичной системе счисления. Каретка расположена над пробелом, разделяющим эти числа на ленте.
  8. *Напишите нормальный алгорифм Маркова, который "сортирует" цифры двоичного числа так, чтобы сначала стояли все нули, а потом — все единицы.
  9. *Напишите нормальный алгорифм Маркова, который умножает двоичное число на 2, добавляя 0 в конец записи числа.
  10. *Составьте программу, которая читает данные о книгах из файла, выводит в таблицу, затем выводит только те записи, для которых количество книг не превышает заданного числа.
  11. *Алгоритм Дейкстры. Взять в качестве исходной весовой матрицы графа данные из файла 2.txt. Реализовать для нее нахождение минимального пути с помощью алгоритма Дейкстры.
  12. Оцените количество операций для алгоритма: поиска всех делителей числа.
    Опишите набор используемых элементарных операций. Определите асимптотическую сложность алгоритма.
  13. Оцените количество операций для алгоритма: нахождения минимального и максимального элементов массива.
    Опишите набор используемых элементарных операций. Определите асимптотическую сложность алгоритма.
  14. Оцените количество операций для алгоритма: определения количества положительных элементов массива.
    Опишите набор используемых элементарных операций. Определите асимптотическую сложность алгоритма.
  15. Оцените количество операций для алгоритма: проверки числа на простоту.
    Опишите набор используемых элементарных операций. Определите асимптотическую сложность алгоритма.
  16. *Предложите алгоритм, позволяющий найти и вывести на экран те символы, которые встречаются в строке более одного раза. Оцените его асимптотическую сложность.
  17. *Алфавит языка племени “тумба-юмба” содержит k символов. Предложите алгоритм построения всех возможных слов этого языка длиной n символов и оцените его асимптотическую сложность.
  18. *Определите предусловие и постусловие для алгоритмов а) нахождения суммы всех делителей числа; б) проверки числа на простоту.
  19. *Определите предусловие и постусловие для алгоритмов а) определения количества слов в символьной строке; б) двоичного поиска элемента в отсортированном массиве.
  20. *Определите предусловие и постусловие для алгоритмов а) перестановки элементов массива в обратном порядке; б) преобразования числа из символьной записи в значение целого типа.
  21. *Оцените сложность алгоритма быстрого возведения в степень при n = 2^m.

Практические задания на "5"

  1. **Определите асимптотическую сложность алгоритма, который сортирует одномерный массив размера n методом слияния, или Merge sort.
  2. **Определите асимптотическую сложность алгоритма, который сортирует одномерный массив размера n методом пирамидальной сортировки, или Heap sort.
  3. **Определите асимптотическую сложность алгоритма, который сортирует одномерный массив размера n методом быстрой сортировки, или Quick sort.
  4. **Алгоритм Флойда-Уоршелла. Взять в качестве исходной весовой матрицы графа данные из файла 2.txt. Реализовать для не нахождение минимальных путей с помощью алгоритма Флойда-Уоршелла.
  5. **Составьте программу, которая, прочитав из файла записи, содержащие сведения о книгах, сортирует их по имени автора и выводит на экран. Запись содержит три поля: автор - author, название - title, количество - count.
  6. ***Составьте программу, которая, прочитав из файла записи, содержащие сведения о книгах, сортирует их с помощью указателей по имени автора и выводит на экран. Запись содержит три поля: автор - author, название - title, количество - count.
  7. ***Постройте программу, которая работает с базой данных в виде типизированного файла. Ваша СУБД (система управления базой данных) должна иметь следующие возможности: а) просмотр записей;
    б) добавление записей;
    в) удаление записей;
    г) сортировка по одному из полей (через указатели).
  8. **В игре “ним” двое игроков по очереди берут камни из двух кучек. За один ход можно взять любое ненулевое количество камней, но только из одной кучки. Тот, кому не осталось камней, проигрывает. Как определить, кто выиграет при правильной игре? Какой инвариант обеспечивает выигрыш?