Файл: Контрольная работа теоретиче с кие основы ин ф орматики оглавление введение.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. Итерация алгоритмов. Итерация (повторение) представляет собой такую композицию С двух алгоритмов А и В, что для любого входного слова р соответствующее слово С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.

Нормальные алгоритмы Маркова являются не только средством теоретических построений, но и основой специализированного языка программирования, применяемого как язык символьных преобразований при разработке систем искусственного интеллекта. Это один из немногих языков, разработанных в России и получивших известность во всем мире.

---