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

Министерство образования Республики Беларусь

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

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

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

по курсу

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

Выполнил:

студент группы 900621-16

Деркач А.Е.

Проверил:

Герман О.В.

Минск 2010

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

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

Решение:

1	ε	0	1
Q1	εUQfin	0LQ1	0LQ2
Q2	1LQ1

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

Текст программы: 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

Решение:

D₁ =¬x₁ v ¬x₂ v ¬x₃;

D₂ =¬x₂ v x₃;

D₃=x₃ v x₅;

D₄= x₃ v ¬x₅;

D₅= ¬x₃ v ¬x₄;

D₆= x₅;

D₇= x₄.

D _1,2 = ¬x₁ v ¬x₂;

D_1,2;3 = ¬x₁ v ¬x₂ v x₃ v x₅;

D_1,2,3;4= ¬x₁ v ¬x₂ v x₃;

D_1,2,3,4;5= ¬x₁ v ¬x₂ v ¬x₄;

D_1,2,3,4,5;6= ¬x₁ v ¬x₂ v ¬x₄ v x₅;

D_{1,2,3,4,5,6;7}= ¬x₁ v ¬x₂ v x₅.