Лекции по теории алгоритмов в Кочерге


Хронология пройденных тем


№1 (7.06.17) Алгоритмы и машины Тьюринга

 

№2 (14.06.17) Проблема остановки и невычислимые функции

Самостоятельно было предложено к следующему разу подумать над такой задачей:

№3 (21.06.17) Определение сложности алгоритмов

Рекомендую до следующего раза подумать самостоятельно над задачами:

  1. Придумайте алгоритм для машин Тьюринга, проверяющий, является ли входная строка палиндромом (то есть читается одинаково слева направо и справа налево). Оцените сложность вашего алгоритма для одноленточных и для многоленточных м.Т..
  2. На лекции мы доказали, что умножение и деление двоичных чисел на одноленточной машине Тьюринга выполнимо за O(n^4). Но на самом деле это можно сделать на ней и за O(n^2). Придумайте, как.
  3. Мы неоднократно пользовались без доказательства тем фактом, что размер алфавита у машины Тьюринга не влияет на сложность алгоритма. Докажите этот факт. А именно: пусть имеется машина Тьюринга с алфавитом размера k, работающая за O(t(n)). Придумайте, как смоделировать ее машиной Тьюринга с двоичным алфавитом, и оцените, во сколько раз от этого возрастет время работы.

 

№4 (28.06.17) Классические задачи на оценку сложности алгоритмов

Самостоятельно предлагаю подумать над такими задачами:

№5 (5.07.17) Классы P и NP