4.Сформулируйте основные определения абстрактного алфавита (алфавит, слово алфавита, расширение алфавита, алфавитный оператор).

Алфавит (абстрактный алфавит) - любая конечная совокупность объектов, называемых буквами (символами) этого алфавита. В качестве символов могут выступать, например, цифры, любые значки, рисунки, целые слова ("ключевые" слова), фразы, абзацы, книги и т.п.

Слово (строка) алфавита - любая конечная упорядоченная последовательность символов, Длина слова - число символов в нем. Пустое слово (‘e’) имеет нулевую длину, в операции конкатенации играет роль единицы. Подслово слова- его левая или правая часть, в частности пустое слово.

При расширении алфавита понятие слова может существенно меняться. Так, например, в алфавите A={0,1,2,3,4,5,6,7,8,9} цепочка символов 69+73 представляет собой два слова, соединенные знаком суммы, а в алфавите В={+,0,1,2,3,4,5,6,7,8,9} это будет одно слово.

Алфавитный оператор (отображение)- всякое соответствие между словами одного и того же или разных (фиксированных) алфавитов. В последнем случае это входной и выходной алфавиты. Алфавитные операторы могут быть однозначными, многозначными, неопределенными на некотором слове и т.д. Область определения алфавитного оператора- совокупность входных слов, где алфавитный оператор (АО) определён.

5.Области применения теории алгоритмов.

Во всех областях математики, в которых встречаются алгоритмические проблемы. Такие проблемы возникают практически во всех разделах математики. В математической логике для каждой теории формулируется проблема решения множества всех истинных или доводочные утверждений этой теории относительно множества всех ее предложений (теории подразделяются на разрешимые и неразрешимые в зависимости от разрешимости или неразрешимости указанной проблемы); в 1936 А. Черч установил неразрешимость проблемы разрешимости для множества всех истинных предложений логики предикатов, дальнейшие важные результаты в этом направлении принадлежат А.Тарском, А. И. Мальцеву и др.. Неразрешимые алгоритмические проблемы встречаются в алгебре (проблема тождества для полугрупп и, в частности, для групп ; первые примеры полугрупп с неразрешимой проблемой тождества были изобретены в 1947 г. независимо А. А. Марковым и Э. Постом, а пример группы с неразрешимой проблемой тождества - в 1952 г. П. С. Новиковым ); в топологии (проблема гомеоморфии, неразрешимость которой для важного класса случаев была доказана в 1958 г. А. А. Марковым ); в теории чисел (проблема решения 'язности диофантовых уравнений, неразрешимость которого была установлена в 1970 г. Ю. В. Матиясевичем ) и в др.. разделам математики.

Теория алгоритмов тесно связана:

1) с математической логикой, поскольку в терминах алгоритмов может быть изложено одно из центральных понятий математической логики - понятие исчисления (и поэтому, напр., Геделя теорема о неполноте формальных систем может быть получена как следствие теорем А. т.) 2) с основами математики, в которых одно из центральных мест занимает проблема соотношения конструктивного и неконструктивного (в частности, А. т. дает аппарат, необходимый для разработки конструктивного направления в математике); в 1965 г. А. Н. Колмогоров предложил использовать А. т. для обоснования теории информации, 3) с кибернетикой, в которой важное место занимает изучение алгоритмов управления. А. т. образует теоретический фундамент для ряда вопросов вычислительной математики.

6.Требования к составу микроопераций и логических условий алгоритма.

Для выполнения операций над информацией используются операционные устройства — арифметико-логические, управления, контроллеры ВУ и т. п. Функцией операционного устройства является выполнение заданного множества операций F ={f₁, f₂, ..., f_k } над входными словами из множества D₁ с целью вычисления выходных слов из множества Doпредставляющих результаты операций D₀  = f_k  (D₁).  k=1,…, K.

            Функциональная и структурная организация операционных устройств, определяющая порядок функционирования и структуру устройств, базируется на принципе микропрограммного управления, который состоит в следующем:

            1. Любая операция f_k, реализуемая устройством, рассматривается как сложное действие, которое разделяется на последовательность элементарных действий над словами информации, называемых микрооперациями.

            2. Для управления порядком следования микроопераций используются логические условия, которые, в зависимости от значений слов, преобразуемых микрооперациями, принимают значения "истина" или "ложь" (1 или 0).

            3. Процесс выполнения операций в устройстве описывается в форме алгоритма, представляемого в терминах микроопераций и логических условий и называемого микропрограммой. Микропрограмма определяет порядок проверки значений логических условий и следования микроопераций, необходимый для получения требуемых результатов.

            4. Микропрограмма используется как форма представления функции устройства, на основе которой определяются структура и порядок функционирования устройства во времени.

            Сказанное можно рассматривать как содержательное описание принципы микропрограммного управления, из которого следует, что структура и порядок функционирования операционного устройства предопределяются алгоритмами выполнения операций из F .