MIPT algorithms course of the first year of study
- Написать программу для подсчета и сортировки слов в файле с помощью двоичного дерева.
-
Написать программу, моделирующую конечные автоматы, работающие с алфавитом {0, 1} и распознающие следующие языки:
-
{0, 10},
-
слова произвольной длины, но только те, которые начинаются с последовательности 10,
-
только слова длиной 3.
-
-
Написать программу, моделирующую работу машины Тьюринга. Машина Тьюринга должна уметь выполнять следующие арифметические операции над натуральными числами, заданными в унарной системе исчисления:
-
сложение двух натуральных чисел,
-
вычитание из натурального числа двойки,
-
умножение целого числа на двойку,
-
деление целого числа на двойку.
-
Программа должна либо проводить все вычисления автоматически и выдавать окончательный ответ, либо дожидаться нажатия клавиши пользователем для выполнения очередного шага. На каждом шаге на экране должны отображаться состояние ленты, текущее положение головки МТ и внутреннее состояние МТ.
- Написать программу для вычисления примитивно рекурсивных функций, используя базис Клини и операции примитивной рекурсии и суперпозиции. Программа должна уметь вычислять следующие функции:
-
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.
-
Известно, что среднее количество случаев, когда при поиске максимального элемента в массиве из N элементов попадается новый элемент, больший, чем текущий максимальный, асимптотически равно ln(N). Провести численный эксперимент, подтверждающий данную оценку. Для этого для каждого значения N из множества {10, 100, 1000, 10000, 100000 и 1000000} сгенерировать некоторое количество массивов длины N, в которых случайным образом распределены натуральные числа, подсчитать сколько раз найдется элемент больший текущего максимального и усреднить по всем массивам данной длины. Построить график зависимости найденного среднего значения от размера массива, на том же графике отложить теоретическую кривую. Для оси x использовать логарифмический масштаб.
-
С помощью алгоритма перебора с возвращениями (backtracking) написать программы, решающие следующие "шахматные задачи":
-
Расположить 8 ферзей на шахматной доске так, чтобы они не угрожали друг другу. Программа должна выводить на экран двумерный массив, в котором положения ферзей обозначены единицами, а пустые клетки - нулями.
-
Обойти шахматную доску конем, стартуя с произвольной клетки, побывав на каждой клетке один раз. Программа должна выводить на экран двумерный массив, значения элементов которого соответствуют очередности посещения данной клетки конем.
- Написать программу, реализующую сортировку массива методом слияния (mergesort).
- Написать программу для определения оптимального способа разрезания стержня, используя подход, основанный на динамическом программировании. Программа должна выводить длины отрезков стержня и полную стоимость отрезков.
- Используя "жадный алгоритм", написать программу для решения задачи об "Activity selection". Для задания Activities использовать несколько частично пересекающихся отрезков, координаты границ которых задаются с помощью псевдослучайных чисел.