Файл: Контрольная работа теоретиче с кие основы ин ф орматики оглавление введение.doc

Министерствонаукиивысшегообразования РоссийскойФедерацииФГБОУ ВО «Кубанскийгосударственныйтехнологическийуниверситет»Кафедра информационныхсистеми программированияКОНТРОЛЬНАЯ РАБОТАТЕОРЕТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИОГЛАВЛЕНИЕВведение…………………………………………………………………………...3Основная часть…………………………………………………………………….4Заключение………………………………………………………………………11Список используемой литературы……………………………………………..12ВведениеКонтрольная работа по дисциплине теоретические основы информатики предназначена для закрепления лекционного материала и приобретения студентами первичных умений и навыков в концептуальной постановке прикладных задач, выявлению существенных связей между объектами и процессами в предметной области, их формальному описанию и разработке прототипа приложений.Вариант19.Задание 1. Разработайте и проверьте модель двухразрядного двоичного сумматора sum/7. Описание аргументов: sum(X1, X2, Y1, Y1, Z1, Z1, P). Здесь складывается двухразрядное число X и двухразрядное число Y. Получаемый результат: двухразрядное число Z и сигнал переноса P.Решение:using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace Help{class Program{static void Main(string[] args){int s1 = int.Parse(IntToDec(Console.ReadLine(), 2));int s2 = int.Parse(IntToDec(Console.ReadLine(), 2));Console.WriteLine("Сумма равна {0}", Convert.ToString(s1+s2,2));Console.ReadLine();}public static string IntToDec(string qint, int q){ string result;const string figure = "01";int dint = 0;for (int i = 0; i < qint.Length; i++){dint = q * dint + figure.IndexOf(qint[i]);}result = dint.ToString();return result;}}}Задание 2.Разработать программу для целочисленного деления на 2 произвольного бинарного числа для машины Тьюринга.

---

Решение:Реализация может выполнять следующее:

1. 
   применяем входные данные в виде # 11 ... 1011 ... 1 # где первая строка из 1s представляет a в унарном, вторая строка представляет b в унарном, # является пустым, а головка ленты изначально начинается с крайнего левого 1;
   
2. 
   немедленно впишем Q в конце ленты; все, что после этого, является частным
   
3. 
   проверяем, является ли b> a; если да, запустите некоторую процедуру, чтобы переписать частное и остаток в красивом формате перед завершением. проверьте, отскакивая назад и вперед по 0 и временно помечая пары ячеек, затем измените их обратно на 1s впоследствии.
   
4. 
   в противном случае изменяем крайние левые экземпляры b с 1 на X, добавляем 1 после крайнего правого 1, а затем повторите с шага 3. Отметьте экземпляры b, перемещаясь взад и вперед по 0 и временно помечая единицы, содержащие b, чтобы не удваивать счет; затем измените их обратнодо 1с.
   

кодinitial tape: #11111011#after step 2: #11111011Q#after step 3: (same)after step 4: #XX111011Q1#after step 3: (same)after step 4: #XXXX1011Q11#after step 3: #1101# (formatted)Задание 3.Сравнить вычислительные сложности выполнения алгоритмов на машинах Тьюринга и Маркова и сделать заключение о классах задач, на которых та или иная машина работает эффективно.Решение:Время, требующееся алгоритму, зависит от входа и машины, на котором он выполняется. Хорошей мерой сложности алгоритма является асимптотическая функция времени в худшем случае (как функция от длины входа, n).Для входа w обозначим n = |w|. Следуя [Hartmanis, 1989], мы говорим, что машина Тьюринга Mработает за времяT(n) , если для всех w длины n, вычисление M(w) требует максимум T(n) шагов, а затем машина останавливается. Это так называемая функция времени в худшем случае, так как машина может работать на каком-нибудь входе длины n.Для всякой функции T : N → N, пустьTIME[T(n)] = { A | A = L(M) для какой-нибудь машины M, работающей T(n)}Алан Кобхэм и Джек Эдмондс определили класс сложности P как все задачи, решаемые за полиномиальное время, и это отличное математическое определение задач, решаемых на практике

---

P = ∪_i=1,2,… TIME[nⁱ ]Всякая задача, не принадлежащая классу P, конечно неосуществима. С другой стороны, у задач, принадлежащих этому классу, обычно есть осуществимые алгоритмы.Кроме P было изучено много других важных классов, некоторые из них это NP, PSPACE, и EXPTIME. PSPACE состоит из задач, решаемых на полиномиальной памяти. EXPTIME - множество задач, решаемых за время 2^p(n) для некоторого полинома p.Возможно, один из самых интересных описанных выше классов – это NP. Недетерминированная машина Тьюринга, N, выбирает между двумя возможными действиями на каждом шаге. Если на входе w некоторая последовательность шагов приводит к тому, что это вход принимается, тогда мы говорим, что N принимает w, и мы говорим, что недетерминированное время, необходимое N на входе w – это всего лишь количество шагов в последовательности, которая ведет к принятию w. Мы не учитываем длины всех возможных последовательностей шагов, только той, которая ведет к принятию.NP иногда определяется как класс проблем S, которые имеют короткие доказательства принадлежности множеству. Например, нам дано множество из m больших натуральных чисел a₁, …, a_m и число t. Проблема Subset Sum формулируется следующим образом: существует ли подмножество данного нам множества, члены которого в сумме дают ровно m? Эту задачу легко решить с помощью недетерминированной машины Тьюринга: для каждого i мы решаем, включить a_i в подмножество или нет. Затем мы суммируем все числе в подмножестве и проверяем, равна ли сумма t. Тем самым, недетерминированное время линейно зависит от длины входа. Однако, не известно (детерминированного) алгоритма, который бы решал эту задачу за менее чем экспоненциальное время.Алгоритмы хорошо изучены, и известна сложность многих задач. В частности, было определено сведение одной задачи к другой, что используется для сравнения сложности задач. Неформально, можно сказать, что A сводится к B (A ≤ B), если существует простое преобразование τ, которое преобразует элементы A в элементы B, так что τ(w) ∈ B

---

⇔ w ∈ A.

Довольно большое число задач оказываются полными для одного из выше описанных классов (Задача A полна для класса сложности C, если , и все остальные задачи этого класса не сложнее, чем A. Две полные задачи одного и того же класса имеют одинаковую сложность).

Причина существования полных проблем непонятна. Одно из возможных объяснений состоит в том, что естественные задачи в каком-то смысле выполняют роль универсальных машин Тьюринга. Универсальная проблема в определенном классе сложности может заменить любую другую. Причина того, что класс NP хорошо изучен, состоит в том, что многие задачи принадлежат NP, включая Subset Sum. Ни одна из этих проблем не имеет известного полиномиального алгоритма, хотя некоторые NP-полные задачи имеют приближенные решения.

Многое еще неизвестно о сложности вычислений. Мы знаем, что строго большее количество вычислительных ресурсов позволяет нам решать строго более сложные задачи. Однако, с разными вычислительными ресурсами все не так просто. Очевидно, что P содержится в NP. Далее, NP содержится в PSPACE, поскольку в PSPACE мы можем систематически пробовать каждую ветвь NP вычислений. PSPACE содержится в EXPTIME, поскольку, если для PSPACE требуется более, чем полиномиальное число шагов, то одна и та же конфигурация встретится дважды, и работа машины зациклится. Вот известные отношения между классами:

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME

И хотя кажется очевидным, что все эти неравенства строгие, ни одно из них не было доказано. Единственное, что было доказано – это то, что P строго содержится в EXPTIME. Оставшиеся задачи – это фундаментальные нерешенные задачи теории сложности вычислений.

Нормальный алгоритм Маркова можно рассматривать как универсальную форму задания любого алгоритма. Универсальность нормальных алгоритмов декларируется принципом нормализации: для любого алгоритма в произвольном конечном алфавите А можно построить эквивалентный ему нормальный алгоритм над алфавитом А,

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

---

Если алгоритм N задан в некотором расширении алфавита А, то говорят, что N есть нормальный алгоритм над алфавитом А.Условимся называть тот или иной алгоритм нормализуемым, если можно построить эквивалентный ему нормальный алгоритм, и ненормализуемым в противном случае. Принцип нормализации теперь может быть высказан в видоизмененной форме: все алгоритмы нормализуемы.Данный принцип не может быть строго доказан, поскольку понятие произвольного алгоритма не является строго определенным и основывается на том, что все Известные в настоящее время алгоритмы являются нормализуемыми, а способы композиции алгоритмов, позволяющие строить новые алгоритмы из уже известных, не выводят за пределы класса нормализуемых алгоритмов. Ниже перечислены способы композиции нормальных алгоритмов.I. Суперпозиция алгоритмов. При суперпозиции двух алгоритмов А и В выходное слово первого алгоритма рассматривается как входное слово второго алгоритма В. Результат суперпозиции С может быть представлен в виде С(р) = В(А(р)),II. Объединение алгоритмов. Объединением алгоритмов А и В в одном и том же алфавите называется алгоритм С в том же алфавите, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В, в записанные рядом слова А(р) и В(р).III. Разветвление алгоритмов. Разветвление алгоритмов представляет собой композицию D трех алгоритмов А, В и С, причем область определения алгоритма D является пересечением областей определения всех трех алгоритмов А, В и С, а для любого слова р из этого пересечения D(p) = А(р), если С(р) = е, D(p) = B(p), если С(р) = е, где е - пустая строка.IV. Итерация алгоритмов. Итерация (повторение) представляет собой такую композицию С двух алгоритмов А и В, что для любого входного слова р соответствующее слово С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.Нормальные алгоритмы Маркова являются не только средством теоретических построений, но и основой специализированного языка программирования, применяемого как язык символьных преобразований при разработке систем искусственного интеллекта. Это один из немногих языков, разработанных в России и получивших известность во всем мире.

---