Контрольные вопросы. 
Теоретические основы информатики

• 1. Приведите различные интуитивные понятия алгоритма. Что в этих определениях общего?
• 2. Каким требованиям должен удовлетворять алгоритм? Какие свойства важны с практической точки зрения при компьютерной реализации алгоритма?
• 3. Приведите структуру алгоритмической системы. Охарактеризуйте взаимосвязи между элементами этой системы.
• 4. Каким образом связаны понятия алгоритма и вычислимой функции?
• 5. Что называется порождающей грамматикой? Какие элементы составляют порождающую грамматику?
• 6. Приведите неформальное определение машины Тыориига. Дайте характеристику элементам машины Тьюринга. Каким реальным устройствам соответствуют компоненты машины?
• 7. Сформулируйте различные проблемы разрешимости. Какие из них могут быть решены с помощью машины Тыориига?

Задания для самостоятельного решения

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

• — нахождение корней квадратного уравнения;
• — нахождение наименьшего общего делителя двух натуральных чисел;
• — нахождение наименьшего общего кратного двух чисел.

Задание 2. В алфавите V = {a, b, c, d, e} найдите:

• а) лексикографический номер слов dabcce, bbacdb, eaebca:
• б) слова, соответствующие номерам 6736, 12 346, 27 737.

Задание 3. Дана грамматика G = (V, N, S, P), в которой V = {а, 6}, N = {Q}, S = = Q, Р = {Q —> ab, в —у авЬ}. Здесь в — любое слово из V*. Определите, какие слова порождаются данной грамматикой.

Задание 4. Машина Тыориига задается множеством состояний Q = {q₀, внешним алфавитом S = {а, 6, с} и следующей функциональной схемой:

Найдите результат работы машины Тыориига для начальной конфигурации bbeb (bjq).