Konrad Kukulski, 163930 Wrocław, 11.06.2010

Elżbieta Tchorowska, 171067

Struktury danych i złożoność obliczeniowa

Projekt nr 3

Temat: Maszyna Turinga.

Prowadzący: prof. dr hab. inż. A. Janiak

Spis treści:

Plan doświadczenia

Do przeprowadzenia doświadczenia użyto komputera z procesorem Intel Core Duo 1,86GHz, 1 Gb RAM. Programem do pisania programów na Maszynę Turinga był program dostarczony przez Zakład.

Sumator

Założenia

Danymi wejściowymi są cyfry 0 i 1. Separacją znak #. Przeprowadza się standardowe dodawanie dwóch liczb binarnych. Dwie liczby oddzielone są pojedynczym separatorem. Wynik dodawania ma znaleźć się po ich prawej stronie, w oddaleniu jednego separatora. Liczby mogą być dowolnej długości.

Algorytm

Wykonanie

Każdy z bloczków schematu jest przedstawiony jako osobna grupa stanów programu. Cały program załączony na płycie. Całość posiada 63 stany + początkowy i końcowy. Samo dodawanie zajmuje tylko 9 stanów. Cała reszta odpowiada za przeniesienia i ustawienia stanu końcowego maszyny.

Największy problem stanowiło dodanie dwóch liczb, gdzie wynik był powiększony o jeden bit. Rozwiązano, dodając niestety trzy dodatkowe stany.

Palindrom

Założenia

Alfabetem wejściowym jest alfabet angielski, 24-cztero znakowy. Separatorem znak #. Program sprawdza, czy wprowadzony ciąg znaków jest taki sam przeglądany od prawej i od lewej. Program ma zwracać odpowiedź `tak' lub `nie', w zależności od wyniku doświadczenia.

Algorytm

Wykonanie

Cały program zajmuje 53 stany i wygląda jak bardzo rozległa sieć Całość jest wykonana praktycznie na samych realizacjach komendy `if', więc utworzone drzewo jest bardzo rozrośnięte w dół, zaś w prawo pozostaje takie samo, nie ważne dla jakiej ilości liter alfabetu. Nie pojawiły się większe problemy w realizacji zadania.

Zawieranie się ciągów

Założenia

Dane są dwa ciągi dowolnych znaków - liter alfabetu angielskiego, oddzielonych separatorem #. Pierwszy po lewej jest mniejszy, drugi większy. Zadaniem jest sprawdzenie, czy pierwszy zawiera się w drugim. Odpowiedzią programu ma być `tak' lub `nie', w zależności od rezultatu doświadczenia.

Algorytm

Wykonanie

Cały program ma ponad 100 stanów. Niestety program nie spełnia pełnych oczekiwań. W chwili pisania zapomniano, że ostatnie pasujące elementy starego sprawdzania ciągu, mogą być pasującymi elementami już w nowym podciągu. Nie dopracowano do końca tego problemu. Całe drzewo jest mało czytelne

START

skopiowanie liczby 1 i 2 na prawą stronę

Przeniesienie liczb o jedno miejsce w lewo

Standardowa operacja dodawania binarnego z przeniesieniem.

Przeniesienie liczb na ich pierwotne miejsca

KONIECSTART

KONIECSTART

START

Szukanie pierwszej litery ciągu

Zamiana litery na #, przejście na ostatnią literę

Jeśli litera ostatnia jest równa pierwszej, zamień na #

Wróć na początek, do następnej litery, jeśli istnieje

Wróć na początek, do następnej litery, jeśli istnieje

Jeśli nie ma więcej liter, zakończ

KONIEC

START

Przepisanie mniejszego ciągu o dwie pozycje w lewo

Odczytanie pierwszej litery krótszego ciągu

Przesunięcie do 1. litery drugiego ciągu, sprawdzenie, czy są równe

Jeśli tak, przeniesienie litery z drugiego ciągu o pozycję w lewo

Jeśli nie, to przepisujemy literę dwa pola dalej

---