Wykłady n.t.

Teoretyczne podstawy informatyki

Algebra Boole'a

Zbiór wartości z określonymi w nich działaniami na dwóch elementach: mnożenia ∧ i dodawania ∨ i działania na jednym elemencie : dopełnienie ~

Dwa wyróżnione elementy 0 i 1 , w których są spełnione aksjomaty dla wszystkich elementów o symbolach x, y, z ∈ {0, 1 }

A1: x ∨ 0 = x A2: x ∧ 1 = x moduł sumy i mnożenia

A3: x ∨ y = y ∨ x A4: x ∧ y = y ∧ x przemienność działania

A5: x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) rozdzielność dodawania względem mnożenia

A6: x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) rozdzielność mnożenia względem dodawania

A7: x ∨ ~x = 1 A8: x ∧ ~x = 0

A9: x ∧ ( y ∧ z ) = ( x ∧ y ) ∧ z łączność mnożenia

A10: x ∨ ( y ∨ z ) = ( x∨ y ) ∨ z łączność dodawania

dodatkowo dodaje się najczęściej aksjomaty:

x ∨ 1 = 1 x ∧ 0 = 0 A.11 i A.12

można zamiast tych aksjomatów podać dwa inne

x ∨ 1 = ~x x ∧ 0 = ~x A.13 i A.14

W przypadku przyjęcia aksjomatów A.11 i A.12 otrzymujemy następujące tabele zależności (czasami nazywamy je tabelami prawdy):

x	y	F(x,y) = x ∨ y		x	y	F(x,y) = x ∧ y
0	0	0		0	0	0
0	1	1		0	1	0
1	0	1		1	0	0
1	1	1		1	1	1

W przypadku przyjęcia aksjomatów A.13 i A.14 otrzymalibyśmy tabele zależności

x	y	F(x,y) = x ∨ y		x	y	F(x,y) = x ∧ y
0	0	0		0	0	1
0	1	1		0	1	0
1	0	1		1	0	0
1	1	0		1	1	1

Funkcja boole'owska

Funkcja boole'owska odwzorowuje zbiory wartości boole'owskich w zbiór wartości boole'owskich:

F(a,b,c,...) z, gdzie a, b, c, ... , z ∈ {0,1}

Funkcje takie można opisać w trojaki sposób:

• słowny,

• w postaci tabeli zależności,

• w postaci wyrażeń boole'owskich

Implikanty i implicenty

Implikantem funkcji F() nazywamy iloczyn I zmiennych w postaci prostej lub zanegowanej, spełniający następującą zależność:

I=1 ⇒ F()=1

Implikant zawierający wszystkie zmienne funkcji F nazywamy implikantem pierwotnym.

Implikant funkcji F, z którego usunięcie dowolnej zmiennej powoduje, że przestaje być implikantem nazywamy implikantem prostym.

Implicentem funkcji F() nazywamy sumę J zmiennych w postaci prostej lub zanegowanej, spełniającą następującą zależność:

J=0 ⇒ F()=0

Implicent zawierający wszystkie zmienne funkcji F nazywamy implicentem pierwotnym.

Implicent funkcji F, z którego usunięcie dowolnej zmiennej powoduje, że przestaje być implicentem nazywamy implicentem prostym.

Przekształcanie i upraszczanie formuł boole'owskich

Prawa d'Morgana

~(x ∧ y) = ~x ∨ ~y oraz ~(x ∨ y) = ~x ∧ ~y

Reguła pochłaniania

A ∨ (A ∧x) = A ∨ (A ∧~x) = A

oraz

A ∧ (A ∨ x) = A ∧ (A ∨ ~x) = A

Reguła sklejania

(A ∧~x) ∨ (A ∧x) = A

oraz

(A ∨ ~x) ∧ (A ∨ x) = A

Sąsiedztwo logiczne

Sąsiedztwo słów binarnych:

Dwa słowa binarne o tej samej długości (ta sama liczba bitów) są sąsiednie logicznie jeżeli różnią się tylko na jednej pozycji.

Sąsiedztwo implikantów (implicentów):

Każdy pierwotny implikant (implicent) można zapisać w postaci ciągu zer i jedynek, przypisując zmiennej w postaci prostej jedynkę a zmiennej w postaci zanegowanej zero lub odwrotnie. Zatem analogicznie do sąsiedztwa słów binarnych, dwa pierwotne implikanty (implicenty) są sąsiednie logicznie jeżeli różnią się postacią tylko jednej zmiennej.

Synteza i upraszczanie funkcji boole'owskiej

Sposoby opisu funkcji boole'owskiej:

• opis słowny,

• opis w postaci tablicy zależności,

• opis w postaci wyrażenia algebraicznego.

W dalszej części przyjmuje się następujące oznaczenia:

~x oznaczamy

~(x ∧ y) oznaczamy

~( x ∨ y ) oznaczamy

Tabela 1

waga/ równoważnik	a	b	c	d	F1	F2	F3	f	f	f	f	f	f	f	f	f	f	f	f	f	f	f	f
		2^3	2^2	2^1				2^0				0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	0	0	0	1	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	1	0	1	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
2	0	0	1	0	1	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0
3	0	0	1	1	0	1	1	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0
4	0	1	0	0	0	1	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0
5	0	1	0	1	1	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
6	0	1	1	0	0	1	1	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0
7	0	1	1	1	0	1	1	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0
8	1	0	0	0	1	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0
9	1	0	0	1	1	0	1	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0
10	1	0	1	0	0	0	1	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0
11	1	0	1	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0
12	1	1	0	0	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0
13	1	1	0	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0
14	1	1	1	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0
15	1	1	1	1	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1

F₁ = f0 + f2 + f5 + f8 + f9 + f11 + f12 + f13 + f15 = ….

F₂ = f0 + f1 + f3 + f4 + f6 + f7 + f11 + f12 + f13 + f14 = …

F₃ = f1 + f3 + f6 + f9 + f10 + f15 = ....

Tabela 1

waga/ równoważnik	a	b	c	d	F1	F2	F3	g	g	g	g	g	g	g	g	g	g	g	g	g	g	g	g
		2^3	2^2	2^1				2^0				0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	0	0	0	1	1	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
1	0	0	0	1	0	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1
2	0	0	1	0	1	0	0	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1
3	0	0	1	1	0	1	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1
4	0	1	0	0	0	1	0	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1
5	0	1	0	1	1	0	0	1	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1
6	0	1	1	0	0	1	1	1	1	1	1	1	1	0	1	1	1	1	1	1	1	1	1
7	0	1	1	1	0	1	1	1	1	1	1	1	1	1	0	1	1	1	1	1	1	1	1
8	1	0	0	0	1	0	0	1	1	1	1	1	1	1	1	0	1	1	1	1	1	1	1
9	1	0	0	1	1	0	1	1	1	1	1	1	1	1	1	1	0	1	1	1	1	1	1
10	1	0	1	0	0	0	1	1	1	1	1	1	1	1	1	1	1	0	1	1	1	1	1
11	1	0	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	0	1	1	1	1
12	1	1	0	0	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	0	1	1	1
13	1	1	0	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	0	1	1
14	1	1	1	0	0	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	0	1
15	1	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	0

F₁ = g1 * g3 * g4 * g6 * g7 * g10 * g14 = ...

F₂ = g2 * g5 * g8 * g9 * g10 * g15 = ...

F₃ = g0 * g2 * g4 * g5 * g8 * g11 * g12 * g13 * g14 = ...

Przykład przekształcania funkcji boole'owskiej do postaci kanonicznej

Przekształćmy do postaci kanonicznych: sumy iloczynów i iloczynu sum funkcję:

Wykorzystując prawa de Morgana otrzymamy:

W celu otrzymania postaci sumy iloczynów wykorzystamy prawo rozdzielności mnożenia względem dodawania. Otrzymamy wówczas:

W celu otrzymania postaci iloczynu sum wykorzystamy prawo rozdzielności dodawania względem mnożenia. Otrzymamy wówczas:

Siatki Karnaugh'a - upraszczanie funkcji logicznej

Zapis informacji - kodowanie liczb

• kodowanie znaków np. ASCII

• kodowanie liczb

• liczby stałopozycyjne

• znak - moduł (0 - liczba dodatnia, 1 - ujemna)

Przykład 0 001011 odpowiada +11

1 010101 odpowiada - 21

moduł

znak

• uzupełnienie do 1

Przykład 0 001011 odpowiada +11

negacja wszystkich bitów

1 110100 odpowiada -11

0 010101 odpowiada +21

1 101010 odpowiada - 21

pozostała część zapisu

znak

• uzupełnienie do 2

Przykład 0 001011 odpowiada +11

negacja wszystkich bitów - uzupełnienie do 1

1 110100 odpowiada -11

+1

1 110101 uzupełnienie do 2

pozostała część zapisu

znak

0 011100 odpowiada +28

1 100011 uzupełnienie do 1

1 100100 odpowiada - 28 uzupełnienie do 2

pozostała część zapisu

znak

! W zapisie uzupełnienia do 1 wartość 0 reprezentują dwie postaci 0 000000 (+0) i 1 111111 (-0)

! Liczby dodatnie w zapisie uzupełnienie do 1 i do 2 są zgodne z zapisem znak moduł

! Najstarszy bit zapisu U1 i U2 wskazuje na znak liczby

• kodowanie ósemkowe {0,1,2,3,4,5,6,7} odpowiada {000,001,010,011,100,101,110,111}

• kodowanie szesnastkowe {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}

• kodowanie dwójkowo - dziesiętne (BCD, kody refleksyjne, kod Exess 3)

• liczby zmiennopozycyjne : zapis znak cecha mantysa

Kody dwójkowo dziesiętne

Liczba przedstawiana jest w postaci dwójkowo-dziesiętnej, tzn. każda pozycja dziesiętna zapisana jest w postaci binarnej (jeden z kodów dwójkowo - dziesiętnych)

Kod dziesiętny	Kod 8421	Kod Excess 3	Kod 2421
0	0 0 0 0	0 0 1 1	0 0 0 0
1	0 0 0 1	0 1 0 0	0 0 0 1
2	0 0 1 0	0 1 0 1	0 0 1 0
3	0 0 1 1	0 1 1 0	0 0 1 1
4	0 1 0 0	0 1 1 1	0 1 0 0
5	0 1 0 1	1 0 0 0	1 0 1 1
6	0 1 1 0	1 0 0 1	1 1 0 0
7	0 1 1 1	1 0 1 0	1 1 0 1
8	1 0 0 0	1 0 1 1	1 1 1 0
9	1 0 0 1	1 1 0 0	1 1 1 1

Najkorzystniejszy z punktu widzenia operacji sumowania jest kod Excess 3.

Przykład

2 3 5 0010 0011 0101 0101 0110 1000

1 7 2 0001 0111 0010 0100 1010 0101

4*0 7 0011 1010 0111 1010*0000 1101

korekta 0100*0000 - 11 +11 - 11

0100 0000 0111 0111 0011 1010

Kod Grey'a

Kolejne słowa kodowe różnią się jednym bitem (na jednej pozycji)

**0 0000

**1 0001

*11 0011

*10 0010

110 0110

111 0111

101 0101

100 0100

1100

1101

1111

1110

1010

1011

1001

1000

Kody detekcyjno - korygujące

Stosowane w celu zwiększenia odporności na zakłócenia przy przesyłaniu informacji cyfrowej na odległość.

Ze zbioru możliwych liczb binarnych (najczęściej o stałej długości) wybrana jest pewna grupa. Pozostałe liczby uważane są za zakazane.

Wyróżnia się:

• kody liniowe z wyróżnionymi grupami parzystości (np. kod z bitem parzystości) oraz

• kody ze stałą liczbą jedynek (najczęściej dwoma)

Dodawanie i odejmowanie liczb binarnych

Reguły wykonywania operacji dodawania i odejmowania

	znak - moduł	uzupełnienie do jedności	uzupełnienie do dwóch
A > 0 B > 0	dodać liczby i przepisać znak 0
A < 0 B < 0	dodać moduły - przepisać znak 1	dodać liczby wraz z bitem znaku przeniesienie z najstarszej pozycji dodać do wyniku	dodać liczby wraz z bitem znaku, a ewentualne przeniesienie z najstarszej pozycji pominąć
A*B<0	do modułu dodajnej dodać moduł uzupełnienia do jedności dodajnika; jeżeli wystąpi przeniesienie z najstarszej pozycji dodać je do sumy; a wynikowi nadać znak dodajnej; jeżeli brak przeniesienia z najstarszej pozycji wyznaczyć uzupełnienie do jedności sumy, a wynikowi nadać znak dodajnika; Uwaga: w dodawaniu nie bierze udziału bit znaku

Postać zmiennoprzecinkowa

Postać w systemie dziesiętnym:

A = m * 10 ^c

Przykład

0.453 * 10^-12 zapisana numerycznie 0.453E-12

Postać znormalizowana posiada następujące właściwości:

1₁₀ > m
0.1₁₀ oraz

c jest liczbą całkowitą

Postać w systemie dwójkowym:

A = m * 2 ^c

gdzie: 1₂ > m
0.1₂ oraz

W tym przypadku po przecinku (kropce) zawsze będzie występowała jedynka. Dla oszczędności można tą pozycję pominąć.

Postać binarna:

bit znaku

cecha w zapisie uzupełnienia do 2

1

mantysa (bity umieszczone po kropce)

Mnożenie i dzielenie liczb binarnych

Przesuwanie liczb ze znakiem

Przesuwanie liczb jest jednoznaczne z mnożeniem danej liczby przez 2ⁱ (gdy przesuwamy liczbę mnożoną przez 2ⁱ w  lewo o "i"  pozycji)  i dzieleniem, czy  też  mnożeniem  przez  2^-i  (gdy przesuwamy liczbę mnożoną przez 2^-i w prawo o "i" pozycji.)

Tabela 1. Przesuwanie liczb

Liczba dodatnia i   ujemna w kodzie ZM	znak bez zmian	przy przesunięciu  wszystkie dodane cyfry  są zerami
Liczba dodatnia i ujemna  w  postaci  kodu ZU1			przy przesunięciu   wszystkie cyfry dodane odpowiadają bitowi znaku
Liczba dodatnia i  ujemna  w postaci    kodu ZU2			przy przesunięciu w lewo dodajemy zera przy przesunięciu w  prawo dodajemy cyfry odpowiadające bitowi znaku

Ilustracja graficzna

Zapis znak moduł

PRZYKŁAD:

D(A) = (-10)₁₀

Kod Znak - Moduł ZM 

1.01010 * 2¹ = 1.10100 = -20

1.01010 * 2^-1 = 1.00101 = -5

Zapis uzupełnienie do jedności

PRZYKŁAD:

D(A) = (-10)₁₀

Kod  ZU1

1.10101 * 2¹ = 1.01011 = -20

1.10101 * 2^-1 = 1.11010 = -5

Zapis uzupełnienia do dwóch

PRZYKŁAD:

D(A) = (-10)₁₀

Kod ZU2

1.10110 * 2¹= 1.01100 = -2⁵ + 2³ + 2² = -32 + 8 + 4 = -20 

1.10110 * 2^-1= 1.11011 = -2⁵ + 2⁴ + 2³ + 2¹ + 2⁰ = -32 + 27 = -5

METODY MNOŻENIA LICZB W SYSTEMIE DWÓJKOWYM

Mnożenie można przeprowadzić wykorzystując metody:

1. metoda mnożenia bezpośredniego,

2. metoda Burksa - Goldsteine'a - von Neumanna,

3. I metoda Robertsona,

4. II metoda Robertsona,

5. metoda Bootha.

METODA MNOŻENIA BEZPOŚREDNIEGO

Jest stosowana do liczb zapisanych w kodzie ZM. Mnożenie w tej metodzie przebiega tak  jak  mnożenie  pisemne  liczb  dziesiętnych,  zatem jest ono zastąpione wielokrotnym dodawaniem odpowiednio przesuniętej mnożnej.

MNOŻENIE METODĄ BOOTH'A

  
I wariant metody Booth'a

Współczynnik
nie występuje we wzorze pierwszym, zatem jest równy 0.

Porównywanie par bitów mnożnika (w ZU2). Badamy ostatnie pary bitów (cyfr) mnożnika.

1. Jeżeli badana para jest kombinacją 1 0, to od iloczynu częściowego odejmujemy mnożną D(A) i przesuwamy wynik o jedno miejsce w prawo (*2^-1).

2. Jeżeli badana para jest odpowiednio parą 0 1, to dodajemy mnożną do iloczynu częściowego i przesuwamy cały wynik o jedno miejsce w prawo.

3. Jeżeli badana para jest parą o jednakowych cyfrach 0 0 lub 1 1, to wykonujemy tylko przesunięcie w prawo.

4. Jeżeli w skład wchodzi bit znakowy (znak), to nie wykonujemy przesunięcia.

PRZYKŁAD 1:

Dla I wariantu metody Booth'a

D(A) =
  = (0.00111)_ZM

D(B)=
= (1.00001)_ZM = (1.11111)_ZU2

Do liczby B na najmniej znaczącej pozycji dopisujemy 0, zatem:

D(B) = (1.111110)_ZU2

Badamy kolejne bity mnożnika (czyli kolejne bity liczby B):

1. para 1-0 - od iloczynu częściowego odejmujemy mnożną (iloczyn częściowy wynosi na początku 0), następnie przesuwamy wynik o jedno miejsce w prawo,

2. para 1-1 -  przesuwamy iloczyn częściowy o jedno miejsce w prawo,

3. para 1-1 -  przesuwamy iloczyn częściowy o jedno miejsce w prawo,

4. para 1-1 -  przesuwamy iloczyn częściowy o jedno miejsce w prawo,

5. para 1-1 -  przesuwamy iloczyn częściowy o jedno miejsce w prawo.

Krok 1		0 00000
		- 1 11001
		1 11001
		1 111001
Krok 2		1 1111001
Krok 3		1 11111001
Krok 4		1 111111001
Krok 5		1 1111111001

Wynik:

(1.1111111001)_ZU2 = (1.0000000111)_ZM =


PRZYKŁAD 2:

Dla I wariantu metody Booth'a

D(A) =
  = (1.00111)_ZM = (1.11001)

D(B) =
= (0.01001)_ZM = (0.01001)_ZU2

Do liczby B na najmniej znaczącej pozycji dopisujemy 0, zatem:

D(B) = (0.010010)_ZU2

Badamy kolejne bity mnożnika (czyli kolejne bity liczby B):

1. para 1-0 - od iloczynu częściowego odejmujemy mnożną (iloczyn częściowy wynosi na początku 0), następnie przesuwamy wynik o jedno miejsce w prawo,

2. para 0-1 - do iloczynu częściowego dodajemy mnożną, przesuwamy iloczyn częściowy o jedno miejsce w prawo,

3. para 0-0 -  przesuwamy iloczyn częściowy o jedno miejsce w prawo,

4. para 1-0 -  od iloczynu częściowego odejmujemy mnożną, przesuwamy iloczyn częściowy o jedno miejsce w prawo,

5. para 0-1 - do iloczynu częściowego dodajemy mnożną, przesuwamy iloczyn częściowy o jedno miejsce w prawo.

Krok 1		0 00000
		- 0 00111
		0 00111
		0 000111
Krok 2		+1 11001
		1 111001
		1 1111001
Krok 3		1 11111001
Krok 4		- 0 00111
		0 00110001
		0 000110001
Krok 5		+1 11001
		1 111000001
		1 1111000001

Wynik:

(1.1111000001)_ZU2 = (1.0000111111)_ZM =


 II wariant metody Booth'a:

1. Przesuwamy mnożną o jedno miejsce w prawo (uzyskujemy A/2 - “A - pół”).

2. Zbadamy ostatni bit mnożnika, jeżeli jest on równy 1, to dodajemy mnożną do iloczynu częściowego, który jest równy zeru na początku mnożenia, jeżeli ostatni   bit mnożnika jest równy 0, to nie wykonujemy żadnego działania.

3. Przesuwamy iloczyn częściowy o jedno miejsce w prawo.

4. Przesuwamy mnożnik o jedno miejsce w prawo ( przejście do kolejnego badania  bitu mnożnika). Jeżeli badany bit jest bitem znakowym b₀, to wtedy gdy jego wartość wynosi 1 odejmujemy mnożną od iloczynu częściowego, zaś gdy jest on równy 0 nie wykonujemy żadnego działania.

5. Uzyskany iloczyn częściowy przesuwamy o jedno miejsce w lewo (powrót do A), wynik jest w postaci ZU2.

PRZYKŁAD:

Dla II wariantu metody Booth'a

D(A) =
  = (0.11001)_ZM

D(B) =
  = (1.10011)_ZM = (1.01100)_ZU1 = (1.01101)_ZU2

Przesuwamy mnożną o jedno miejsce w prawo - uzyskanie wartości “A - pół”:




Badamy kolejne bity mnożnika począwszy od ostatniego:

1. bit = 1 - dodajemy mnożną (“A-pół”) do iloczynu częściowego (na początku równego 0), a następnie przesuwamy otrzymany iloczyn częściowy o jedno miejsce w prawo,

2. bit = 0 - nie wykonujemy żadnej operacji, przesuwamy otrzymany iloczyn częściowy o jedno miejsce w prawo,

3. bit = 1 - dodajemy mnożną do iloczynu częściowego, przesuwamy otrzymany iloczyn częściowy o jedno miejsce w prawo,

4. bit = 1 - dodajemy mnożną do iloczynu częściowego, przesuwamy otrzymany iloczyn częściowy o jedno miejsce w prawo,

5. bit = 0 - nie wykonujemy żadnej operacji, przesuwamy iloczyn częściowy o jedno miejsce w prawo,

6. bit =1 - badany bit jest bitem znakowym i jest równy 1 dlatego wystąpi tzw. poprawka - odejmujemy mnożną od iloczynu częściowego,

7. otrzymany wynik przesuwamy o jedno miejsce w lewo.

Krok 1		0 000000
		+0 011001
		0 011001
		0 0011001
Krok 2		0 00011001
Krok 3		+0 011001
		0 01111101
		0 001111101
Krok 4		+0 011001
		0 101000101
		0 0101000101
Krok 5		0 00101000101
Krok 6		-1 100111
		1 11000100101
		1 1000100101

  Wynik: (1.1000100101)_ZU2 = (1.0111011011)_ZM = 


Uwaga:

Mnożymy nie tylko ułamki!

Jeżeli chcemy pomnożyć ułamki niewłaściwe to możemy zapisać je w postaci mantysy i cechy i wykonujemy mnożenie mantys i dodawanie cech, ostateczny wynik to mantysa * 2^cecha.

Innym rozwiązaniem jest ustalenie pozycji części ułamkowych mnożnej i mnożnika. Wówczas w ostatecznej postaci wyniku należy wyznaczyć dodatkowo położenie części ułamkowej wyniku.

DZIELENIE LICZB BINARNYCH

 Dzielenie można przeprowadzić wykorzystując następujące metody:

1. metoda porównawcza,

2. metoda restytucyjna,

3. metoda nierestytucyjna,

Metoda porównawcza - jest stosowana w zapisie znak moduł (ZM) i gdy jest spełniony warunek A<B, gdzie:

A - dzielna

B - dzielnik

r₀ - reszta początkowa

R_n - reszta z dzielenia

r_n - n - ta reszta częściowa

Q - iloraz uzyskany w algorytmie o bitach q_i.

Metoda ta polega na porównywaniu dzielnika z n - tą resztą.

•   Jeżeli dzielnik jest mniejszy od r_n-tej reszty r_n=>B, to odejmujemy dzielnik od przesuniętej n - tej reszty, a bit ilorazu q_i = 1.

•   Jeżeli n - ta reszta jest mniejsza od dzielnika r_n<B, to kolejny bit ilorazu q_i = 0. Następnie przesuwamy wynik o jedno miejsce w lewo. Otrzymaną resztę częściową porównujemy z dzielnikiem.

Uwaga: Wynikiem dzielenia jest iloraz Q o bitach q₀q₁..q_i.W pierwszym kroku porównujemy resztę początkową r₀ z dzielnikiem, gdzie r₀ - to D(A) zapisana na tylu pozycjach co D(B).

PRZYKŁAD:

Dla metody porównawczej

A=
= (1.0000011)_ZM

B  = 
= (0.1001)_ZM

Warunek A<B jest spełniony; porównujemy kolejne reszty częściowe z modułem dzielnika:

Krok I: r0 A<B		.0000011
		.0000110
Krok II: r1 <B	r1 =	.0000110	q1 =0
		.0001100
Krok III: r2 <B	r2 =	.0001100	q2 =0
		.0011000
Krok IV: r3 <B	r3 =	.0011000	q3 =0
		.0110000
Krok V: r4 <B	r4 =	.0110000	q4 =0
		.1100000
Krok VI: r5 >B	r4 =	.1100000	q3 =1
		-.1001000
		.0011000
		.0110000	r6

reszta z dzielenia R_n wyraża się wzorem:

R_n =


R_n = 0.011 * 10^1.110 (uwaga! wynik jest zapisany binarnie)

Bit znaku q₀ = a₀ A b₀, czyli q₀ = 1, bo a₀ = 1, b₀ = 0

Ostateczny iloraz Q wynosi: Q = q₀ q₁ q₂...q_n =  1.00001

Metoda restytucyjna -

to metoda dzielenia dwóch liczb zapisanych w kodzie znak moduł (ZM) i gdy |A|<|B|.

Algorytm metody restytucyjnej różni się od metody porównawczej tym, że zawsze następuje odejmowanie dzielnika od i - tej reszty. Jeżeli otrzymana reszta jest większa od zera, to kolejny bit ilorazu jest równy 1, jeżeli jest mniejsza od zera, to kolejny bit ilorazu jest równy 0. Bez względu na znak reszty z odejmowania przesuwamy resztę o jedno miejsce w lewo. Dla reszty ujemnej z powrotem dodajemy dzielnik, zanim przesuniemy wynik w lewo.

Metoda nierestytucyjna -

to metoda dla dzielenia dwóch liczb zapisanych w kodzie ZU2. Dzielna A i dzielnik B są ułamkami w postaci znormalizowanej oraz wymagane jest by był spełniony warunek |A|<|B|.

Metoda ta polega na badaniu znaku dzielnika i kolejnej reszty częściowej. Jeżeli znaki są zgodne to odejmujemy dzielnik od przesuniętej w lewo kolejnej reszty częściowej. Jeżeli znaki ich są różne to dodajemy dzielnik do przesuniętej w lewo kolejnej reszty częściowej. Przy zgodnych bitach znakowych dzielnika i reszty bit ilorazu jest równy 1, a dla znaków przeciwnych jest równy 0. Do otrzymanego wyniku dodajemy poprawkę równą: -1+2^-n, gdzie n - oznacza n - tą resztę z dzielenia.

PRZYKŁAD:

  Dla metody nierestytucyjnej





1.0110000 !!!!

Warunek
jest spełniony:

r0	1.1100111	q0 = 1
	1.100111
	- 1.0110000 (+0.1010000)
r1	0.0011110	q1 = 0
	0.01111
	+1.0110000
r2	1.11011	q2 = 1
	1.1011
	-1.0110000 (+0.1010000)
r3	0.0101	q3 = 0
	0.101
	+1.0110000
	0.000

nastąpiło wyzerowanie reszty częściowej. Koniec obliczeń.

Wynik:  1.010;

Do wyniku dodajemy poprawkę, która wynosi:

-1 + 2^-n, gdzie n jest to nr ostatniej reszty dzielenia, zatem:

-1 + 2^-n = (1.0001)_ZU2

Q = 1.010 +1.0001 = (0.0101)_ZU2 = +


Algorytmy

W sposób nieformalny możemy określić algorytm jako ściśle określoną procedurą obliczeniową, która dla poprawnych danych wejściowych „wytwarza” żądane dane wyjściowe nazywane wynikiem działania algorytmu. Algorytm jest więc ciągiem kroków obliczeniowych prowadzących do przekształcenia danych wejściowych w wyjściowe.

Inaczej, algorytm można potraktować jako sposób rozwiązania konkretnego problemu obliczeniowego. Postawienie problemu polega na sprecyzowaniu wymagań dotyczących relacji między danymi wejściowymi i wyjściowymi, a algorytm opisuje właściwą procedurę obliczeniową, która zapewnia, że ta relacja zostaje osiągnięta.

Algorytm jest poprawny, gdy dla każdego egzemplarza problemu algorytmu zatrzymuje się i daje poprawny wynik. Mówimy wtedy, że poprawny algorytm „rozwiązuje” zadany problem obliczeniowy. Algorytm niepoprawny może się nigdy nie zatrzymać albo po zatrzymaniu dać wynik zły. Niepoprawne algorytmy mogą być jednak użyteczne, jeśli ich błędne działanie może być kontrolowane.

Algorytm może być przedstawiany w postaci programu komputerowego albo zrealizować sprzętowo. Jedynym wymaganiem jest precyzja opisu wynikającej z niego procedury obliczeniowej.

Złożoność obliczeniowa algorytmów

Algorytmy:

• dla problemów decyzyjnych,

• dla problemów optymalizacyjnych.

Problemy decyzyjne - problemy, na które można dać odpowiedź tak lub nie.

Np. problemy z dziedzin: teorii liczb, teorii grafów, teorii automatów

Problemy optymalizacyjne - ekstremalizacja pewnej funkcji celu.

W sensie „natury obliczeniowej” można badać w ten sam sposób co problemy decyzyjne. Problem optymalizacyjny można sprowadzić do problemu decyzyjnego. Taki problem decyzyjny nie jest obliczeniowo trudniejszy niż odpowiadający mu problem optymalizacyjny.

Jeśli problem decyzyjny jest obliczeniowo „trudny” (NP.-zupełny), to trudny jest również problem optymalizacyjny.

Teoria złożoności obliczeniowej

W odniesieniu do problemów decyzyjnych.

Pytanie: czy dla rozważanego problemu istnieje w ogóle jakiś rozwiązujący go algorytm (tzn. procedura pozwalająca dać odpowiedź tak lub nie).

Odpowiedź, to stwierdzenie czy problem jest rozstrzygalny czy nierozstrzygalny.

Postulat rozróżniania algorytmów lepszych i gorszych z obliczeniowego punktu widzenia: czas i zajętość pamięci.

Istnieje wiele algorytmów, dla których nie udało się podać „dobrych” algorytmów, ale sprowadzają się te problemy do siebie nawzajem, tak że znając rozwiązanie jednego z nich, można w wielomianowym czasie skonstruować rozwiązanie innego.

Definicja

Przez problem Π rozumiany będzie zbiór parametrów, które nie muszą mieć nadanych wartości, oraz zdanie określające właściwości jakie powinno mieć rozwiązanie tego problemu.

Ustalając wartości wszystkich parametrów problemu Π otrzymamy konkretny problem (instalację) I.

Zbiór wszystkich konkretnych problemów oznaczamy przez D_Π .

Dane konkretnego I є D_Π , kodowane są za pomocą skończonego łańcucha x(I) symboli należących do z góry określonego alfabetu Σ zgodnie z ustalonymi regułami kodowania.

Rozmiar konkretnego problemu N(L), to długość łańcucha danych x(I).

Reguły kodowania powinny spełniać następujące postulaty:

1. Łańcuch symboli kodujących dane konkretnego problemu nie może zawierać nadmiarowych symboli,

2. Liczby występujące w danych powinny być zapisane dwójkowo lub przy użyciu dowolnej innej ustalonej podstawie liczenia większej od 1.

Można przyjąć każdą „rozsądną” regułę kodowania, która nie powoduje wykładniczego wzrostu rozmiaru kodowania konkretnego problemu w stosunku do innych reguł kodowania.

W praktyce dogodne jest wyrażanie rozmiaru problemu za pomocą jednego parametru, określającego liczbę elementów zbioru charakterystycznego dla danych rozważanego konkretnego problemu. Np. dla określenia maksymalnego przepływu w sieciach - liczba wierzchołków w sieci.

Problemowi decyzyjnemu Π i regule kodowania e odpowiada język L(Π,e) = {x(I) є Σ*: I є D_Π ∧ Σ jest alfabetem używanym przez e ∧ odpowiedź na I brzmi „tak”}.

Σ* - zbiór wszystkich skończonych łańcuchów symboli należących do Σ

Rozwiązania problemu Π odpowiada rozpoznanie języka L(Π,e)

Algorytm rozwiązuje problem Π, jeśli znajduje rozwiązanie dla każdego konkretnego problemu I є D_Π

Definicja

Funkcja f(k) jest rzędu g(k), co zapisuje się O(g(k)), jeśli istnieje taka stała c, że | f(k) | <= c * | g(k) |, dla wszystkich wartości k

Definicja

Funkcja złożoności obliczeniowej algorytmu A rozwiązującego problem Π będziemy rozumieli funkcję złożoności czasowej przyporządkowującą każdej wartości rozmiaru konkretnego problemu I є D_Π maksymalną liczbę elementarnych kroków maszyny cyfrowej potrzebnych do rozwiązania za pomocą algorytmu A konkretnego problemu o tym rozmiarze, tzn. funkcję

f_A(N(I)) = max{t: t jest liczbą elementarnych kroków niezbędnych dla rozwiązania konkretnego problemu I є D_Π ∧ |x(I)| = N(I)}

Można udowodnić, że wybór konkretnej reguły kodowania i modelu maszyny cyfrowej nie ma wpływu na rozróżnienie między algorytmami wielomianowymi i wykładniczymi.

Definicja

Algorytmem wielomianowym nazywamy algorytm, którego funkcja złożoności obliczeniowej jest O(p(k)), gdzie p jest pewnym wielomianem, a k rozmiarem rozwiązywanego konkretnego problemu.

Każdy algorytm, którego funkcja złożoności nie może być tak ograniczona, nazywa się algorytmem wykładniczym. !Funkcja złożoności obliczeniowej tych algorytmów nie musi być funkcją wykładniczą!

Algorytmy wielomianowe - efektywne

Algorytmy wykładnicze - nie efektywne

Klasy złożoności obliczeniowej

Uogólnione modele maszyn cyfrowych:

• maszyna o dostępie swobodnym RAM - random acces machine

• maszyna Turinga




Rysunek 1. Podstawowy model maszyny RAM

Maszyna Turinga

Maszyna Turinga jest prostym urządzeniem algorytmicznym, uderzająco prymitywnym w porównaniu z dzisiejszymi komputerami i językami programowania, a jednak na tyle efektywnym, że pozwala na wykonanie nawet najbardziej złożonych algorytmów. Maszyna Turinga jest mechanizmem powstałym w wyniku ciągu uproszczeń: danych, sterowania nimi oraz uproszczeń podstawowych operacji. Maszynę tą wymyślił w roku 1936 brytyjski matematyk A.M.Turing

Wprowadzenie takiego prostego i stosunkowo powolnego modelu obliczeń ma swoje uzasadnienie. Używać go bowiem będziemy wtedy, gdy problem będzie miał złożoność obliczeniową „wyższego rzędu”.

Zasady zapisu algorytmów w Maszynie Turinga:

Zasada 1: Upraszczanie danych

Każdy element danych używany w algorytmie, czy to będą dane wejściowe, wyjściowe czy wartości pośrednie, można traktować jako ciąg symboli, czyli napis. Liczba całkowita nie jest niczym innym, jak ciągiem cyfr, liczba ułamkowa zaś ciągiem cyfr, który może zawierać kropkę. Prostej linearyzacji mogą podlegać zarówno słowa jak i teksty, które są ciągiem symboli składającym się z liter, znaków przestankowych i odstępów. Wszystkie obiekty a nawet najbardziej skomplikowane struktury danych możemy łatwo zakodować, traktując je cały czas symbolicznie, jako liczby, słowa lub teksty.

Liczba różnych symboli jest skończona i ustala się ją zawczasu. Każdą interesującą nas jednostkę danych możemy więc zapisać na jednowymiarowej taśmie o nieograniczonej długości składającej się z ciągu kwadratów, z których każdy zawiera pojedynczy symbol z pewnego skończonego alfabetu. Alfabet składa się z rzeczywistych symboli, które same tworzą jednostki danych, oraz specjalny symbol pusty wskazujący brak informacji. Taśma zawsze będzie zawierać skończoną znaczącą porcję danych, otoczoną z każdej strony nieskończonym ciągiem symboli pustych.

Zasada 2: Upraszczanie sterowania

Jedną z najważniejszych rzeczy dla uproszczenia sterowania jest skończoność tekstu algorytmu. Procesor może znajdować się tylko w jednym ze skończonej liczby miejsc w tym tekście. Wystarczy użyć więc prymitywnego mechanizmu zawierającego pewien rodzaj układu sterowania, obejmującego skończenie wiele stanów. Stany układu będziemy traktować jako służące do kodowania miejsc w algorytmie, więc poruszanie się w nim modelujemy zmianą stanu. W każdym punkcie wykonywania algorytmu miejsce, które ma być odwiedzone jako następne, zależy od miejsca, w którym się znajdujemy, tak więc następny stan układu zależy od jego bieżącego stanu. Zmiana stanu zależy od danych oraz od bieżącego stanu. W danej chwili czasu może być czytany tylko pojedynczy symbol, więc dopuszcza się badanie tylko jednego kwadratu na raz. Mechanizm zmienia stan w zależności od wartości czytanego symbolu i swojego stanu bieżącego, przechodząc do nowego stanu. Mechanizm porusza się po taśmie przesuwając się wzdłuż po jednym kwadracie, a kierunek ruchu zależy od bieżącego stanu skrzyni biegów i bieżącego symbolu.

Opisane ograniczenia upraszczają sterowanie w algorytmie. Powstały mechanizm jest prostym mechanizmem mogącym być w jednym ze skończonej liczby stanów, poruszając się wzdłuż taśmy po jednym kwadracie. Mechanizm ten działa wyznaczając nowe stany i kierunki jako funkcje stanu bieżącego i bieżącego symbolu.

Zasada 3: Upraszczanie podstawowych operacji

Poprawność działania algorytmów zależy od poprawnego manipulowania danymi, przekształcania ich, wymazywania, czytania lub zapisywania, stosowania do nich operacji arytmetycznych lub tekstowych. Do zmiany stanu i poruszania się o jeden kwadrat w lewo lub w prawo omawiany mechanizm jest wyposażony w możliwości przekształcania w określonym stanie pewnego widzianego symbolu w jeden ze skończonej liczby dostępnych symboli.

Podstawowy model maszyny Turinga

Maszyna Turinga jest z przedstawionych modeli najprostszym modelem matematycznym komputera.

Podstawowy model przedstawiony na rysunku 2 ma skończone sterowanie, taśmę wejściową podzieloną na komórki (kwadraty) oraz głowicę taśmy, mogącą obserwować w dowolnej chwili tylko jedna komórkę taśmy. Taśma ma komórkę położoną najbardziej na lewo, ale jest prawostronnie nieskończona. Każda z komórek taśmy może zawierać dokładnie jeden symbol z skończonego alfabetu symboli. Przyjmuje się umownie, że ciąg symboli wejściowych umieszczony jest na taśmie począwszy od lewej, pozostałe komórki ( na prawo od symboli wejściowych) są wypełnione specjalnym symbolem taśmowym noszącym nazwę symbolu pustego.

Maszyna Turinga składa się z następujących elementów:

• skończonego alfabetu symboli;

• skończonego zbioru stanów;

• nieskończonej taśmy z zaznaczonymi kwadratami, z których każdy może zawierać pojedynczy symbol;

• ruchomej głowicy odczytująco - zapisującej, która może wędrować wzdłuż taśmy przesuwając się na raz o  jeden kwadrat

• diagramu przejść między stanami, zawierającego instrukcje, które powodują, że zmiany następują przy każdym zatrzymaniu się.




Rysunek 2. Podstawowy model maszyny Turinga

W zależności od obserwowanego symbolu przez głowicę taśmy oraz stanu sterowania skończonego, maszyna Turinga w pojedynczym ruchu:

• zmienia stan,

• wpisuje symbol w obserwowanej komórce taśmy, zastępując symbol tam wpisany,

• przesuwa głowicę o jedną komórkę w prawo lub w lewo.

 Definicja wielotaśmowej maszyny Turinga

Struktura wielotaśmowej maszyny Turinga przedstawiona na rysunku 3. zawiera k taśm prawostronnie nieskończonych. Każda taśma podzielona jest na klatki. W każdej klatce może być umieszczony jeden symbol ze skończonego alfabetu, zwanego alfabetem symboli roboczych. Każda taśma posiada głowicę, która może poruszać się po taśmie oraz czytać lub pisać na niej symbole robocze. Operacje wielotaśmowej maszynyTuringa wyznaczone są przez pewien skończony zbiór stanów i sterowanie zawsze jest w jednym z takich stanów (stany te można traktować jako numery instrukcji w programie maszyny Turinga




Rysunek 3. Model wielotaśmowej maszyny Turinga

Formalnie maszynę Turinga (MT) nazywamy:

M = <Q,
,
, ð, q₀, B, F >

gdzie:

Q - jest skończonym zbiorem stanów,

Γ - skończony zbiór dopuszczalnych symboli taśmowych,

B - symbol pusty należący do
,

Σ - podzbiór
nie zawierający B, zwany zbiorem symboli wejściowych,

ð - funkcja następnego ruchu, będąca odwzorowaniem

Q x Γ Q x Γ x { L, P } dla maszyny jednotaśmowej i

Q x Γ^k Q x (Γ x { L, P })^k dla maszyny k - taśmowej.

gdzie:

L- oznacza ruch w lewo

P- ruch w prawo,

q₀- stan początkowy,

F ⊆ Q - zbiór stanów końcowych

Działanie maszyny Turinga przedstawia się jako diagram przejść między stanami lub jako tabelę stanów, które to pojęcia zostały omówione poniżej.

Diagram przejść między stanami zawiera instrukcje, które powodują, że zmiany następują po każdym zatrzymaniu się. Diagram przejść jest grafem skierowanym, którego wierzchołki reprezentują stany. Krawędź prowadząca ze stanu s do stanu t nazywa się przejściem i etykietuje się ją kodem postaci (a/b, kierunek) gdzie a i b są symbolami,
a kierunek określa ruch głowicy w prawo bądź w lewo. Część a etykiety jest wyzwalaczem przejścia, a część <b, kierunek> akcją:



( a / | b , kierunek )

wyzwalacz | akcja

Dla układu (k+1) - elementowego, składającego się ze stanu i k symboli roboczych, funkcja przejścia określa nowy stan i k par, z których każda określa nowy symbol roboczy i kierunek ruchu głowicy. Przypuśćmy, że δ(q,a₁,a₂,...,a_k) = (q',(a'₁,d₁)(a'₂,d₂) … (a'_k,d_k)) oraz maszyna Turinga jest w stanie q, a głowica taśmy o numerze i ustawiona jest nad symbolem a_i, dla 1<= i<=k. Wówczas w jednym kroku maszyna Turinga przechodzi do stanu q' , zmienia symbole a_i na a_i' oraz przesuwa głowicę taśmy o numerze i w kierunku d_i, dla 1<= i<=k.

W czasie swego działania maszyna Turinga, kiedy znajdzie się w stanie s i odczytywanym symbolem będzie a to nastąpi wpisanie w to miejsce b i przesunięcie o jedno pole w kierunku kierunek. Fragment przykładowego diagramu przejść przedstawia rysunek 4.




Rysunek 3. Fragment grafu przejść między stanami dla maszyny Turinga

Aby zapobiec niejednoznaczności, co do następnego ruchu maszyny (tj. aby jej zachowanie było deterministyczne), z jednego stanu nie wychodzą dwa przejścia z tym samym wyzwalaczem. Jeden ze stanów w diagramie jest zaznaczony skierowaną do niego strzałką opatrzoną etykietą start i jest nazywany stanem początkowym. Podobnie stany z których nie wychodzą już żadne przejścia, nazywa się stanami końcowymi.

Tabela stanów - która również obrazuje przejścia między stanami maszyny Turinga zawiera wszystkie symbole
z skończonego alfabetu wejściowego jak również wszystkie stany w których może znaleźć się maszyna Turinga. Każde pole tabeli określa:

1. dla danego stanu q_i kolejny stan q_i+1

2. symbol, który ma być zapisany na taśmie

3. kierunek (L / P) dla ruchu głowicy

q0

q1

q2

q3

q4

Φ

q1

q0

q5

q4

q5

B

L

B

L

C

P

B

P

C

L

A

q0

q4

q6

q3

q7

Φ

P

C

L

B

L

A

P

Φ

L

B

q1

q2

q3

q2

q3

A

L

C

P

D

P

Φ

L

A

L

C

q0

q2

q0

q1

q4

Φ

P

Φ

L

Φ

L

D

P

D

P

Rysunek 4. Fragment stanów maszyny Turinga

Zarówno dla tabeli stanów jak i grafu przejść wyróżnia się specyficzne stany będące odpowiednio stanem początkowym i stanem (bądź stanami ) końcowym, zwane też stanami biernymi. Zakłada się, że maszyna rozpoczyna swoje działanie od swego stanu początkowego p₀ na pierwszym od lewej niepustym kwadracie taśmy i postępuje krok po kroku zgodnie z narzuconym ruchem, zaś kończy działanie po osiągnięciu stanu końcowego.

Teza Churcha-Turinga

Różnorodność zadań stawianych przed maszyną Turinga postawiło pytanie :
Jakie problemy można rozwiązać odpowiednio zaprogramowaną maszyną Turinga (oczywiście pomijając czas) ? 

Otóż okazuje się że:

Maszyny Turinga potrafią rozwiązać każdy efektywnie rozwiązywalny problem algorytmiczny.

Mówiąc inaczej, każdy problem algorytmiczny dla którego możemy znaleźć algorytm dający się zaprogramować w pewnym dowolnym języku, wykonujący się na pewnym dowolnym komputerze, nawet na takim, którego jeszcze nie zbudowano, ale można zbudować, i nawet na takim, który wymaga nieograniczonej ilości czasu i pamięci dla coraz większych danych, jest także rozwiązywalny przez maszynę Turinga. To stwierdzenie jest jedną z wersji tzw. tezy Churcha-Turinga (Alonz Church, Alan M. Turing), którzy doszli do niej niezależnie w połowie lat trzydziestych. Istotną sprawą jest aby uświadomić sobie, że teza Churcha-Turinga jest tezą a nie twierdzeniem, zatem nie może być dowiedziona w matematycznym tego słowa znaczeniu. Jedno z pojęć, do której się odwołuje, jest bowiem nieformalnym i nieprecyzyjnym, pojęciem “efektywnej obliczalności”.

Skąd biorą się przesłanki aby akceptować tezę Churcha-Turinga, szczególnie, jeśli nie można jej udowodnić?

Już od wczesnych lat trzydziestych badacze proponowali różne modele komputera absolutnego, wszechpotężnego, lub uniwersalnego. Chciano bowiem sprecyzować ulotne pojęcie “efektywnej obliczalności”. Na długo przedtem nim wymyślono pierwszy komputer, Turing zaproponował swoją maszynę, a Church wymyślił matematyczny formalizm funkcji zwany rachunkiem lambda (jako podstawa języka programowania Lisp). Mniej więcej w tym samym czasie Emil Post zdefiniował pewien typ systemu produkcji do manipulowania symbolami, a Stephen Kleene zdefiniował klasę obiektów zwanych funkcjami rekurencyjnymi.
Wszyscy oni próbowali użyć tych modeli do rozwiązania wielu problemów algorytmicznych, do których znane były “efektywnie wykonalne” algorytmy.

Przełomowym zdarzeniem istotnym dla wszystkich tych modeli stało się udowodnienie, iż są one równoważne w kategoriach problemów algorytmicznych, które rozwiązują. I ten fakt jest dziś nadal prawdziwy nawet dla najsilniejszych modeli, jakie można sobie wyobrazić.

Z tezy Churcha-Turinga wynika, że najpotężniejszy superkomputer z wieloma najwymyślniejszymi językami programowania, interpretatorami, kompilatorami i wszelkimi zachciankami, nie jest potężniejszy od domowego komputera z jego uproszczonym językiem programowania. Mając ograniczoną ilość czasu i pamięci mogą obydwa rozwiązać te same problemy algorytmiczne, jak również żaden z nich nie może rozwiązać problemów nierozstrzygalnych (nieobliczalnych). Schematycznie rozstrzygalność problemów przedstawia rysunek 5.

Problem algorytmiczny, do którego nie ma żadnego algorytmu jest nazywany nieobliczalnym; jeśli to problem decyzyjny nazywa się nierozstrzygalnym. Dla problemów tego typu w żaden sposób nie można skonstruować algorytmu, wykonywanego na dowolnym komputerze, bez względu na ilość wymaganego czasu i pamięci, który mógłby je rozstrzygnąć.




Rysunek 5. Sfera problemów algorytmicznych.

Najbardziej naturalnym sformułowaniem problemu, który ma być rozwiązany przez Deterministyczną Maszynę Turinga jest sformułowanie w postaci problemu decyzyjnego

Klasę P tworzą wszystkie problemy decyzyjne, które w co najwyżej w wielomianowym czasie rozwiązuje DTM.

Istnieje liczna klasa problemów, dla których nie są znane algorytmy wielomianowe, lecz dla których można w co najwyżej wielomianowym czasie zweryfikować pozytywną odpowiedź.

Dla bardziej formalnego ujęcia rozważań posłużymy się pojęciem Niedetrministycznej Maszyny Turinga (NDTM).

Przez NDTM będziemy rozumieć DTM wyposażoną dodatkowo w moduł generujący. Program NDTM jest określony w ten sam sposób co dla DTM.

Wykonanie programu przez NDTM dla łańcucha x(I), stanowiącego dane rozwiązywanego konkretnego problemu I różni się od wykonania programu przez DTM, gdyż przebiega w dwóch etapach.

Etap I: moduł generuje w całkowicie dowolny sposób i zapisuje na taśmie w komórkach -1, -2, ... , łańcuch S symboli ze zbioru Γ.

Etap 2: NDTM sprawdza, w taki sam sposób, w jaki jest wykonywany program przez DTM, czy wygenerowany łańcuch S spełnia warunki określone w pytaniu konkretnego problemu I. (Dla konkretnego problemu I może istnieć wiele takich łańcuchów S.)

ODMIANY MODELU MASZYNY TURINGA

Działanie maszyny Turinga można ograniczyć na wiele sposobów nie zmniejszając jednak klasy problemów, które rozwiązuje. Można na przykład żądać, żeby dane wejściowe pozostały nienaruszone i żeby przy zatrzymaniu taśma zawierała tylko dane i wyniki otoczone symbolami pustymi. Można zdefiniować maszynę Turinga z taśmą, która jest nieskończona tylko z prawej strony, a dane są zapisywane na taśmie od lewego skraju. Obie odmiany maszyny mogą rozwiązywać dokładnie te same problemy co model podstawowy i wobec tego nie są od niego słabsze. Podobnie dodanie maszynom dowolnie silnej własności nie powoduje żadnego rozszerzenia klasy rozwiązywalnych problemów. W żadnym z rozszerzeń nie da się rozwiązać problemu nie rozwiązywalnego.

Maszyna, która może symulować działanie dowolnej maszyny Turinga na dowolnych danych nazywa się uniwersalną maszyną Turinga. Uniwersalna maszyna Turinga U akceptuje jako dane opis dowolnej maszyny Turinga M, po którym jest umieszczony skończony ciąg X traktowany jako dane dla maszyny M. Następnie symuluje ona akcje maszyny M na taśmie, na której znajdują się dane X otoczone symbolami pustymi. Jeśli maszyna M nie może zatrzymać się na taśmie, to także nie może zatrzymać się maszyna U, jeśli maszyna M zatrzyma się to zatrzyma się również maszyna U. Obie taśmy będą wyglądać dokładnie tak samo po zakończeniu działania.

Ograniczenia narzucone na maszyny Turinga nie pomniejszają uniwersalności modelu. Oczywiście nie wszystkie ograniczenia mają tę właściwość. Maszyny, od których wymaga się, aby zatrzymywały się zaraz po uruchomieniu lub nie zatrzymywały się w ogóle , nie dokonają wiele. Istnieje również inny sposób ograniczenia modelu maszyny Turinga. Wiąże się on z ograniczeniem samego mechanizmu maszyny. Jedną z najbardziej interesujących degeneracji otrzymuje się ograniczając poruszanie się maszyny Turinga na taśmie tylko do jednego kierunku (jednokierunkowa maszyna Turinga), np. w prawo. Wynikiem jest urządzenie zwane automatem skończenie stanowym lub automatem skończonym. Automat skończony rozwiązujący problem decyzyjny działa następująco. Przechodzi wzdłuż podanej sekwencji symbol po symbolu zmieniając stan w wyniku stanu bieżącego i nowego symbolu z taśmy. Po osiągnięciu końca sekwencji zatrzymuje się, a odpowiedź zależy od tego, czy automat zatrzymał się w stanie TAK czy NIE. Automat skończony można przedstawić jako diagram przejść między stanami, tak jak dla maszyny Turinga, teraz jednak baz części <b, kierunek> w etykiecie; przejście jest etykietowane symbolem, który je wyzwala. 

Maszyna Turinga może być użyta do rozpoznawania języków. Alfabet symboli roboczych maszyny zawiera również alfabet języka, zwany alfabetem symboli wejściowych. Ponadto zawiera symbol pusty B oraz być może jeszcze jakieś inne symbole robocze. Początkowo na pierwszej taśmie k-taśmowej maszyny umieszczono słowo nad alfabetem wejściowym, po jednym symbolu na klatkę, poczynając od pierwszej klatki. Wszystkie pozostałe klatki tej pierwszej taśmy zawierają symbol pusty. Pozostały taśmy maszyny Turinga są całkiem puste. Słowo wejściowe jest akceptowane przez maszynę Turinga wtedy i tylko wtedy, gdy startując od stanu początkowego i od położenia głowic wszystkich taśm na skrajnie lewej klatce, po skończonej liczbie kroków maszyna przechodzi do stanu końcowego. Język akceptowany przez maszynę Turinga jest zbiorem wszystkich słów w ten sposób akceptowanych.

Przykłady zadań rozwiązanych za pomocą maszyny Turinga

Przykład 1:

Maszyna Turinga bada problem polegający na sprawdzeniu, czy dana liczba jest parzysta

Wystarczy sprawdzić, czy w zapisie dwójkowym liczby ostatnią pozycją jest 0.

Określamy program DTM rozwiązujący ten problem przyjmując:

Γ = {0,1,b}, Σ = {0,1} , Q = {q₀,q₁,q_n,q_p} i funkcję przejść pokazaną w tabeli:

q\s	0	1	b
q0	(q0,0,P)	(q0,1,P)	(q1,B,L)
q1	(qp,B,L)	(qn,B,L)	(q0,B,L)

Przykład 2

Maszyna Turinga bada czy dane słowo jest palindromem.

Maszyna Turinga badająca czy dane słowo z alfabetu wejściowego
={a, b, c} jest palindromem (to znaczy słowem, które czyta się tak samo z obu stron). Dodatkowo przyjmuje się, że pojedynczy symbol jest palindromem. Wprowadza się dodatkowo 2 stany akceptacji SA i nieakceptacji SN. Przejście do stanu akceptacji oznacza, że dane słowo jest palindromem, zaś przejście do stanu nieakceptacji oznacza, że słowo nie jest palindromem. Tabela przejść miedzy stanami wygląda następująco:

q0

q1

q2

q3

q4

q5

q6

q7

q8

q9

q10

q11

Ø

q0  ø, P

q2  ø, L

q10  ø, P

q0  ø, P

q5  ø, L

q10  ø, P

q0  ø, P

q8  ø, L

q10  ø, P

q0  ø, P

SA

SN

a

q1  ø, P

q1  a, P

q3  ø, L

q3  a, L

q4  a, P

q11  a, P

q6  a, L

q7  a, P

q11  a, P

q9  a, L

S.A.

SN

b

q4  ø, P

q1  b, P

q11  b, P

q3  b, L

q4  b, P

q6  ř, L

q6  b, L

q7  b, P

q11  b, P

q9  b, L

S.A.

SN

c

q7  ø, P

q1  c, P

q11  c, P

q3  c, L

q4  c, P

q11  c, P

q6  c, L

q7  c, P

q9  ø, L

q9  c, L

S.A.

SN

Tabela stanów

q1 - pamięta odczytaną literę a	q2 - i natrafia ø
q3 - i cofa się do początku	q4 - pamięta odczytaną literę b
q5 - i natrafia ø	q6 - i cofa się do początku
q7 - pamięta odczytaną literę c	q8 - i natrafia ø
q9 - i cofa się do początku	q10 -

Symulacja akcji maszyny Turinga dla taśmy zawierającej słowo abba

Głowica maszyny umieszczona jest na kwadracie zawierającym a znajdujące się najbardziej na lewo. Maszyna "pamięta" pierwszy przeczytany symbol, po czym wymazuje go zastępując symbolem pustym i przechodzi w prawo, aż do osiągnięcia pierwszego symbolu pustego. (etap 1-5)


  Maszyna przesuwa się o jeden symbol w lewo, zatrzymuje się więc na najbardziej prawym symbolu (etap 6), w omawianym przypadku jest to symbol a. Gdyby odczytany symbol był różny od zapamiętanego, to maszyna przeszłaby do stanu nieakceptacji.


  Maszyna wymazuje odczytany najbardziej prawy symbol a i przechodzi do stanu, który doprowadza ją do pierwszego symbolu pustego po lewej stronie słowa. (etap 10)


  Maszyna przesuwa się o jeden kwadrat w prawo i zapamiętuje przeczytany symbol, drugi symbol słowa - symbol b. Ruszając się w prawo maszyna porówna zapamiętany symbol z przedostatnim symbolem słowa. (etap 13)Porównanie kończy się sukcesem i maszyna wymazuje symbol b.


  Maszyna rusza w lewo w poszukiwaniu dalszych symboli. Nie znajdując żadnego i nie osiągając stanu nieakceptacji przechodzi do stanu akceptacji. (etap 14-16)

1

...

ø

ø

a

b

b

a

ø

ø

...

2

...

ø

ø

ø

b

b

a

ø

ø

...

3

...

ø

ø

ø

b

b

a

ø

ø

...

4

...

ø

ø

ø

b

b

a

ø

ø

...

5

...

ø

ø

ø

b

b

a

ø

ø

...

6

...

ø

ø

ø

b

b

a

ø

ø

...

7

...

ø

ø

ø

b

b

ø

ø

ø

...

8

...

ø

ø

ø

b

b

ø

ø

ø

...

9

...

ø

ø

ø

b

b

ø

ø

ø

...

10

...

ø

ø

ø

b

b

ø

ø

ø

...

11

...

ø

ø

ø

ø

b

ø

ø

ø

...

12

...

ø

ø

ø

ø

b

ø

ø

ø

...

13

...

ø

ø

ø

ø

b

ø

ø

ø

...

14

...

ø

ø

ø

ø

ø

ø

ø

ø

...

15

...

ø

ø

ø

ø

ø

ø

ø

ø

...

16

...

ø

ø

ø

ø

ø

ø

ř

ř

...

Rysunek 6. Symulacja akcji maszyny Turinga dla taśmy zawierającej słowo abba.

 

Języki formalne, gramatyki, odwrotna notacja polska

Języki i gramatyki formalne

alfabet - dowolny zbiór symboli, z których będą zestawiane słowa języka,

słowo - uporządkowany ciąg symboli alfabetu,

język - zbiór wszystkich możliwych słów,

gramatyka - zbiór reguł umożliwiających generowanie słów danego języka jak też rozróżnienie słów poprawnie zbudowanych od niepoprawnie zbudowanych.

Przykład

Alfabet - {a, b}

Słowo - np. aaaab, bbbb, a , b

Gramatyka - Reguła 1: a jest poprawne (tzn. słowo zbudowane z pojedynczego symbolu a jest poprawne).

Reguła 2: jeżeli α jest poprawne , to aαb też jest poprawne.

Przykłady pojedynczych słów:

a - na podstawie Reguły 1.

aab - na podstawie Reguły 1 i Reguły 2.

aaabb - na podstawie Reguły 1 i dwukrotnie stosowanej Reguły 2.

Gramatyką nazywamy czwórkę

G = ( V, Σ , P , δ )

gdzie:

V - zbiór symboli terminalnych (alfabet końcowy),

Σ - zbiór symboli nieterminalnych (alfabet pomocniczy),

P - lista produkcji,

δ - słowa języka.

Słownikiem A nazywamy zbiór będący sumą mnogościową alfabetu końcowego i alfabetu pomocniczego: A = V ∪ Σ.

Przez A* oznaczamy zbiór wszystkich skończonych ciągów (napisów), których elementy należą do zbioru A.

Język L(G) to zbiór wszystkich słów poprawnych w sensie gramatyki G, tzn. wyprowadzalnych z δ przez listę produkcji P.

Symbol ε oznacza ciąg pusty.

Klasyfikacja gramatyk według Chomskiego:

1. Gramatyki klasy 0

Wszystkie gramatyki mają postać

u w

gdzie:

u ∈ A* - { ε }

w ∈ A*

2. Gramatyki klasy 1 (kontekstowe):

Wszystkie produkcje mają postać:

uXw ubw

gdzie:

u, w ∈ A*

X ∈ Σ

b ∈ A* - {ε}

3. Gramatyki klasy 2 (bezkontekstowe):

Wszystkie produkcje mają postać:

X b,

gdzie :

X ∈ Σ

b ∈ A* - {ε}

4. Gramatyki klasy 3 (regularne):

Wszystkie produkcje mają postać:

X bY (gramatyki prawostronnie regularne)

X Yb (gramatyki lewostronnie regularne)

gdzie :

X ∈ Σ

Y ∈ Σ ∪ {ε}

b ∈ A* - {ε}

Można łatwo się przekonać, że każda gramatyka klasy „i” jest jednocześnie gramatyką klasy „j”, gdzie 0 <= j <= i

Przykład 1.

Definiowanie gramatyki generującej wyrażenia postaci:

aⁿb^mc^k; n, m, k ∈N,

gdzie:

_df

aⁱ = a a ... a

i razy

Rozwiązanie:

Należy zdefiniować kolejno:

V, Σ , P , δ

Zatem otrzymujemy:

V = {a, b, c}

Σ = {W, Z, U}

P: <W>::=a<W>a<Z>

<Z>::=b<Z>b<U>

<U>::=c<U>c

δ = W

Przykład 2.

Zdefiniować gramatykę generującą wyrażenia postaci:

aⁿb^kcⁿ

gdzie:

_df

ai = a a ... a

i razy

Rozwiązanie:

V = {a, b, c}

Σ = {W, U}

P: <W>::=a<W>ca<U>c

<U>::=b<U>b

δ = W

Przykład 3,

Zdefiniować gramatykę generującą liczby całkowite. Liczba składa się z niepustego ciągu cyfr i może zawierać znak.

Rozwiązanie:

V = {0,1,2,3,4,5,6,7,8,9,+,-}

Σ = {LC,L,C,Z}

P:<LC>::=<Z><L> <L>

<L> ::=<C><L> <C>

<C> ::= 0 1 2 3 4 5 6 7 8 9

<Z> ::= + -

δ = LC

Przykład 4.

Dany jest język L(G):

G = <V,Σ,P,δ>

V = {a,b, … ,z,+,(,),*}

Σ = {W,S,C}

P = <W> ::= <W>+<S>| <S>

<S> ::= <S>*<C>|<C>

<C> ::= (<W>) a|b|c| ... |z

δ = W

Czy słowo:

(((a+b * d) * d+a))* a+b+d

jest słowem poprawnym języka L(G) ?

Rozwiązanie:

.....................

{ przedstawiono na wykładzie }

Beznawiasowe algebry Łukasiewicza

Notacje umożliwiająca zapisanie dowolnego wyrażenia arytmetycznego bez użycia nawiasów zmieniających kolejność wykonywania działań.

Odwrotna Notacja Polska (ang. reverse Polish notation)

system notacji beznawiasowej umożliwiający zapisywanie wyrażeń w ten sposób, że argumenty operacji poprzedzają operatory (notacja przyrostkowa)

Ze względu na łatwość obliczania wyrażeń zapisanych w ONP przy użyciu stosu znalazła ona szerokie zastosowanie w arytmetyce komputerów.

Gramatyka pozwalająca na generowanie napisów w ONP oraz Algorytm dokonujący zamiany wyrażeń zapisanych w arytmetyce nawiasowej na ONP.

V = {a,b,d,+,*}

P: <W> ::= <Z><Z><O>|<Z>

<Z> ::= <X><X><O>|<X>

<X> ::= a | b | d

<O> ::= +|*

Przykłady prostych wyrażeń arytmetycznych i odpowiadający im zapis w ONP:

1)

(a+b)*d a b + d *

2)

(a + b)/c*(d-e) ab+c/de-*

Oprócz Odwrotnej Notacji Polskiej istnieje także Notacja Polska. Zmiana dotyczy produkcji:

P: <W> ::= <O><Z><Z>|<Z>

<Z> ::= <O><X><X>|<X>

<X> ::= a | b | d

<O> ::= +|*

Algorytm wyznaczania wartości wyrażenia w ONP


















T










N


N T










N T











Przykład

Obliczyć wartość wyrażenia: 2 3 4 5 + * +

Definicja

Translacja to przekład tekstów zredagowanych w jednym języku źródłowym na równoważny semantycznie tekst w innym języku - wynikowym.

Translacja prostych wyrażeń arytmetycznych na zapis w odwrotnej notacji polskiej (ONP) wymaga ustalenia tablicy priorytetów dla operatorów arytmetycznych.

Tablica priorytetów:

Operator	Priorytet
Funkcja (lg, sin, exp, ...)	0
Potęgowanie ( ↑ )	1
Mnożenie, dzielenie, negacja ( *, / , )	2
Dodawanie, odejmowanie (+, -)	3




Wzrost

Priorytetu

Reguły translacji przy użyciu stosu:

1. nawias otwierający zawsze wprowadzany jest do stosu.

2. argumenty wyprowadzane są bezpośrednio na wyjście stosu.(nie „wchodzą” do stosu).

3. operator wprowadzany jest do stosu, o ile ma wyższy priorytet od operatora znajdującego się na szczycie stosu.

4. jeżeli operator ma równy lub niższy priorytet niż operator znajdujący się na szczycie stosu, to wówczas wprowadzany jest do stosu , usuwając przedtem z niego wszystkie operatory o równym i niższym priorytecie,

5. nawias zamykający powoduje wyprowadzenie zawartości stosu do pierwszego napotkanego nawiasu otwierającego, łącznie z nim.

Konwencja graficzna:

WEJŚCIE		STOS		WYJŚCIE STOSU
		SZCZYT STOSU

Automaty skończone

DETERMINISTYCZNY AUTOMAT SKOŃCZONY

Automat skończony jest modelem matematycznym systemu o dyskretnych wejściach i wyjściach. System taki w danej chwili może znajdować się w jednym ze skończonej liczby stanów, który to stan jest ściśle uzależniony od stanu poprzedniego. Jeden ze stanów pełni rolę stanu początkowego, od którego dany automat rozpoczyna działanie, z drugiej strony niektóre stany pełnią rolę stanów końcowych kończąc pracę automatu. Praca automatu oparta jest na analizie symboli wejściowych ze skończonego alfabetu. Każdy odczytany symbol wymusza przejście do innego stanu (w niektórych przypadkach przejście prowadzi do tego samego stanu). Po przeanalizowaniu wszystkich symboli automat skończony może przyjąć jeden z dwu stanów: akceptacji lub nieakceptacji. Bardzo często automat skończony, który w dalszych rozważaniach będziemy oznaczać jako AS jest przedstawiany za pomocą grafów skierowanych, w których wierzchołki obrazują stany automatu. Jeżeli istnieje przejście z jednego stanu do następnego to takie przejście przedstawione jest za pomocą łuku. Dla wyodrębnienia stanu początkowego, wierzchołek rozpoczynający pracę automatu wzbogacony jest o strzałkę z napisem START. W celu zaakcentowania stanu końcowego wprowadza się dwa odrębne wierzchołki grafu opatrzone etykietą A (s. akceptacji) N (s. nieakceptacji), bądź stan końcowy oznacza się podwójnym kółkiem. Rysunek 1 przedstawia fragment grafu dla automatu skończonego:




Rys. 7. Fragment grafu przejść dla automatu skończonego.

Automat skończony przedstawiamy formalnie jako uporządkowaną piątkę:

< Q,
, ð , q_o, F>

gdzie:

Q - jest skończonym zbiorem stanów,


- jest skończonym alfabetem symboli wejściowych,

q₀ należące do Q jest stanem początkowym od którego automat rozpoczyna działanie,

F
Q - jest zbiorem stanów końcowych (stan akceptacji lub nieakceptacji),

ð - dla automatu jednowejściowego jest funkcją odwzorowującą Q x
Q czyli ð określa każdemu stanowi q i każdemu symbolowi „a” na wejściu nowy stan automatu, oraz

dla automatu k-wejściowego jest funkcją odwzorowującą Q x
x
... x
Q czyli ð określa każdemu stanowi q i k symbolom na wejściu nowy stan automatu
q.

Jednowejściowy automat skończony możemy sobie wyobrazić jako głowicę sterująco-czytającą, która analizuje symbole zapisane na taśmie w sposób pokazany na rysunku 8.

Zaś k - wejściowy automat skończony będzie reprezentowany przez k głowic sterująco-czytających.




Rys. 8. Schemat pracy automatu skończonego

W danej chwili automat odczytuje symbol wejściowy i przechodzi do kolejnego stanu. Jeżeli stan ten jest stanem akceptacji to znaczy, że dotychczasowy ciąg symboli na taśmie jest zaakceptowany przez AS. Jeżeli głowica przesunęła się na koniec taśmy, a ostatni stan jest stanem zaakceptowanym przez AS to AS zaakceptował cały łańcuch.

Formalnie przyjmuje się, że łańcuch jest akceptowany przez automat M, jeżeli ð (q_o,x)= p dla jakiegoś p należącego do F. Język akceptowany przez dany automat M oznaczany L(M), to zbiór {x | (q_o,x) należy do F}. Język nazywamy zbiorem regularnym, jeżeli jest on językiem akceptowanym przez pewien automat skończony. Zbiory regularne zostaną szczegółowo omówione pod koniec tego rozdziału.

Przykłady działania deterministycznego automatu skończonego

W celu zobrazowania konstrukcji automatu skończonego przeanalizujmy dwa przykłady dotyczące akceptacji liczb podzielnych przez wybraną liczbę.

Przykład 1 : Automat skończony akceptujący liczby podzielne przez 2

Dla tego automatu zbiór symboli wejściowych będzie złożony z cyfr od 0..9 czyli
= {0,1,2,3,4,5,6,7,8,9}. Wiadomo też, że liczba jest parzysta gdy ostatnia jej cyfra jest podzielna bez reszty przez 2.


  Konstrukcję automatu rozpoczynamy od wykreślenia wierzchołka stanu q₀, który jest stanem wejściowym (Rys. 8)




Rysunek 8

Jeżeli pojawi się na wejściu cyfra podzielna przez 2 to zaznaczmy to na grafie jako przejście do stanu q₁, jeżeli pojawi się na wejściu cyfra niepodzielna przez 2 to zaznaczmy to jako przejście do stanu q₂ (Rys.9)




Rysunek 9

jeżeli AS jest w stanie q₁ i kolejna cyfra na wejściu jest podzielna przez dwa to automat pozostaje nadal w tym samym stanie co zaznaczamy na grafie łukiem wychodzącym z stanu q₁ opatrzonego etykietą {0,2,4,6,8}, jeżeli pozostając w stanie q₂ AS odczyta wszystkie symbole (co umownie oznaczamy pojawieniem się symbolu ø lub # ) wówczas AS przechodzi do stanu akceptacji A (Rys 10)




Rysunek 10

jeżeli AS jest w stanie q₁ i kolejna cyfra na wejściu jest nieparzysta to AS pozostaje nadal w tym samym stanie co zaznaczamy na grafie łukiem wychodzącym i wchodzącym do stanu q₂ opatrzonego etykietą {1,3,5,7,9}, jeżeli pozostając w stanie q₂ AS odczyta wszystkie symbole to wówczas AS przechodzi do stanu nieakceptacji N (Rys. 11 )




Rysunek 11

Oczywiście istnieje możliwość pojawienia się na wejściu przemiennie liczb parzystych i nieparzystych a tym samym przejścia z stanu q₁ do stanu q₂ (Rys 12 - ostateczna konstrukcja automatu )


źle!!`

Rysunek 12

 

Pojawienie się na wejściu liczby np.123 dla rozpatrywanego automatu sprawi, że automat przejdzie przez następujący porządek stanów: q₀, q₂, q₁, q₂, N - czyli liczba 123 nie zostanie zaakceptowana przez automat ( co jest zgodne z prawda gdyż 123 nie jest liczbą parzystą); natomiast pojawienie się liczby 36 wymusi przejście przez stany: q₀, q₂, q₁, A-czyli liczba zostanie zaakceptowana prze automat (co jest zgodne z prawdą gdyż 36 - jest liczbą parzystą).

Przykład 2: Automat skończony akceptujący liczby podzielne przez 3.

Dla tego automatu zbiór symboli wejściowych będzie złożony z cyfr od 0..9 czyli
= {0,1,2,3,4,5,6,7,8,9}. Wiadomo też, że liczba jest podzielna bez reszty przez 3 gdy suma cyfr danej liczby jest podzielna przez 3. Musimy więc rozpatrzyć następujące przypadki tego zadania: po pierwsze jeżeli liczba złożona jest z cyfr 0,3,6,9 to jest ona na pewno podzielna przez 3. Dla cyfr 1,4,7 i 2,5,8 rozpatruje się dodatkowe warunki : pojawienie się cyfr 1,4,7 musi wystąpić trzykrotnie bądź musi wystąpić cyfra 2,5,8 by liczba była podzielna przez 3. Tak samo pojawienie się cyfr 2,5,8 musi wystąpić trzykrotnie bądź po pojawieniu się jednej z nich musi wystąpić cyfra 1,4,7. Diagram przejść takiego automatu przedstawia rysunek 13.




Rys. 13. Automat skończony akceptujący liczby podzielne przez 3.

Pojawienie się na wejściu liczby 126 spowoduje przejście automatu przez stany: q₀, q₁, q₂, A czyli cyfra jest podzielna przez trzy, natomiast 125 wymusi drogę: q₀, q₁, q₂, N czyli liczba nie jest podzielna przez 3.

W praktyce badanie czy dana liczba jest podzielna przez n sprowadza się do operacji modulo (badanie reszty z dzielenia liczby przez n). W tym celu przed wykreśleniem grafu automatu skończonego tworzymy tabelę stanów, obrazującą przejścia między stanami w zależności od rozpatrywanej cyfry. Tabelę taką tworzymy w następujący sposób:


  liczba kolumn jest równa n, czyli liczbie przez którą dana liczba wejściowa ma być podzielna,


  natomiast liczba wierszy jest równa liczbie cyfr (0-9) uzupełniona o 1 dla symbolu pustego ø .

Przeanalizujmy tabelę 4, która dotyczy automatu skończonego badającego czy liczba jest podzielna przez 3.

 

	q0	q1	q2
f	T	N	N
0	q0	q1	q2
1	q1	q2	q0
2	q2	q0	q1
3	q0	q1	q2
4	q1	q2	q0
5	q2	q0	q1
6	q0	q1	q2
7	q1	q2	q0
8	q2	q0	q1
9	q0	q1	q2

Tabela 4.Tabela stanów dla automatu skończonego akceptującego liczby podzielne przez 3

Chcąc stworzyć automat skończony badający podzielność liczb przez 4, do tabeli 4 dodajemy jedną kolumnę z stanem q4, zaś samo liczenie w pionie zwiększamy do 4, czyli pierwsza kolumna będzie miała następujący porządek stanów: q₀, q₁, q₂, q₃, q₀, q₁, q₂, q₃, q₁, q₂. Na tej podstawie możemy stworzyć automat badający podzielność przez dowolną liczbę.

Dla tego typu automatów pojawienie się na wejściu jakiegokolwiek symbolu powoduje ruch automatu ściśle określoną drogą bez możliwości wyboru. Jak się okaże w kolejnych podrozdziałach wybór drogi automatu wcale nie musi być z góry określony tzn. że dany symbol wejściowy może wymusić przejście do różnych stanów. Dlatego automaty skończone gdzie istnieje tylko jedna droga przejścia ze stanu do stanu dla danego symbolu wejściowego określa się jako deterministyczne automaty skończone (DAS).

 

NIEDETERMINISTYCZNY AUTOMAT SKOŃCZONY

Jak już zostało wspomniane w końcówce poprzedniego podrozdziału dany symbol wejściowy może wymusić przejście do różnych stanów, stąd wprowadźmy modyfikację modelu automatu skończonego, polegającą na istnieniu kilku przejść ze stanu przy tym samym symbolu wejściowym. Taka modyfikacja pozwala zdefiniować model niedeterministycznego automatu skończonego (NAS), który formalnie jest definiowany jako uporządkowana piątka:

<Q,
, ð , q_o, F>

gdzie:

Q - jest skończonym zbiorem stanów,


- jest skończonym alfabetem symboli wejściowych, q₀ należące do Q jest stanem początkowym, od którego automat rozpoczyna działanie,

F
Q - jest zbiorem stanów końcowych (stan akceptacji lub nie akceptacji),0

ð - jest odwzorowaniem Q x
2^Q. (2^Q - jest zbiorem potęgowym Q, czyli zbiorem wszystkich podzbiorów Q), czyli ð (q,a) jest zbiorem wszystkich stanów p, dla których istnieje przejście ze stanu q do p po etykiecie związanej z symbolem wejściowym a.

Rysunek 14 przedstawia konstrukcję NAS akceptującego ciągi zerojedynkowe w których przynajmniej raz wystąpiło podwojenie zer lub jedynek:







Rys. 14. Niedeterministyczny automat skończony akceptujący ciągi, w których wystąpiło podwojenie zer i jedynek.

Z rysunku 14 widać, że ze stanu q₀ wychodzą dwie krawędzie (drogi) o etykiecie 0, czyli z chwilą pojawienia się zera na wejściu istnieje możliwość przejścia ze stanu q₀ do stanu q₁ lub q₃ . Taka właśnie możliwość wyboru stanów przy tym samym symbolu wejściowym wyróżnia NAS od DAS. Ten typ automatów będzie akceptował ciąg symboli a₁,a₂...a_n, dla którego istnieje ciąg przejść prowadzący od stanu początkowego do stanu końcowego. Dla przykładu ciąg 101001 zostanie zaakceptowany przez powyższy NAS bo istnieje towarzyszący mu ciąg przejść: q₀, q₀, q₀, q₃, q₄, q₄; natomiast dla ciągu 10101 nie istnieje żadne przejście ze stanu początkowego do końcowego, gdyż automat w wyniku pojawienia się symboli 10101 pozostanie w stanie q₀ czyli wyrażenie nie zostanie zaakceptowane.

Rysunek 15 przedstawia jeszcze jeden niedeterministyczny automat skończony, który akceptuje ciągi wyrazowe
w których wystąpiła przynajmniej raz sekwencja symboli a b c.




Rys. 15. NAS akceptujący ciąg symboli, w których przynajmniej raz wystąpiła sekwencja a,b,c.

Deterministyczny automat skończony z poprzedniego podrozdziału jest szczególnym przypadkiem NAS, w którym dla każdego stanu istnieje dokładnie jedno przejście ze stanu do stanu czyli każdy DAS jest NAS.

AUTOMAT SKOŃCZONY Z  ε - RUCHAMI

Modyfikacją niedeterministycznego automatu skończonego jest automat skończony z
- ruchami. Model automatu w tym przypadku dopuszcza przejście ze stanu do stanu przy pustym wejściu
. Formalnie niedeterministyczny automat skończony z
-ruchami jest definiowany jako uporządkowana piątka:

< Q,
, ð , q_o, F>

gdzie:

Q,
, q_o, F- takie same znaczenie jak w przypadku DAS i NAS

đ- odwzorowuje Q x (

{
}) 2^Q. Czyli ð jest zbiorem wszystkich stanów p takich, że istnieje przejście o etykiecie a ze stanu q do p, natomiast a jest słowem pustym
lub symbolem ze zbioru
.

Dla przykładu rozpatrzmy diagram przejść AS z
- ruchami z rysunku 16, który akceptuje ciąg symboli zawierających dowolna liczbę zer, po których następuje dowolna liczba jedynek, a następnie dowolna liczba dwójek. Oczywiście zgodnie z definicją dowolna liczba poszczególnych symboli może wynosić 0 czyli nastąpi przejście przy pustym wejściu
:




Rys.16. NAS z ε-ruchami akceptujący ciąg złożony z kilku 0, potem kilku 1, a potem kilku 2.

Dla powyższego diagramu słowo 002 zostanie zaakceptowane gdyż istnieje droga od stanu początkowego do stanu końcowego: q₀, q₀, q₀, ε, ε, q₂, o łukach etykietowanych 0 ,0, ε, ε, 2.

Konstrukcja NAS
- ruchami jest bardziej zrozumiała po zapoznaniu się z wyrażeniami regularnymi, które zostały omówione w następnym rozdziale.

 

WYRAŻENIA REGULARNE

Języki akceptowane przez automaty skończone można łatwo opisać prostymi wyrażeniami zwanymi wyrażeniami regularnymi. Celem przedstawienia zapisu języków akceptowanych wprowadźmy pojęcia: złożenia i domknięcia na zbiorach łańcuchów.

Niech Σ będzie skończonym zbiorem symboli i niech L, L₁, L₂ będą zbiorami łańcuchów z Σ^*. Złożeniem L₁ i L₂, oznaczanym jako L₁ L₂, nazywamy {xy | x należy do L₁ i y należy do L₂} - oznacza to, że łańcuchy należące do L₁ L₂ tworzone są poprzez wypisanie łańcucha z L₁ , a następnie łańcucha z L₂, we wszystkich możliwych kombinacjach np. niech L₁ ={0,1} i L₂={01,101} wtedy złożenie L₁ L₂ = {001,0101, 101,1101}.

Niech L⁰={
} i Lⁱ =LL^i-1 dla i > 0. Domknięciem Kleene'ego (domknięciem) L, oznaczanym symbolem L^*, nazywamy zbiór:




a domknięciem dodatnim L oznaczanym symbolem L⁺ , zbiór




Tak więc L^* jest zbiorem wszystkich słów otrzymanych w wyniku złożenia dowolnej liczby słów z L, zaś L⁺ wyklucza przypadek zera słów, których złożenie określa się -
; np.:

domknięciem Kleene'ego {1,0}^* ={
, 1, 0, 11,10,01,00....}, zaś 
domknięciem dodatnim {1,0}⁺ = {1, 0, 11,10,01,00....}.

Wyrażenia regularne i zbiory przez nie reprezentowane definiujemy w następujący sposób:

• Ø jest wyrażeniem regularnym reprezentującym zbiór pusty.

• 
  jest wyrażeniem regularnym reprezentującym zbiór {
  }.

• Dla każdego a z Σ, a jest wyrażeniem regularnym reprezentującym zbiór {a}.

Jeżeli r i s są wyrażeniami regularnymi reprezentującymi odpowiednio języki R i S, to

• (r+s) - są wyrażeniami regularnymi reprezentującymi zbiór R
  S,

• (rs) - są wyrażeniami regularnymi reprezentującymi zbiór RS,

• (r^*) są wyrażeniami regularnymi reprezentującymi zbiór R^*.

Dla przykładu:

• 00 jest wyrażeniem regularnym, reprezentującym {00}

• (0+1) opisuje zbiór wszystkich łańcuchów złożonych z zer i jedynek

• (0+1)^*00(0+1)^* opisuje zbiór wszystkich zer i jedynek w których przynajmniej raz wystąpiło podwojenie zer

• (1+10)^* reprezentuje zbiór wszystkich zer i jedynek rozpoczynających się od 1 i nie zawierajęcych podwojonych symboli 0.

• (0+1)^*011 opisuje wszystkie łańcuchy zer i jedynek kończące się sekwencją 011

• 0⁺ 1⁺ 2⁺ jest wyrażeniem reprezentującym dowolna liczbę zer po których następuje dowolna liczba jedynek, a następnie dowolna liczba dwójek (domknięcie dodatnie - czyli łańcuchy końcowe muszą zawierać przynajmniej po jednym reprezentancie powyższych symboli).

Udowodniono, że wyrażenia regularne reprezentują języki akceptowane przez automaty skończone co oznacza, że dla dowolnego wyrażenia regularnego istnieje odpowiadający mu NAS z e -ruchami, co więcej wprowadzono gotowe konstruktory dla diagramów przejść pozwalające dla dowolnego wyrażenia regularnego stworzyć mechanicznie konstrukcję automatu skończonego. Wyróżniono trzy podstawowe postacie wyrażeń regularnych:

• suma teoriomnogościowa r = r₁ + r₂

• złożenie r = r₁ r₂

• domknięcie r = r₁^*




Każda droga na powyższym diagramie automatu M musi rozpoczynać się od przejścia do stanu q₁ lub do stanu q₂ przy pustym wejściu
. Jeżeli droga prowadzi do q₁, to następnie może dowolnie przebiegać w automacie M₁, aż do osiągnięcia stanu f₁, potem następuje przejście do stanu f_o, przy pustym wyjściu
. Podobnie, jeżeli droga rozpoczęła się przejściem ze stanu q₀ do q₂ to następnie może przebiegać dowolną trasą w automacie M₂, aż do osiągnięcia stanu f₂, a następnie przejście do stanu f₀.




Każda droga z q₁ do f₂ w automacie M składa się z drogi etykietowanej jakimś łańcuchem x prowadzącej z q₁ do f₁, po której następuje przejście ze stanu f₁ do stanu q₂ przy pustym wejściu
a następnie następuje droga z q₂ do f₂ etykietowana jakimś łańcuchem y.




Dowolna droga prowadząca z q₀ do f₂ składa się albo z drogi z q₀ do f₀ o etykiecie
, albo też z drogi od q₀ do q₁ przy
, po których następuje pewna liczba (w szczególnym przypadku 0) dróg z q₁ do f₁, potem znowu do q₁ przy
, następnie znów droga z q₁ do f₁, aż w końcu droga z f₂ do f₀ przy
.

Powyższe konstruktory są bardzo pomocne przy kreśleniu diagramów przejść NAS dla wyrażeń regularnych. Konstrukcję takiego automatu rozpoczynamy wtedy od rozłożenia wyrażenia regularnego na elementarne składowe dla których tworzymy automaty, te z kolei na podstawie konstruktorów łączymy w logiczną całość. Przeanalizujmy przykład automatu akceptującego wyrażenie regularne postaci: 01^*+1. To wyrażenie jest postaci r = r₁ + r₂ gdzie: r₁=01^*; r₂ = 1. Dla wyrażenia r₂ postać automatu jest następująca:




wyrażenie r₁ możemy zapisać jako r₁ = r₃ r₄ gdzie r₃= 0; r₄=1^*. Automat dla r₃ ma prostą konstrukcję, która przedstawia się następująco:




z kolei wyrażenie r₄ możemy zapisać jako r₄ = r₅^* gdzie r₅ to 1, a NAS dla r₅ to:




Wykorzystują przedstawione konstruktory zaczniemy kreślenie automatu dla wyrażenia r₄ = 1* ( konstruktor domknięcia)




następnie dla r₁ =r₃r₄ (r= 01^*) wykorzystujemy konstruktor złożenia dokładając do rys. a następującą konstrukcję:




Teraz tworzymy konstrukcję dla wyrażenia r= r₁ + r₂ (r=01^*+1) wykorzystując konstruktor sumy teoriomnogościowej.


 Zastosowania automatów skończonych

Istnieje cała skala problemów z zakresu projektowania oprogramowania, które dają się uprościć poprzez automatyczną konwersję symboliki wyrażeń regularnych na efektywną implementację komputerową odpowiedniego automatu skończonego. Teorię automatów skończonych wykorzystano do:

Analizatorów leksykalnych

Tokeny (czyli bazowe kategorie syntaktyczne) języka programowania dają się niemal bez wyjątku przedstawić w postaci wyrażeń regularnych. I tak na przykład, identyfikatory PASCALa, będące ciągami liter i cyfr rozpoczynającymi się od litery (małej czy dużej), bez ograniczenia co do długości ciągu, można wyrazić w postaci

( litera ) ( litera + cyfra )^*

gdzie litera oznacza A + B +... + Z + a + b + .. z, a cyfra - 0 + 1 + .. + 9

Identyfikatory w Fortranie, których długość jest ograniczona do sześciu znaków i które nie mogą zawierać innych liter niż duże oraz znak $ mogą być przedstawione jako

( litera ) ( ε + litera + cyfra )⁵

Niektóre generatory analizatorów leksykalnych przyjmują jako wejście ciąg wyrażeń regularnych opisujących tokeny i wytwarzają pojedynczy automat skończony, rozpoznający dowolny token. Zazwyczaj przekształcają one wyrażenia regularne na NAS z ε -przejściami, a następnie konstruują podzbiory zbioru stanów, aby otrzymać DAS w sposób bezpośredni, zamiast wyeliminować najpierw ε -przejścia.

Edytorów tekstu

Pewne edytory tekstu oraz podobne do nich programy pozwalają na zastępowanie dowolnego łańcucha pasującego do danego wyrażenia regularnego pewnym innym łańcuchem.

Techniki

Wykorzystywane do projektowania układów przełączających na przykład działanie termostatu jest oparte na analizie temperatur i wybieraniu jednego z dwóch stanów : włączenie układu grzewczego i wyłączenie.

błąd

KONIEC

φ

operator

pobierz argumenty ze stosu, wykonaj działanie, wynik na stos

stos

argument

pobierz symbol z lewej ku prawej

start

---