Контрольные работы
1. Приведите протокол работы алгоритма поиска наибольшего общего делителя чисел 123456 и 4321.
2. Запишите утверждение, состоящее в том, что h есть наибольший общий делитель чисел f и g в терминах предиката D(x,y), означающего «x делит y» и предиката G(x,y). означающего «x больше или равно y».
3. Постройте конечный автомат для распознавания языка {abncma}.
Опишите грамматику языка {abncma} в форме Бэкуса-Наура.
4. Постройте машину Тьюринга для вычитания натуральных чисел в единичном коде (из n вычесть m (n>m), если первое число записано n единицами на ленте машины, затем следует разделитель, например, *, после которого идут m единиц второго числа).
5. Поставьте электронную подпись на сообщении, заданным двузначным числом 27, используя код RSA с открытыми частями m=17*23 и e= 125.
6. Классифицируйте по трудоемкости их решения следующие задачи:
а) перемножение целых чисел, размер задачи определяется длиной минимального из чисел n;
б) разложение целых чисел на множители, размер задачи определяется длиной числа n;
в) доказательство того, что логическое выражение, заданное логической формулой, состоящей из переменных и логических связок, является тавтологией, размер задачи определяется количеством символов n, входящих в формулу;
г) нахождение кратчайшего пути, соединяющего две заданные вершины взвешенного графа, размер задачи определяется числом вершин графа n;
д) нахождение кратчайшего пути, проходящего через все вершины взвешенного графа, размер задачи определяется числом вершин графа n.
Возврат
