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: 2
Plan doświadczenia 3
Sumator 3
Założenia 3
Algorytm 3
Wykonanie 4
Palindrom 4
Założenia 4
Algorytm 4
Wykonanie 5
Zawieranie się ciągów 5
Założenia 5
Algorytm 5
Wykonanie 6
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.
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.
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
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.
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.
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
Jeśli nie ma więcej liter, zakończ
KONIEC
Cały program zajmuje 53 stany i wygląda jak bardzo rozległa sieć J 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.
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.
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
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 J
tiptiripti