Задачи по теории алгоритмов Написать программу мт, которая аннулирует все слова в алфавите {a, b}, содержащие вхождение заданного непустого слова

• Выполнили: Фурманова Диана 3класс, 121.65kb.
• Задание по олимпиаде для 10 класса, 150.36kb.
• Программа > Результаты решения уравнения Обработка данных для получения статистических, 263.62kb.
• Цель: Проверить основные знания учащихся о составе слова, 66.34kb.
• Як правило, в півтора роки більшість дітей починають активно розмовляти, 44.89kb.
• Это не бага, это фича! Неизвестный интернетчик, 1105.4kb.
• Задачи: совершенствовать умение группировать слова по общности словообразовательных, 74.03kb.
• Сотрудничество с усц юнеско – одна из форм поддержки талантливых детей, 114.37kb.
• Марина Цветаева Пушкин и Пугачев, 361.81kb.
• Вопросы диагностики по музыке для 5 класса, 31.97kb.

Задачи по теории алгоритмов

1. Написать программу МТ, которая аннулирует все слова в алфавите {a, b}, содержащие вхождение заданного непустого слова u. Указание: пусть u=u(1)…u(m); буквы слова u должны содержаться в программе машины в качестве параметров.
   
2. Написать схему НА, обращающего любое слово в заданном алфавите V, т.е. перерабатывающего любое слово w  V*, в слово w^R.
   
3. Написать программу МТ, выполняющей правое присоединение данного слова u к любому слову в алфавите V.
   
4. Написать схему НА, который в любом входном слове в заданном алфавите V выполняет замену всех букв b₁,…,b_k из V словами u_1,…, u_k соответственно.
   
5. Используя теоремы сочетания применительно к МТ, построить МТ, выполняющей умножение натуральных чисел, представленных словами в алфавите V₀ = {0,|} (именно, натуральное число n записывается как слово 0||…| - с n палочками).
   
6. Используя теоремы сочетания, построить НА, аннулирующий все палиндромы в алфавите V. Указание: используйте схемы алгорифмов обращения и правого присоединения слова через разделитель).
   
7. Написать программу МТ, которая к произвольному слову в алфавите {a, b} приписывает слева слово aba.
   
8. Построить НА для выполнения сложения и умножения натуральных чисел. Указание: используйте теоремы сочетания.
   
9. Написать программу МТ, которая аннулирует любое слово вида x$x, где x  {a,b}*, а $  {a, b}.
   
10. С использованием теорем сочетания построить НА, который аннулирует все слова вида x$x, где x  {a,b}*, а $  {a, b}.
    
11. Написать программу МТ, которая аннулирует любое слово вида x$x^R, где x  {a,b}*, а $  {a, b}.
    
12. С использованием теорем сочетания построить НА, который аннулирует все слова вида xx^R, где x  {a,b}*.
    
13. Построить МТ, которая вычисляет модуль разности двух любых натуральных чисел. Указание: используйте сочетания МТ.
    
14. Написать программу МТ, которая удваивает любое входное слово в заданном алфавите.
    
15. Построить МТ, которая обращает любое входное слово в заданном алфавите. Указание: используйте программу МТ, удваивающей заданное слово, и сочетания МТ.
    
16. Опираясь на теорему композиции, доказать теорему соединения нормальных алгорифмов.
    
17. Является ли алгорифмически разрешимым множество всех двойных слов, т.е. слов вида ww, в заданном алфавите V?
    
18. Используя теоремы сочетания, построить НА, который проверяет делимость на 3 заданного в десятичной системе счисления натурального числа.
    
19. Построить разрешающий нормальный алгорифм для множества всех четных натуральных чисел (как слов в алфавите {0,|}).
    
20. Построить НА, который вычисляет остаток от деления заданного натурального числа (как слова в алфавите {0,|}) на 5.
    
21. Написать программу МТ, которая сдвигает входное слово на заданное число k ячеек вправо, а в освободившиеся k первых после маркера начала ленты ячейки записывает специальный символ $.
    
22. Используя сочетания МТ, построить МТ, которая вычисляет сумму цифр натурального числа, заданного в десятичной системе счисления.
    
23. В виде МТ реализовать разрешающий алгоритм для множества всех нечетных чисел, заданных как слова в алфавите {0,|}.
    
24. Будем представлять положительные рациональные числа как слова вида . Напишите схему НА, который выполняет сложение таких «дробей» с одинаковыми знаменателями.
    
25. Векторной формулой подстановки в алфавите V назовем выражение вида (p_1, p₂,…p_k)  (q_1, q₂,…q_k), где p_i, q_i – слова в алфавите V (i=1,…,k). Применение векторной формулы подстановки к слову x состоит, по определению, в следующем: если слово x может быть представлено в виде x₁p₁x₂p₂…x_kp_kx_k+1, где каждое вхождение x_i*p_i*x_i+1p_i+1… x_kp_kx_k+1 есть первое, то результатом применения векторной формулы подстановки к слову x считается слово x₁q₁x₂q₂…x_kq_kx_k+1; в противном случае результат применения векторной формулы подстановки к слову x не определен. Построить НА, выполняющий векторную подстановку.
    
26. Построить МТ, которая для заданного k > 0 проверяет, что входное слово имеет длину, строго большую k, и тогда вставляет специальный символ $ между k-ой и (k+1)-ой буквами. В противном случае (т.е при длине входного слова, не большей k) входное слово не изменяется, т.е. МТ реализует тождественную функцию.
    
27. Построить НА, который для любых двух натуральных чисел, заданных в виде слов в алфавите {0,|} проверяет, является одно из них делителем другого.
    
28. Построить МТ, распознающую палиндромы в алфавите {a, b}.
    
29. Реализовать в виде МТ разрешающий алгоритм для множества правильных скобочных структур.
    
30. Написать схему НА, который каждое слово x в заданном алфавите V перерабатывает в слово x^Rx.