1. Написать программу для подсчета и сортировки слов в файле с помощью двоичного дерева.

​

2. Написать программу, моделирующую конечные автоматы, работающие с алфавитом {0, 1} и распознающие следующие языки:

   - {0, 10},

   - слова произвольной длины, но только те, которые начинаются с последовательности 10,

   - только слова длиной 3.

​

 3. Написать программу, моделирующую работу машины Тьюринга. Машина Тьюринга должна уметь выполнять следующие арифметические операции над натуральными числами, заданными в унарной системе исчисления:

   - сложение двух натуральных чисел,

   - вычитание из натурального числа двойки,

   - умножение целого числа на двойку,

   - деление целого числа на двойку.

​

Программа должна либо проводить все вычисления автоматически и выдавать окончательный ответ, либо дожидаться нажатия клавиши пользователем для выполнения очередного шага. На каждом шаге на экране должны отображаться состояние ленты, текущее положение головки МТ и внутреннее состояние МТ.

​

4. Написать программу для вычисления примитивно рекурсивных функций, используя базис Клини и операции примитивной рекурсии и суперпозиции. Программа должна уметь вычислять следующие функции:

  - SUM(x,y) = x + y,

  - MUL(x,y) = x*y,

  - EXP (x,y) = x в степени y,

  - TETR (x,y)  - операция тетрации,

  - FAC(x) = факториал x,

  - PRED(x) = x - 1, x >0, 0 в противном случае,

  - DIFF(x,y) = x - y, x > y, 0 в противном случае,

  - ABS (x,y) = |x-y|,

  - sg(x) = 1, x > 0, 0 в противном случае,

  - anti_sg(x) = 0, x >0, 1 в противном случае,

  - REM(x,y) - остаток от деления x на y,

  - MOD(x,y) - целая часть при делении x на y.

​

5. Известно, что среднее количество случаев, когда при поиске максимального элемента в массиве из N элементов попадается новый элемент, больший, чем текущий максимальный, асимптотически равно ln(N).  Провести численный эксперимент, подтверждающий данную оценку. Для этого для каждого значения N из множества {10, 100, 1000, 10000, 100000 и 1000000} сгенерировать некоторое количество массивов длины N, в которых случайным образом распределены натуральные числа, подсчитать сколько раз найдется элемент больший текущего максимального и усреднить по всем массивам данной длины. Построить график зависимости найденного среднего значения от размера массива, на том же графике отложить теоретическую кривую. Для оси x использовать логарифмический масштаб.

 

6. С помощью алгоритма перебора с возвращениями (backtracking)  написать программы, решающие следующие "шахматные задачи":

- Расположить 8 ферзей на шахматной доске так, чтобы они не угрожали друг другу. Программа должна выводить на экран двумерный массив, в котором положения ферзей обозначены единицами, а пустые клетки - нулями.

- Обойти шахматную доску конем, стартуя с произвольной клетки, побывав на каждой клетке один раз. Программа должна выводить на экран двумерный массив, значения элементов которого соответствуют очередности посещения данной клетки конем.

 

7. Написать программу, реализующую сортировку массива методом слияния (mergesort).

​

8. Написать программу для определения оптимального способа разрезания стержня, используя подход, основанный на динамическом программировании. Программа должна выводить длины отрезков стержня и полную стоимость отрезков.

​

9. Используя "жадный алгоритм", написать программу для решения задачи об "Activity selection". Для  задания Activities использовать несколько частично пересекающихся отрезков, координаты границ  которых задаются с помощью псевдослучайных чисел.