bsuir.info
БГУИР: Дистанционное и заочное обучение
(файловый архив)
Вход (быстрый)
Регистрация
Категории каталога
Другое [30]
Форма входа
Логин:
Пароль:
Поиск
Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0
Файловый архив
Файлы » АСОИ » Другое

Алгоритмы и алгоритмическая сложность
Подробности о скачивании 27.05.2010, 12:37
Министерство образования Республики Беларусь

Белорусский государственный университет информатики и радиоэлектроники

Кафедра информационных технологий автоматизированных систем

Контрольная работа

по курсу
«Алгоритмы и алгоритмическая сложноать»

Выполнил:
студент группы 900621-16
Деркач А.Е.
Проверил:
Герман О.В.

Минск 2010

Контрольное задание №1

На вход поступает последовательность из 0 и 1. Машина должна заменить каждую единицу на 01. Пример. 00110010 заменяется на 00010100010.

Решение:
1 ε 0 1
Q1 εUQfin 0LQ1 0LQ2
Q2 1LQ1

ε – Пустой символ.
Qfin – Конец работы машины Тьюринга.
Текст программы:

unit Unit1;

interface

uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;

type
TForm1 = class(TForm)
Edit1: TEdit;
Memo1: TMemo;
Button1: TButton;
Button2: TButton;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form1: TForm1;
i:integer;
stroka,itogstr: string;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
begin
Memo1.Clear;
stroka:=Edit1.text;
for i:=1 to length(form1.Edit1.text) do
begin
if stroka[i]='1' then
begin
Memo1.Lines.Add('01');
end else
begin Memo1.Lines.Add('0');
end;
end;

end;
procedure TForm1.Button2Click(Sender: TObject);
begin
itogstr:='';
Memo1.Clear;
stroka:=Edit1.text;
for i:=1 to length(form1.Edit1.text) do
begin
if stroka[i]='1' then
begin
itogstr:=itogstr+'01';
end else
itogstr:=itogstr+'0';
end;

Memo1.Lines.Add(itogstr);
end;

end.

При нажатии кнопки Button1 символы выводятся в столбик.
При нажатии Button2 символы выводятся в строку.
Контрольное задание №2

Решить задачу ВЫПОЛНИМОСТЬ Методом резолюций Робинсона.
Дизъюнкты кодируются последовательностью чисел, например, 1,-2,4,-6. Эта последовательность задает следующий дизъюнкт: . В Вашем варианте будет представлено несколько дизъюнктов. Из п.А Вы выбираете метод и применяете его к Вашей задаче ВЫПОЛНИМОСТЬ. Вы должны показать работу метода по шагам с разъяснением.

Вариант 4. -1,-2,-3
-2,3
3,5
3, -5
-3, -4
5,
4

Решение:

D1 =¬x1 v ¬x2 v ¬x3;
D2 =¬x2 v x3;
D3=x3 v x5;
D4= x3 v ¬x5;
D5= ¬x3 v ¬x4;
D6= x5;
D7= x4.

D 1,2 = ¬x1 v ¬x2;
D1,2;3 = ¬x1 v ¬x2 v x3 v x5;
D1,2,3;4= ¬x1 v ¬x2 v x3;
D1,2,3,4;5= ¬x1 v ¬x2 v ¬x4;
D1,2,3,4,5;6= ¬x1 v ¬x2 v ¬x4 v x5;
D1,2,3,4,5,6;7= ¬x1 v ¬x2 v x5.

Категория: Другое | Добавил: KLINSKI
Просмотров: 3229 | Загрузок: 43 | Комментарии: 28
Всего комментариев: 261 2 »
0  
21 meljo   (26.01.2011 02:17) [Материал]
если кого интересует могу скинуть на паскале прогу которая будет работать именно по вашим правилам машины тьюринга (по вашей таблице) так сказать универсальную, по ней можете проверить правильно составили свою таблицу или нет biggrin
прога ничего хитрого не делает просто считывает текстовый файл, в котором записанны правила вашей машины, и по этим правилам обрабатывает текстовый файл где записанно входное слово, после того как она отработает, открываете файл и смотрите что стало с входным словом

0  
24 hexau   (27.01.2011 12:09) [Материал]
есть же исходник в методе. универсальной мТ. cool

0  
25 meljo   (27.01.2011 16:35) [Материал]
да есть но он что-то у меня не пошел, а переделывать не люблю, легче заново написать, хотя потом сравнивал в целом похоже biggrin

0  
20 meljo   (26.01.2011 02:11) [Материал]

полностью с этим согласен ведь там написанно:

а у вас машина тьюринга работает по своим правилам (еще не факт что правильным), а програма в делфях по своим правилам

+1  
19 meljo   (26.01.2011 02:02) [Материал]
D1 =¬x1 v ¬x2 v ¬x3;
D2 =¬x2 v x3;
D3=x3 v x5;
D4= x3 v ¬x5;
D5= ¬x3 v ¬x4;
D6= x5;
D7= x4.
решение:
D12=¬x1 v ¬x2,
D13=¬x1 v ¬x2 v x5,
D14=¬x1 v ¬x2 v ¬x5,
D25=¬x2 v ¬x4,
D34=x3,
D35=x5 v ¬x4,
D45=¬x5 v ¬x4,
D46=x3,
D57=¬x3,
а вот теперь можно создать резольвенту из D34 и D57, которая даст пустой дизъюнкт:
D3457=□.
Вывод система противоречива или невыполнима

+1  
18 meljo   (26.01.2011 01:54) [Материал]
Решить задачу ВЫПОЛНИМОСТЬ Методом резолюций Робинсона.
решение не верное - где ответ на ваше решение

и ещё

biggrin

+2  
16 vitor   (12.01.2011 00:12) [Материал]
Первое задание решено не совсем верно.
Машина Тьюринга не может делать это:

if stroka[i]='1' then
begin
itogstr:=itogstr+'01';
end else
itogstr:=itogstr+'0';
end;

Все что она "умеет" это читать или записывать один символ, смещаться вправо, влево или оставаться на месте и переходить в некоторое другое состояние.

Вот пример выполнения этого же задания:

#include "stdafx.h"
#include <iostream>
using std::cout;
using std::cin;
using std::endl;

#define R 1
#define N 0
#define L -1

#define Q1 0
#define Q2 1
#define Q3 2
#define Q4 3
#define Q5 4
#define Q6 5
#define Q7 6
#define Q8 7
#define EXIT 8

typedef struct
{
char symbol;
char action;
char state;
}MT_struct;

int _tmain(int argc, _TCHAR* argv[])
{
MT_struct MT[8][4]={
{{' ',R,Q1},{' ',R,Q1},{' ',N,EXIT},{'=',N,Q2}},
{{' ',L,Q2},{' ',L,Q2},{' ',L,Q2},{' ',R,Q3}},
{{'e',R,Q4},{'e',R,Q5},{'e',R,Q7},{' ',N,EXIT}},
{{' ',R,Q4},{' ',R,Q4},{' ',R,Q4},{'0',N,Q2}},
{{' ',R,Q5},{' ',R,Q5},{' ',R,Q5},{'0',N,Q6}},
{{' ',R,Q6},{' ',R,Q6},{' ',R,Q6},{'1',N,Q2}},
{{' ',R,Q7},{' ',R,Q7},{' ',R,Q7},{0,L,Q8}},
{{' ',L,Q8},{' ',L,Q8},{' ',L,Q8},{' ',R,EXIT}},
}; // таблица состояний

char str[100];
char index=1,symbol,state=Q1; //turing initial state

cout<<"Input 0 or 1\n";
str[0] = 'e';
cin.get(&str[1],100);

if (str[index]=='0') symbol=0;
else if (str[index]=='1') symbol=1;
else if (str[index]=='=') symbol=2;
else symbol=3;

while (state != EXIT)
{
if (MT[state][symbol].symbol!=' ') str[index] = MT[state][symbol].symbol;

index += MT[state][symbol].action;
state = MT[state][symbol].state;

if (str[index]=='0') symbol=0;
else if (str[index]=='1') symbol=1;
else if (str[index]=='=') symbol=2;
else symbol=3;
}
cout<<&str[index]<<endl;
return 0;
}

если интересно как это работает или нужно сделать такое задание(любое из предложенных вариантов) пишите - [email protected]


-2  
17 KLINSKI   (13.01.2011 01:22) [Материал]
Интересно, а если на вход будет поступать несколько тысяч 0 и 1 сколько состояний будет иметь ваша машина????

0  
22 meljo   (26.01.2011 02:20) [Материал]
хоть несколько миллионов, количество состояний от этого не поменяется, просто машина дольше головой будет дергать вдоль ленты cool

0  
15 Andromeda   (29.12.2010 15:44) [Материал]
Может кто решил задачу на выполнимость методом групповых резолюций? Подскажите как делать, не могу понять... sad

0  
13 patrol   (08.12.2010 11:37) [Материал]
Может ктот знает как для 7 варианта написать машину тьюринга?

0  
12 Richi   (16.11.2010 21:17) [Материал]
нужна помощь по написанию этой контрольной... отпишитесь в личку..

+1  
11 Vahe   (16.11.2010 16:40) [Материал]
Задача на выполнимость написана не правильно!

0  
14 KLINSKI   (23.12.2010 17:56) [Материал]
Блин, народ, ну как же не правильно???? Сам лично писал и сдавал эту контрольную.... контрольная была безупречна. Препод убедился что контрольную писал сам, и 6 баллов в зачётке!!!!!!

0  
26 hexau   (29.01.2011 18:00) [Материал]
преподы тоже люди и, о боже, тоже ошибаются. biggrin

0  
10 Vahe   (15.11.2010 20:45) [Материал]
и скажыте как понять! дык это задача решёная на машине Тьюринга правильно или нет!?

0  
23 meljo   (26.01.2011 02:25) [Материал]
найти рабочую машину тьюринга, загрузить в нее таблицу с лентой и посмотреть правильно отработает или нет wink

1-10 11-19
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]