TEORETYCZNE PODSTAWY INFORMATYKI
Wymagania:
Algorytmy. Modele obliczeń, maszyny Turinga, obliczalność. Języki
formalne, gramatyki i automaty. Złożoność obliczeniowa, klasy
złożoności, NP-zupełność.
Wykłady:
1. Algorytmy. Dziedzina algorytmiczna. Termy i wyrażenia arytmetyczne.
Wyrażenia logiczne. Przykłady algorytmów.
2. Algorytmy. Procedury i rekursja. Przykłady algorytmów rekurencyjnych.
3. Poprawność algorytmów. Algorytm poprawny  semantyczna poprawność
algorytmów. Poprawność częściowa, własność określoności obliczeń,
własność stopu.
4. Poprawność algorytmów Dowodzenie poprawności częściowej - metoda
niezmienników Naur a-Floyd a. Dowodzenie własności stopu - metoda
liczników iteracji.
5. Sprawność algorytmów. Miary efektywności algorytmów. Złożoność
obliczeniowa algorytmów. Złożoność pesymistyczna i średnia. Dolne i górne
ograniczenie złożoności. Problemy algorytmicznie zamknięte i otwarte.
6. Klasyfikacja problemów algorytmicznych. Problemy łatwo-rozwiązywalne i
trudno-rozwiązywalne. Klasy problemów algorytmicznych: logarytmiczne,
wielomianowe, NP, NP-zupełne.
7. Klasyfikacja problemów algorytmicznych. Otwarte problemy związane z
klasyfikacją problemów algorytmicznych. Dowodzenie NP-zupełności.
8. Prymitywne modele algorytmiczne. Teza Churcha-Turinga. Maszyna
Turinga i jej warianty.
9. Prymitywne modele algorytmiczne. Przykłady implementacji wybranych
algorytmów.
10. Języki systemów informacyjnych. System informacyjny. Składania i
semantyka języka. Reguły przekształcania termów.
11. Języki systemów informacyjnych. Postać normalna termów. Dokładność i
efektywność języka.
12. Automaty. Układy sekwencyjne i kombinacyjne. Języki formalne. Język
wyrażeń regularnych. Automaty Rabina-Scotta. Automaty Meale go i Moor a.
13. Automaty. Realizacje automatów. Synteza abstrakcyjna z wykorzystaniem
charakterystyki wejście-wyjście.
1
14. Sieci Petriego. Definicja i klasyfikacje sieci Petriego. Reprezentacje
teoriomnogościowa, graficzna i macierzowa. Modelowanie - przykłady
zastosowań.
15. Sieci Petriego. Analiza właściwości  żywotność strukturalna i funkcjonalna.
Zjawiska blokady i konfuzji. Niezmienniki. Rozszerzenia sieci  czasowe,
kolorowane, stochastyczne.
Literatura
1. Banachowski L., Kreczmar A., Elementy analizy algorytmów. WNT, Warszawa
1982.
2. Majewski W., Albicki A., Algebraiczna teoria automatów. WNT, Warszawa
1980.
3. Pawlak Z., Systemy informacyjne (Podstawy teoretyczne). WNT, Warszawa
1983.
4. Błażewicz J., Złożoność obliczeniowa w projektowaniu systemów
komputerowych. Wyd. Politechniki Poznańskiej, Poznań 1984.
5. Starke P.K., Sieci Petri. Podstawy, teoria, zastosowania. PWN, Warszawa
1987.
2
TEORETYCZNE PODSTAWY INFORMATYKI
 Komputer zmusił nas do uporządkowania samych
siebie.,,,Zmusza nas do uprzedniego przemyślenia naszych
założeń i powoduje, że zdajemy sobie w ogóle sprawę z tego, że
przyjmujemy jakieś założenia.
Peter Druckner
1. ALGORYTMY
" Algorytmy  rys historyczny, przykłady
" Dziedzina algorytmiczna
" Termy i wyrażenia arytmetyczne
" Wyrażenia logiczne
" Przykłady algorytmów
ALGORYTM  z
ródłosłów
Abu Jafar Mukhammad ibin Musa al-Kwarizmi
(Mukhammad, ojciec Jafar a, syn Moses a, Kwarizmianin)
Al-Khorezmi z Khorezm (780  850) (Uzbekistan)
(Arytmetyka, Algebra) abu-aljabar
 Kitab al-jabr wal-muqabala z
ródło  Fihrist  An-Nadin (987)
(The book of Aljabar and Almuqaba
 The book of Restoring and Equating)
Księga rekonstrukcji i bilansu
1 + 2 + 4 + ...+ 263 = (((162) 2) 2) 2 = 18 446 744 073 709 551 615
Algorytm  przepis postępowania, w sposób automatyczny prowadzący do
rozwiązania określonego zadania.
Zakłada się, ze pewne pierwotne instrukcje tego przepisu są
wykonalne, to znaczy, że są one zdefiniowane i w algorytmie nie musi
się ich definiować, ale można ich używać.
3
Przykład
Mnożenie dwóch liczb naturalnych zapisanych w układzie dziesiętnym,
zakłada znajomość tabliczek dodawania i mnożenia cyfr dziesiętnych.
Budowa algorytmu zakłada zatem znajomość zbioru obiektów na
których ma działać zbiór wykorzystywanych w nim pierwotnych operacji.
Dziedzina algorytmiczna
- zbiór obiektów wraz z operacjami pierwotnymi
(A, f1,...,fn, r1,...,rm)
gdzie
A  zbiór niepusty
f1,...,fn  funkcje częściowo określone dla argumentów ze zbioru A i
przyjmujące wartości w zbiorze A
r1,...,rm  relacje zachodzące między elementami zbioru A
rj(x1,...,xk)  relacja k-argumentowa , rj ą" Ak
fj(x1,...,xk) = xk+1  funkcja k-argumentowa częściowa
k+1- argumentowa relacja, taka że dla ustalonego
(x1,...,xk) istnieje co najwyżej jeden element xk+1 ,
dla którego układ (x1,...,xk, xk+1) należy do tej relacji
Funkcja całkowita określona jest dla wszystkich
układów (x1,...,xk)
Przykład
Dziedziną algorytmiczna liczb całkowitych jest układ:
(Z , + , - , * , div , mod , = , >)
gdzie:
Z  zbiór liczb całkowitych
+ , - , * - dwuargumentowe całkowite funkcje dodawania, odejmowania i
mnożenia dwóch liczb całkowitych
` = , > odpowiednio relacja równości i relacja porządku w zbiorze liczb
całkowitych
div, mod  częściowe funkcje dwuargumentowe określone dla par (n,m) gdy
m`"0, dającymi odpowiednio iloraz i resztę z dzielenia n przez m
4
Przykład
Dziedzina algorytmiczna rachunku logicznego (Algebra Boole a)
(B , Ź , '" , (" , �! , �!)
gdzie
B  zbiór wartości logicznych {false,true}
Ź,'",(",�!,�! - funkcje pierwotne zdefiniowane następująco:
Ź(false) = true , Ź(true) = false
'"(true,true) = true , '"(true,false) = '"(false,true) = '"(false,false) = false
("(a,b) = Ź('"(Ź (a),Ź(b)))
�!(a,b) = ("(Ź(a),b)
�!(a,b) = '"(�!(a,b), �!(b,a))
Termy
Niech (A, f1,...,fn, r1,...,rm) będzie dziedziną algorytmiczną.
Term - napis języka (np. programowania), który definiuje algorytm polegający
na obliczeniu wartości funkcji pierwotnej danej dziedziny algorytmicznej, albo
superpozycji takich funkcji, a zatem spełniający warunki:
1) Każda stała i każda zmienna przyporządkowana danej dziedzinie
algorytmicznej jest termem.
2) Jeżeli f jest symbolem funkcji k-argumentowej oraz jeżeli t1,...,tk są
termami, to napis f(t1,...,tk) jest termem
3) Termem jest tylko taki napis, który można otrzymać stosując 1) lub 2)
Przykład
c , x , f(x) , f(d) , g(f(y),c)) , itp. są termami
gdzie:
c, d  stałe
x, y  zmienne
f, g  symbole funkcji odpowiednio jedno i dwuargumentowej
Wykonanie termu, a więc algorytmu określonego przez term, polega na
obliczeniu jego wartości.
Przykład
W ramach dziedzin liczb całkowitych lub rzeczywistych termy nazywa się
wyrażeniami arytmetycznymi (definiującymi skończone ciągi operacji
arytmetycznych, które trzeba wykonać w określonej kolejności).
+(x,-(z,*(76.3,u)))
(x+(z-(76.3*u)))
x+z-76.3*u
5
Język definiujący napisy (algorytmy) obejmuje:
Stałe - napisy, którym jest przyporządkowana jedna określona wartość 
element zbioru A, np. 0, -1, 00678, 315, itp. dla dziedziny liczb
całkowitych
Zmienne -napisy, które mogą mieć przyporządkowaną dowolną wartość ze
zbioru A, np. var i,j,k: integer
re, im: real
itd.
Obliczenie wartości termu polega na obliczeniu wartości odpowiednich funkcji dla
określonych wartości stałych i wartości zmiennych.
Wartościowanie stałych  stałym odpowiadają pewne elementy zbioru A.
Wartościowanie zmiennych  określa funkcja �((x) , gdzie x  zmienna
Przykład
Jeżeli term jest stałą to jego wartością jest ta stała.
Jeżeli term jest zmienną, to jego wartość równa jest wartościowaniu
zmiennej.
Jeżeli term jest funkcją k-argumentową f(t1,...,tk) oraz funkcja g jest
określona to �(f(t1,...,tk) = g(�(t1),..., �(tk))
Przykład
Podstawienie (przypisanie) x := t , gdzie x  zmienna , t  term
Dla danego wartościowania � oblicza się wartość termu �(t). Jeżeli
wartość ta jest należy do dziedziny algorytmicznej, do której jest
przyporządkowana zmienna x, to wartości zmiennej x można przypisać
(zastąpić) wartość �(t).
Przykład
Niech a, b, c  zmienne, których początkowe wartości są równe
długościom boków trójkąta.
Algorytm obliczania pola trójkąta (ze wzoru Herona) definiują dwa
przypisania:
P:= (a + b + c)/2
S := sqrt(p*(p-a)*(p-b)*(p-c)
Algorytm ten można oczywiście zapisać korzystając z jednego
przypisania:
S := sqrt((a + b + c)*( b + c-a)*( a + c - b)*( a + b-c)/16)
Uwagi:
Porównaj niezbędną do wykonania liczbę operacji dodawania,
mnożenia i pierwiastkowania.
Ile algorytmów rozwiązuje dany problem?
Jak porównywać algorytmy?
6
Przykład
Traktując liczbę zespolona jako uporządkowana parę liczb rzeczywistych (a,b)
mnożenie dwóch liczb zespolonych (a,b)*(c,d) = (e,f) można określić przy
pomocy dwóch algorytmów:
a) e:= a*c  b*d
f := a*d + b*c
b)
g := (a+b)*c ; h := a*(d-c) ; f:= g+h
h := b(*(d+c) ; e := g-h
Który z algorytmów jest lepszy?
Uwaga:
Termy postaci wyrażeń arytmetycznych oraz instrukcje podstawienia
umożliwiają definiowanie algorytmów najprostszej postaci (nie korzystających
z pierwotnych relacji danej dziedziny algorytmicznej) nie pozwalających
zmieniać kolejności wykonywanych czynności w zależności od aktualnego
wartościowania zmiennych, tzw. algorytmów liniowych.
Wyrażenia logiczne (wyrażenia boolowskie)
Zbiór napisów spełniających następujące warunki:
1) Każda stała logiczna i każda zmienna logiczna są wyrażeniami logicznymi
2) Jeżeli t1,...tk są termami oraz r jest symbolem relacji k-argumentowej, to
r(t1,...,tk) jest wyrażaniem logicznym.
3) Jeżeli s, u są wyrażeniami logicznymi, to napisy Źs , s'"u , s("u , s�!u
, s�!u są również wyrażeniami logicznymi
4) Wyrażeniem logicznym jest tylko ten napis, który można otrzymać stosując
1)  3).
Przykłady algorytmów
Algorytm Euklidesa
Dane są dwie liczby całkowite dodatnie m i n. Należy wyznaczyć ich
największy wspólny dzielnik.
Z definicji NWD (największy wspólny dzielnik) oznacza największa dodatnią
liczbę całkowitą k taką, że k dzieli n i m (bez reszty).
7
Rozważmy
n = q*m + r
" r = 0 NWD(n,m) = m
" r > 0 NWD(n,m) = NWD(m,r)
n = 18 , m = 12 18 = 1*12 + 6
9*2 = 1*6*2 + 3*2
6*3 = 1*4*3*+ 2*3
n = 15 , m = 11 15 = 1*11 + 4
15*1 = 1*11*1 + 4*1
Uwaga: Zatem zadanie poszukiwania NWD(n,m) można zastąpić zadaniem
NWD(m,r)
m > r oznacza, ze liczba kroków algorytmu jest skończona
Warunek stopu n = q *m + r , r = 0 ; NWD = m
Przykład
program euklid(input,output);
var r,n,m: integer;
begin read(n); read(m)
r:= n mod m;
while r `" 0 do
begin n:= m ; m := r ;
r := n mod m
end;
write(m)
end.
Przykład
n m r
420 825 420
825 420 405
420 405 15
505 15 0
Przykład
n m r
521 428 93
428 93 56
93 56 37
56 37 19
37 19 18
19 18 1
18 1 0
8
Sito Eratostenesa
Należy wygenerować wszystkie liczby pierwsze, nie większe od danej
liczby naturalnej n.
Rozważmy ciąg 2,...,n wszystkich liczb naturalnych od 2 do n.
Niech a0,a1,...,ak,ak+1,...,am będzie podciągiem tego ciągu otrzymanym
w wyniku wykonania k-kroków tego algorytmu.
Dla k = 0 jest ciąg 2,3,...,n przy czym a0 = 2.
W założeniu indukcyjnym przyjmuje się, że a0,a1,...,ak są kolejnymi
liczbami pierwszymi oraz ak+1,...,am  wszystkimi liczbami naturalnymi i,
ak < i d" n, takimi, że żadna z liczb a0,a1,...,ak nie dzieli i.
W kolejnym kroku usuwa się z ciągu ak+1,...,am wszystkie liczby
podzielne przez ak.
Otrzymuje się ciąg a0,a1,...,ak,a k+1,...,a l. Jeżeli ciąg a k+1,...,a l jest pusty
to STOP.
Uwagi: Skończona liczba kroków postępowania.
Zastosowanie algorytmu Euklidesa
Przykład
2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31
2, 3, 5,7,9,11,12,13,15,17,19,21,23,25,27,29,31
2,3, 5, 7,11,13,17,19,23,25,29,31
2,3,5, 7, 11,13,17,19,23,29,31
2,3,5,7, 11, 13,17,19,23,29,31
.........................................................
2,3,5,7,11,13,17,19,23,29,31
Uwagi:
Generowanie kolejnych liczb pierwszych
Wzór Euklidesa e1 = 2, e2 = 3
e3 = e1 * e2 +1 = 7
e4= e1 * e2* e3 +1 = 43
e5 = e1 * e2* e3 * e4+1 = 1087
...................................
ek = e1 * e2* e3 * ek-1+1
e5 ; e6 ????
Liczby Mersena Mp = 2p  1 ,
p = 2,3,5, 7,13,17,19,31,67,127,257
p = 67 , 257 i 61, 89, 107 ????
9
2. Algorytmy
" Procedury i rekursja.
" Przykłady algorytmów rekurencyjnych.
program euklid(input,output);
var r,n,m: integer;
begin read(n); read(m)
r:= n mod m;
while r `" 0 do
begin n:= m ; m := r ; r := n mod m
end;
write(m)
end.
Procedura definiuje operacje (bloki  fragmenty algorytmów) wykorzystywane w
algorytmie. Procedura musi mieć nazwę oraz opis argumentów, na których będzie
działać.
procedure euklid1 (n,m: integer);
Parametry formalne typ
Rodzajem procedury jest funkcja:
function euklid2 (n,m: integer);integer;
Parametry formalne typ
Przykład p:= euklid2 (7,234) + q
Przykład
function euklid2 (n,m: integer);integer;
var r: integer;
begin r := n mod m;
while r `" 0 do
begin n := m ; m := r ; r := n mod m
end;
euklid2 := m
end.
10
Komunikowanie się parametrów formalnych z aktualnymi:
" Przekazywanie przez wartość
" Przekazywanie przez zmienną
Przykład
procedure euklid3 (n,m: integer; var p: integer));integer;
var r: integer;
begin r := n mod m;
while r `" 0 do
begin n := m ; m := r ; r := n mod m
end;
p:= m
end.
Algorytmy rekurencyjne
Przykład a)
Dany jest ciąg a1,...,an liczb całkowitych, dla n e" 2. Należy wyznaczyć
największą i najmniejsza spośród tych liczb.
Ciąg liczb zadany jest przez tablicę a[1..n]. Aby znalez
ć element
największy rozważmy ciąg jednoelementowy a[1]. Jego największy
element jest równy a[1].
Załóżmy, że a[j] jest największy w ciągu a[1],...,a[i-1]. Porównajmy a[i] z
a[j].
Jeżeli a[i] będzie większy od a[j], oznacza to, że a[i] jest największy w
ciągu a[1],...,1[i], należy zatem zmienić wartość zmiennej j na i.
W przeciwnym razie wartościowanie pozostaje bez zmiany.
Po wykonaniu iteracji aż do i = n, a[j] będzie wskazywało na największy
element w tym ciągu.
Dla wyznaczenia najmniejszego elementu relację > należy zastąpić
relacją <.
program maxmin 1 (input, output);
label 1,2,3; const n = 100;
var i,j,k: integer; a : array [1..n] of integer;
begin
for i:=1 to n do read(a[i]);
1: j:=1; for i :=2 to n do if a[i] > a[j] then j:=i;
2: k:=1; for i :=2 to n do if a[i] < a[k] then k:=i;
3: write(a[j]; write(a[k])
end.
11
Przykład b)
program maxmin 2 (input, output);
label 1,2; const n = 100;
var i,j,k: integer; a : array [1..n] of integer;
begin
for i:=1 to n do read(a[i]); j:=1 ; k:=1;
for i :=2 to n do
1: if a[i] > a[j] then j:=i; else
if a[i] < a[k] then k:=i;
2: write(a[j]; write(a[k])
end.
Uwagi:
Jakie są złożoności (koszty obliczeń) obu algorytmów?
Jakie diagramy przepływu (flowcharty) odpowiadają przedstawionym
algorytmom?
Algorytm porządkowania elementów ciągu.
Jak maleje złożoność obliczeniowa algorytmu porządkowania elementów
ciągu przy zastosowaniu zasady dziel i zwyciężaj (ang. divide and conquer).
Podaj algorytm wyznaczający wartość Fn, n tej liczby Fibonacciego, określonej
następującym wzorem rekurencyjnym:
F0 = 1 , F1 = 1 , Fn+1 = Fn + Fn-1 dla n e" 1.
3. Poprawność algorytmów
" algorytm poprawny  semantyczna poprawność algorytmów.
" poprawność częściowa,
" własność określoności obliczeń,
" własność stopu.
1. Czy ułożony program (zbudowany algorytm) rzeczywiście stanowi
rozwiązanie postawionego problemu?
2. Czy dla realizacji programu (dla potrzeb rozwiązania postawionego
problemu) wystarczy ta ilość czasu pracy komputera i ta ilość
miejsca pamięci, które można dla niego przeznaczyć?
3. Czy zmieniony program na każdym komputerze da te same wyniki,
co program przed modyfikacją?
12
Dana wejściowa algorytmu  wartość dostarczana do algorytmu z zewnątrz
(z programu wywołującego dany algorytm)
Przykład
W programie euklid wielkościami tymi są zmienne n i m. Ich wartości
ustalane są przy wykonywaniu instrukcji wejścia read(n) oraz read (m).
Wynik algorytmu  wartość, która algorytm przekazuje na zewnątrz
(do programu wywołującego dany algorytm)
Przykład
Wynikiem programu euklid jest wartość zmiennej m, którą ten program
wypisuje przy wykonywaniu instrukcji write(m).
Z każdym algorytmem wiążą się warunki:
" Początkowy  podający ograniczenia na dane wejściowe algorytmu
" Końcowy  opisujący własności wyników algorytmu i ich związek z danymi
wejściowymi algorytmu.
Przykład
Dla programu euklid warunek początkowy może być sformułowany:
 wartości wczytywane na zmienne n i m są dodatnimi liczbami
całkowitymi
warunek końcowy natomiast:
 wypisywana wartość jest największym wspólnym dzielnikiem
początkowych wartości n i m
Niech dany algorytm K oraz para warunków opisujących jego działanie:
ą- warunek początkowy oraz � warunek końcowy
Algorytm K jest semantycznie poprawny względem warunków
początkowego ą i końcowego � , jeśli dla każdych danych
wejściowych spełniających warunek ą obliczenie algorytmu K
dochodzi do punktu końcowego oraz wartościowanie zmiennych
spełnia warunek �.
Przykład
Niech instrukcja (algorytm):
for j:=1 to m do A[j] := B[j] , w której j i m są zmiennymi całkowitymi, n 
stałą całkowitą oraz A i B tablicami typu array[1..n] of integer.
13
 Instrukcja ta jest poprawna względem warunków:
początkowego  n > 0 '" m d" n
końcowego  "j=1..m (A[j] = B[j]])
Jest również poprawna dla warunków
 n = m = 100
 Ł (i=1..n) A[i] = Ł (i=1..m) B[i]
 n = m = 0
 " i=1..n (A[i]) = 5)
Nie jest natomiast poprawna względem warunków:
 n > 0
 "j=1..m (A[j] = B[j]])
 n > m
" i=1..n (A[i] `" B[i])
Uwagi:
" Dla każdego algorytmu można dobrać takie warunki, żeby algorytm był
poprawny względem tych warunków.
" Dla każdego algorytmu można dobrać takie warunki, żeby algorytm nie
był poprawny względem tych warunków.
" Warunki początkowy i końcowy zdeterminowane są przez nasze
postulaty, co algorytm ma liczyć.
Przykład
Niech dana instrukcja (algorytm):
begin i:= 0; while i `" u do i := i+1 end. i, u  zmienne rzeczywiste
dla u = -1 lub u = 0.5 - obliczenie instrukcji staje się nieskończone,
obliczanie jest skończone dla u spełniającego własność  u jest liczbą
naturalną
Przykładowe warunki poprawne  u jest liczbą naturalną oraz  u=i
Przykładowe warunki nie poprawne  u>0 oraz  u=i
14
Uwagi:
Niepoprawność algorytmu może być trojakiego rodzaju. Dla pewnych danych
wejściowych obliczenie algorytmu
" albo dochodzi do punktu końcowego, ale wyniki nie spełniają warunku
końcowego
" albo zatrzymuje się w punkcie niekońcowym tego algorytmu
" albo jest nieskończone
Poprawność algorytmu K względem warunków początkowego ą i końcowego
� dowodzi się zwykle przez pokazanie, że algorytm K ma następujące trzy
własności:
1) dla każdych danych wejściowych spełniających warunek początkowy ą
jeżeli obliczenie algorytmu K dochodzi do punktu końcowego, to
otrzymane wyniki spełniają warunek końcowy �
2) dla każdych danych wejściowych spełniających warunek początkowy ą
obliczenie algorytmu K nie jest przerwane
3) dla każdych danych wejściowych spełniających warunek początkowy ą
obliczenie ą algorytmu K nie jest nieskończone.
Jeżeli zachodzi 1) wówczas algorytm K jest częściowo poprawny względem
warunku początkowego ą i końcowego �
Jeżeli zachodzi 2) wówczas algorytm K ma własność określoności obliczeń
względem warunku początkowego ą
Jeżeli zachodzi 3) wówczas algorytm K ma własność stopu względem
warunku początkowego ą
Poprawność algorytmu ustala się zatem dowodząc:
Częściowej poprawności,
Określoności obliczeń
Własności stopu
Podstawową metodą dowodzenia częściowej poprawności i określoności
algorytmów jest tzw. metoda niezmienników, w której opisywane są własności
wartościowań zmiennych otrzymywanych, gdy obliczenie algorytmu przechodzi przez
wyróżnione punkty tego algorytmu.
4 Poprawność algorytmów
" Dowodzenie poprawności częściowej - metoda niezmienników Naur a-Floyd a.
" Dowodzenie własności stopu - metoda liczników iteracji.
15
Dowodzenie poprawności częściowej
Przykład
procedure intdiv (x, y: integer; var q, r: integer);
label 1, 2, 3;
begin {ą: 0 d" '" 0 d" y}
1: q := 0; r := x;
2: while y d" r do
begin q := q+1; r:= r  y end;
3: {�: x: = q*y + r '" 0 d" r < y}
end.
Należy wykazać, że dla każdego obliczenia algorytmu, które startuje z danymi
wejściowymi spełniającymi warunek ą, jeżeli obliczanie algorytmu dochodzi do końca
(do etykiety 3), to wartości zmiennych x, y, q oraz r spełniają warunek końcowy �.
Trzeba zatem wykazać pewna własność obliczeń algorytmu, która łączy
zachodzenie pewnego warunku przy etykiecie 1 z zachodzeniem pewnego
warunku przy etykiecie 3.
Należy zatem skorzystać z tego co się dzieje miedzy etykietami 1 a 3; np. jaki
warunek spełniają wartości zmiennych x, y, q i r w punkcie pośrednim
oznaczonym etykieta 2.
Dokładniej: jaki warunek spełniają wartości zmiennych w chwili sprawdzania
warunku  y d" r sterującego iteracją.
Rozważmy warunek:
ł: x= q*y + r '" 0 d" r '" 0 d" y
Uwagi:
Jeżeli obliczenie algorytmu startuje z danymi wejściowymi spełniającymi
warunek początkowy ą i dochodzi do punktu końcowego, to otrzymane wyniki
spełniają warunek końcowy �  algorytm jest częściowo poprawny
Jeżeli algorytm nie jest poprawny względem rozważanych warunków, np. dla
x = y = 0, wówczas obliczenie tego algorytmu jest nieskończone.
Wyróżniając pewne miejsca w algorytmie, przypisuje się do nich warunki na
wartościowanie zmiennych i wykazuje, że jeżeli początkowy stan obliczania
spełnia warunek początkowy, to ilekroć obliczanie algorytmu dochodzi do
wyróżnionego miejsca, zawsze przyporządkowany temu miejscu warunek jest
spełniony przez aktualne wartościowanie zmiennych.
16
W szczególności jeżeli obliczenie dochodzi do punktu końcowego to końcowe
wartościowanie zmiennych spełnia warunek końcowy algorytmu.
Postępując w ten sposób nie można stwierdzić, czy obliczenie algorytmu w
ogóle dochodzi do punktu końcowego. Stwierdza się tylko, że jeżeli dochodzi,
to jest spełniony warunek końcowy.
Wszystkie działania algorytmu są zawsze określone. Algorytm posiada
własność określoności obliczeń.
Dowodzenie własności stopu
Algorytm K ma własność stopu względem warunku początkowego ą, jeśli
dla każdych danych wejściowych spełniających warunek ą , obliczenie
algorytmu K nie jest nieskończone.
Przy dowodzeniu zwykle stosuje się jedną z metod:
" liczników iteracji
" malejących wielkości
Dowodzenie własności stopu algorytmów metoda liczników iteracji
Brak spełnienia warunku stopu, oprócz przypadków trywialnych, może
wystąpić przy realizacji instrukcji iteracyjnej.
Jak udowodnić więc, że przykładowy algorytm postaci:
 while ł do K ma własność stopu względem warunku początkowego ą
Wprowadz
my dodatkową zmienną całkowitą l, nie występującą ani w warunku ł ani
w instrukcji K, zmienną służącą do obliczania liczby wykonań instrukcji iterowanej K.
Zmienna l nazywa się zwykle licznikiem iteracji  while ł do K
Niech c będzie stała całkowitą (zazwyczaj c = 0 lub c = 1).
Równoważny algorytm ma postać:
M: begin
l:= c
while ł do
begin K; l:= l + 1 end
end
Szukamy wyrażenia arytmetycznego � , którego wartość w trakcie realizacji
algorytmu M ograniczałaby z góry wartość zmiennej l. Zakładamy, że wartości
zmiennych występujących w termie � nie są zmieniane w trakcie realizacji instrukcji
iterowanej begin K; l:= l + 1 end .
17
Skoro dla każdego obliczenia algorytmu M, które rozpoczyna się stanem
spełniającym warunek ą, przy każdym sprawdzaniu warunku iteracji ł warunek � e" l
jest spełniony i wartość � jest stała, więc liczba wykonań instrukcji iterowanej
begin K; l:= l + 1 end jest skończona.
Dowodzenie poprawności algorytmów rekurencyjnych
Stosowana jest indukcja względem wielkości danych wejściowych, dla których
algorytmy są realizowane. Nie zachodzi potrzeba dzielenia całego procesu
dowodzenia poprawności algorytmu na odrębne etapy weryfikacji własności
częściowej poprawności, określoności obliczeń i stopu.
function NWD(x,y: integer): integer
var r: integer;
begin {ą: x > 0 '" y > 0}
r:= x mod y;
if r = 0 then NWD := y else NWD := NWD(y,r)
{�: NWD = (x,y)}
end
(x,y)  oznacza największy wspólny dzielnik dodatnich liczb naturalnych x i y.
Dla wykazania, że funkcja NWD jest poprawna względem warunków ą i � wystarczy
wykazać, że dla każdych dodatnich wartości naturalnych x i y obliczenie wywołania
funkcji NWD(x,y) dochodzi do punktu końcowego z wartością NWD = (x,y)
4. Sprawność algorytmów.
" Miary efektywności algorytmów.
" Złożoność obliczeniowa algorytmów.
" Złożoność pesymistyczna i średnia.
" Dolne i górne ograniczenie złożoności.
" Problemy algorytmicznie zamknięte i otwarte.
Każde wykonanie algorytmu na komputerze wymaga pewnej ilości czasu pracy, jak
również pewnej ilości miejsca pamięci.
Przykład
Rozważmy algorytm, dla którego daną wejściową jest liczbą naturalna n i w
którym liczba jednostkowych operacji wykonywanych dla danej n wynosi n!
Zakładającym że komputer wykonuje średnio 105 jednostkowych operacji na
sekundę i że jest do wyłącznej dyspozycji przez 24 godziny algorytm ten może
być wykonany tylko dla danej wartości n d" 13.
Dla 2n ograniczenie to zwiększa się do n d" 33.
18
Przykład
Przyjmując wcześniejsze założenia, w przypadku algorytmów, których liczba
wykonywanych operacji określa funkcja wielomianowa od wartości danej
wejściowej (rozmiaru zadania), dla algorytmów wykonujących odpowiednio n3,
n2 , n*log(n) operacji w czasie 24 h komputer  poradzi sobie odpowiednio z
n = 2000 ; 90 000 ; 250*106.
Znajomość czasu działania algorytmu przydaje się również wtedy, gdy chcemy
wybrać najoszczędniejszy spośród algorytmów alternatywnych.
PROBLEM - ALGORYTM - KOMPUTER
komputer
algorytm
105 107
n!
13 16
2n
33 42
n3
2000 20 000
Przykład
Dane zadanie należy rozwiązać dla danej wejściowej n = 10 000 przy
użyciu komputera, który wykonuje średnio 105 jednostkowych operacji
na sekundę. Do dyspozycji są 4 algorytmy wykonujące dla danej n
odpowiednio n3 , n2 , n*log(n) jednostkowych operacji. Algorytmy te
wykonają zadanie odpowiednio w: 107 s. czyli ok. 115 dni, 17 minut i 13
sekund.
Pułapka wymiarowości
Problem
Dana jest para (X, c) , gdzie
X - zbiór rozwiązań dopuszczalnych
c: X R - funkcja celu
Należy znalez
ć rozwiązanie x* " X takie, że c(x*) = min c(x)
x " X
19
x  podzbiór zbioru {1, 2, 3,& ,n}; 2n
x  permutacja zbioru {1, 2, 3,& ,n}; n!
Czasy obliczeń: (jedno wyliczenie funkcji celu trwa 1 �s)
n n!
n3 2n
10 0,001 s 0,001 s 3,6 s
20 0,008 s 1,05 s 771,5 stuleci
50 0,125 s 35,7 lat 9,6*1048 stuleci
100 1 s 4,2*1014 stuleci 3,0*10142 stuleci
Wpływ wzrostu mocy obliczeniowej komputera na czasy obliczeń
Rozmiar największego problemu rozwiązywanego
w ciągu godziny
Przez obecny komputer Przez komputer 1000
razy szybszy
n3 N1 10*N1
2n N2
d" N2 + 10
n! N3
d" N3 + 2 (przy n3 > 10)
Miary efektywności algorytmów
o Funkcja kosztu (funkcja złożoności czasowej, pesymistyczna złożoność
czasowa)
o Złożoność średnia, złożoność pamięciowa
20
Dany algorytm K, dla którego zbiorem danych wejściowych jest zbiór D taki, że
dla każdej danej d ze zbioru D obliczenie algorytmu K dochodzi do punktu
końcowego.
Przez t(d) oznaczana jest liczba jednostkowych operacji wykonywanych przez
algorytm K dla danej wejściowej d ze zbioru D.
Odwzorowanie t jest funkcją ze zbioru danych D w zbiór liczb naturalnych
(tzw, pełna funkcja kosztu algorytmu K).
Przykład
Algorytm sprawdzający czy dana liczba naturalna n jest liczba pierwszą.
function prime(n: integer): Boolean;
label 1, 2, 3, 4;
var p: integer; B: Boolean;
begin {ą: n > 0 }
1: p:= 2 ; B:= true;
2: while (p*p d" n) '" B do {(B a"" (q=2..p-1) n mod q `" 0)}
begin
3: if n mod p= 0 then B:= false; p := p+1
end;
4: prime := B
{�: (prime a" " (q=2..n-1) n mod q `" 0)}
end.
Uwaga:
Przykłady operacji jednostkowych: podstawienie, skok,
dodawanie, itp.
Oszacowania liczb jednostkowych operacji wykonywanych przez instrukcje
odpowiadające poszczególnym etykietom:
1)  dokładnie 2 operacje jednostkowe
2)  co najwyżej 3 �ł"n�ł operacji jednostkowych
3)  co najwyżej 4(�ł"n�ł - 1) +1 operacji jednostkowych
4)  dokładnie 1 operacja jednostkowa
Razem wykonywanych jest co najwyżej 7 �ł"n�ł jednostkowych operacji
Uwaga:
W przypadku gdy n jest liczba pierwsza wykonuje się dokładnie
t(n) = 7�ł"n�ł - 1 operacji jednostkowych
W przypadku gdy n jest kwadratem liczby pierwszej t(n) = 7�ł"n�ł
W przypadku gdy n jest liczbą parzysta wówczas t(n) = 14
21
Niech X dowolny zbiór, a f i g funkcje przekształcające zbiór X w zbiór liczb
rzeczywistych.
Funkcja f jest co najwyżej rzędu funkcji g , f = O(g), jeśli istnieje stała c > 0 taka,
że nierówność |f(x)| d" c|g(x)| zachodzi dla prawie wszystkich x " X .
Pełna funkcja kosztu algorytmu prime jest, co najwyżej rzędu "n,
tzn. t(n) = O("n)
Funkcja f jest dokładnie rzędu funkcji g , oznaczenie f = Ś(g), jeżeli istnieją stałe
c1 , c2 większe niż 0 jakie, że nierówności c1|g(x)| d"|f(x)| d" c2|g(x)| zachodzi dla
prawie wszystkich x "X .
Ilustracja
Zbiór wszystkich ciągów o długości n
3n2 + 8n + 4
2nlogn + 4n + 3
2n + 3
Uwaga
Dolne i górne ograniczenie złożoności obliczeniowej, złożoność
pesymistyczna.
3n2 + 8n + 4 n2
Złożoność obliczeniowa algorytmu porządkowania n liczb jest O(n2)
22
Dokładniej:
Rozmiar problemu - długość ciągu kodującego binarnie wszystkie dane problemu.
(Praktycznie  liczba danych charakteryzujących problem)
Złożoność obliczeniowa algorytmu dla danego problemu o rozmiarze n  liczba
elementarnych operacji, które musi wykonać algorytm aby przy
najbardziej niesprzyjających danych rozwiązać problem o
rozmiarze n.
Uwaga:
Przy analizie złożoności algorytmów (czasowej złożoności) zwykle rozważa się
tzw, operacje dominujące algorytmu.
Oprócz złożoności czasowej algorytmu rozważa się również złożoność
pamięciową.
Średnia złożoność czasowa  funkcja T(w) = Ł Prw(d) t(d) odwzorowująca
|d|=w
zbiór rozmiarów danych W w zbiór liczb
rzeczywistych, gdzie:
Prw(d)  prawdopodobieństwo wystąpienia
na wejściu algorytmu danej d rozmiaru w
Przykład
Dane wejściowe algorytmu tworzy liczba naturalna n i permutacja a zbioru
liczb {1, 2, 3,& ,n}. Przyjmujmy, że rozmiarem danej d = (n,a) jest n,
tzn. |d| = n.
Przyjmując, że każda permutacja n elementowa jest jednakowo
prawdopodobna, otrzymujemy Prw(d) = 1/n! dla każdej danej d rozmiaru
n.
Problemy algorytmiczne zamknięte i otwarte
" Algorytm porządkowania liczb.
" Algorytm wyznaczania kolejnych liczb pierwszych
" Algorytm sprawdzania czy dana liczba naturalna jest liczbą pierwszą
" . . .
23
6. Klasyfikacja problemów algorytmicznych
" problemy łatwo i trudno rozwiązywalne
" klasy problemów algorytmicznych
Problemy łatwo i trudno rozwiązywalne
(a) (b)
PROBLEMY PROBLEMY
TRUDNE A
ATWE DECYZYJNE OPTYMALIZACYJNE
Przykład (problem sortowania)
Dany jest zbiór {7, 5, 6, 1, 3, 4 , 2, 9, 8, 10}. Zbiór ten należy uporządkować
(posortować) od najmniejszego do największego elementu, tzn. {1, 2, 3 , 4 , 5
, 6 , 7 , 8 , 9 , 10}. Ile, w najgorszym przypadku, należy dokonać
elementarnych porównań i przestawień elementów zbioru, aby go
uporządkować?
Przyjmując zasadę porządkowania wg. algorytmu  bąbelkowego liczba ta nie
n2 n
-
przekracza , gdzie n  liczność porządkowanego zbioru. Złożoności
2 2
obliczeniową tego problemu określa funkcja O(n2)
Przykład (problem plecakowy)
Dany jest zbiór A = {ai | i = 1,n} różnych typów towarów. Każda jednostka
danego typu towaru ma tę sama objętość gi (wagę wi) oraz cenę ci.
Dysponujemy plecakiem o pojemności G (możemy udz
wignąć W).
Ile, jakich towarów należy załadować do plecaka aby wyjść z maksymalnym
zyskiem?
Przyjmując, że jednostek każdego towaru jest ta sama ilość m, liczba
wszystkich wariantów nie przekracza mn. Złożoności obliczeniową tego
problemu określa funkcja O(mn).
24
Przykład (problem komiwojażera)
Komiwojażer, każdego dnia odwiedza n  miast. Dane są odległości di,j
pomiędzy każdą para miast i i j. Startując z wybranego miasta, należy
powrócić do niego przejeżdżając przez każde z pozostałych miast tylko jeden
raz.
Która z tras jest najkrótsza?
Liczba wszystkich tras, które trzeba sprawdzić nie przekracza (n-1)!
Złożoności obliczeniową tego problemu określa funkcja O(n!)
Problemy decyzyjne i optymalizacyjne.
Spotykane problemy dzielą się też na problemy decyzyjne i optymalizacyjne.
Przyjmując konwencję, wg., której każdy problem charakteryzuje trójka
(DANE, OGRANICZENIA, PYTANIE), za problem decyzyjny uznaje się taki, w
którym pytania są formułowane w taki sposób aby udzielana na nie odpowiedz

była postaci TAK lub NIE.
Z kolei za problem optymalizacyjny przyjmuje się taki, którego pytanie jest
sformułowane w taki sposób, aby udzielana na nie odpowiedz
dotyczyła
ekstremum pewnej funkcji celu.
Z każdym problemem optymalizacyjnym można związać problem decyzyjny.
Przykład
Problem plecakowy (problem optymalizacyjny)
Dany jest zbiór A = {ai | i = 1,n} różnych typów towarów. Każda jednostka
danego typu towaru ma tę sama objętość gi (wagę wi) oraz cenę ci.
Dysponujemy plecakiem o pojemności G (możemy udz
wignąć W). Ile, jakich
towarów można załadować do plecaka aby wyjść z maksymalnym zyskiem?
Przestrzeń stanów (wartości zmiennej decyzyjnej) PS = N0 x N0 x...x N0
obejmuje stan początkowy X = (0, 0, ..., 0) oraz stan końcowy
X* = (x1,x2,...,xn) spełniający warunki funkcji celu, tzn.,
25
n
X*= max( Ł xi ci)
i=1
n
Przy ograniczeniach Ł xi gi d" G
i=1
n
(Ł xi wi d" W )
i=1
Przykład
Problem plecakowy (problem decyzyjny)
Przy identycznym sformułowaniu i tych samych ograniczeniach funkcja celu
ma postać:
n
Ł xi ci d" F
i=1
Uwaga
Zmniejszenie złożoności obliczeniowej można uzyskać bądz
to poprzez
odpowiednie przedefiniowanie problemu, bądz
też przeformułowanie problemu
(zmieniające strukturę danych).
Przykład (Zasada dziel i zwyciężaj)
Zbiór danych jest dzielony na dwa rozłączne zbiory, prawie równoliczne, dla
których w dwóch następnych krokach są rozwiązywane podobne problemy.
Postępowanie takie pozwala zmniejszyć złożoność obliczeniową algorytmu.
Problem sortowania. Dany jest zbiór {7, 5, 6, 1, 3, 4 , 2, 9, 8, 10}. Zbiór ten
należy uporządkować (posortować) od najmniejszego do największego
elementu, tzn. {1, 2, 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10}.
Przyjmując zasadę porządkowania wg. algorytmu  bąbelkowego złożoność
obliczeniowa dana jest funkcją n2/2 - n/2,
czyli: 100/2 -10/2 = 45 porównań.
W przypadku gdy zbiór ten wstępnie podzielimy na dwa, tzn. {7, 5, 6, 1, 3} ,
{4 , 2, 9, 8, 10} to na wynikową złożoność obliczeniową składają się trzy
składniki:
(n/2)2/2 - (n/2)/2 + (n/2)2/2 - (n/2)/2 + n
a zatem 52/2 - 5/2 + 52/2 - 5/2 + 10
52 - 5 + 10 = 25 - 5 + 10 = 30 porównań.
26
Czy dalszy podział zbioru wyjściowego na 4 lub 6 podzbiorów zmniejszyłby
złożoność obliczeniową?
Problem  Specyfikacja problemu  Algorytm
Schemat postępowania przy rozwiązywaniu problemów kombinatorycznych
Próba znalezienia algorytmu wielomianowego
sukces brak sukcesu
alg. o złożoności (nk)
próba zmniejszenia próba wykazania
wykładnika k NP-zupełności
brak sukcesu sukces
konstrukcja alg.
przybliżonego
Metody przeszukiwania
Metody deterministyczne (wolne od przypadku) są realizacjami schematu
ogólniejszego  metody prób i błędów.
Algorytm niedeterministycznych  algorytm realizujący techniki  prób i
błędów składający się z dwóch faz: niedeterministycznej, polegającej na
odgadywaniu, i deterministycznej, polegającej na sprawdzaniu. Algorytm
niedeterministyczny ma złożoność wielomianową, gdy taka złożoności ma
odpowiednia procedura weryfikacji.
Klasy problemów
Klasa problemów typu P  klasa problemów rozpoznawania, które dadzą się
rozwiązać za pomocą wielomianowych algorytmów
deterministycznych.
27
Klasa problemów typu NP  klasa problemów rozpoznawania, które dadzą się
rozwiązać za pomocą wielomianowych algorytmów
niedeterministycznych.
Uwagi:
" P �" NP
" Trudno sobie wyobrazić aby metodę prób i błędów  nawet prz założeniu
szybkiej weryfikacji hipotez - można było zawsze zastąpić szybkim
algorytmem deterministycznym. Stąd hipoteza: P `" PN.
Problem NP-zupełny  problem należący do takiej klasy problemów, że jeżeli
udałoby się dla jednego problemu z tej klasy zbudować algorytm
wielomianowy to algorytm taki istniałby dla każdego pozostałego
problemu z tej klasy.
Gdyby natomiast wykazano, że nie istnieje algorytm wielomianowy dla
jednego, to nie istniałby dla każdego problemu z tej klasy.
NP  Nondeterministic Polynomial
Przykład (najprostszy problem NP-zupełny)
Problem podziału n liczb naturalnych a1 , a2, & , an. Czy istnieje podzbiór
A �" N = {1,2,3,& ,n} taki, że
Ł ai = Ł ai
i"A i"N\A
N = 9
3 4 3 2
3 1 3 2
2
N\A
A
2
4 3
3
3 1 2 5 3
28
Nikt nie podał algorytmu, którego liczba elementarnych kroków zależy wielomianowo
od liczby kulek n.
7. Klasyfikacja problemów algorytmicznych
" dowodzenie NP-zupełności
Metodyka dowodzenia NP-zupełnosci
1. Przejść z badanego problemu optymalizacyjnego 1 na problem
decyzyjny.
Problem optymalizacyjny:
Znajdz
x* " X takie, że c(x*) = min c(x)
x"X
Problem decyzyjny:
Znajdz
x* " X takie, że c(x*) d" y
2. Wielomianowa weryfikacja:
Pokazać, że dla każdego rozwiązania x oraz  poziomu y, sprawdzenie
 czy x " X oraz c(x*) d" y
można wykonać algorytmem wielomianowym od rozmiaru badanego
problemu decyzyjnego 1.
3. Znalez
ć  zbliżony do problemu 1 , problem 2 , o którym wiemy, że
jest NP-zupełny. Pokazać, że problem 2 jest wielomianowo transformowany do
problemu 1 .
D( ) - zbiór wszystkich indywidualnych problemów (instancji),
problemu .
Y( ) - zbiór tych instancji problemu , dla których odpowiedz
brzmi
 TAK ; Y( ) �" D( ).
Transformacja wielomianowa pomiędzy problemami 2 i 1.
f: D( 2) D( 1)
29
" złożoność wyznaczenia wartości f(I) dla każdej instancji I, I " D( 2),
jest ograniczona przez wielomian od rozmiaru tej instancji
" odpowiedz
dla instancji I problemu 2 brzmi  TAK wtedy i tylko wtedy,
gdy dla instancji f(I) problemu 1 też brzmi  TAK
 TAK dla I z 2 �!  TAK dla f(I) z 1
Ilustracja transformacji wielomianowej
Problem NP-zupełny nasz problem
D( 2) D( 1)
Y( 1)
Y( 2)
30
Przykład
Problem plecakowy (załadunku) 1
- n elementów (elementów N = {1, 2, 3,& ,n} ); element j" N jest
określony przez jego ciężar cj i wartość wj,
- ciężar plecaka po załadowaniu nie może przekroczyć C.
Należy tak załadować plecak, żeby miał największą wartość
Znalez
ć podzbiór A �" N taki, że
Ł wi max
i"A
Ł ci d" C
i"A
Problem decyzyjny
Czy istnieje dla poziomu W (zadanej dolnej wartości plecaka), podzbiór elementów
A �" N taki, że
Ł wi e" W 1)
i"A
Ł ci d" C 2)
i"A
2. Wielomianowa weryfikacja:
Rozmiar problemu 1 - n
Dla danego poziomu W oraz podzbioru A �" N sprawdzenie, czy
zachodzą nierówności 1) i 2) wymaga
2(n-1) - dodawań
2 - porównań
A
ącznie 2n elementarnych porównań
Oznacza to, że możliwa jest wielomianowa weryfikacja.
31
3. Wielomianowa transformacja:
Znany jest problem NP-zupełny:
Problem podziału zbiór 2 - n liczb naturalnych a1 , a2 , a3 ,& ,an
Transformacja
2 2
wartość ciężar
a1 w1 c1 w1 = c1 = a1
a2 w2 c2 w2 = c2 = a2
f
. . .
. . .
. . .
an wn cn wn = cn = an
W C W = C = S/2
S = Ł aj
2 2
Ł wi e" W
Ł ai = Ł ai
i"A
i"A i"N\A
Ł ci d" C
i"A
Ł ai e" � Ł ai
i"A i"N
Ł ai = Ł ai
i"A i"N\A
Ł ai d" � Ł ai
i"A i"N
Ł ai = Ł ai �! Ł ai e" � Ł ai
i"A i"N\A i"A i"N
32
8. Prymitywne modele algorytmiczne.
- maszyna Turinga i jej warianty.
- przykłady implementacji wybranych algorytmów.
Turing zauważył, że każdy w pełni mechaniczny proces obliczeń
składa się z następujących operacji:
- odczytywanie symboli,
- wymazywanie i zapisywanie symboli
- zapamiętywanie i przenoszenie informacji
Obserwacje te doprowadziły do poniższej konstrukcji:
JEDNOTAŚMOWEJ DETERMINISTYCZNEJ MASZYNY TURINGA
(maszyny Turinga)
Maszyna Turinga  składa się z taśmy, głowicy pisząco-czytającej oraz urządzenia
sterującego.
Obustronnie nieskończona taśma podzielona jest na klatki, z których każda
zawiera najwyżej jeden symbol skończonego alfabetu, zwanego alfabetem
roboczym maszyny.
W dowolnym momencie prawie wszystkie klatki są puste  zawierają element
wyróżniony b (ang. blank  pusty).
Głowica ma w polu swojego działania zawsze dokładnie jedna klatkę.
Urządzenie sterujące pełni funkcje pamięcią; w każdym momencie znajduje
się ono w jednym ze skończonej liczby stanów.
Maszyna Turinga pracuje w czasie dyskretnym, tzn. kolejne ruchy numerowane
mogą być liczbami naturalnymi.
Każdy ruch jest jednoznacznie określony przez aktualny stan urządzenia
sterującego i odczyt głowicy.
Pojedynczy ruch składa się z trzech operacji:
- Symbol odczytywany przez głowicę może być zastąpiony nowym
symbolem,
- Urządzenie sterujące może przejść w nowy stan
- Głowica musi przesunąć się o jedną klatkę w lewo (L) lub w prawo (P)
W zbiorze stanów wyróżnia się stan początkowy So (START) i stan końcowy (HALT).
Przejściu maszyny w stan {SY , SN} (HALT), wyjątkowo, nie musi towarzyszyć
przesunięcie głowicy.
Maszyna Turinga znajduje się w konfiguracji początkowej, jeśli:
- Urządzenie sterujące znajduje się w stanie START
- Niepuste klatki tworzą skończony odcinek taśmy
- Głowica odczytuje zawartość pierwszej niepustej klatki.
Zawartość niepustej części taśmy w momencie rozpoczęcia obliczeń tworzy ciąg
zwany SA
OWEM wejściowym (lub DANYMI wejściowymi) maszyny.
33
Przykład
Rozważmy maszynę obliczająca funkcję f(x) = x + 1 w układzie dwójkowym.
Oznacza to, że jeśli w konfiguracji początkowej niepusta część taśmy była
zapisem dwójkowym liczby x, to po zatrzymaniu niepusta część taśmy będzie
zapisem x + 1.
Symbol
Stan
0 1 b
START 0 START R 1 START R LEFT L
LEFT 1 HALT 0 LEFT L 1 HALT
Uwaga
START: Jeżeli odczytasz b, przesuń głowice w lewo i przejdz
do LEFT; w
przeciwnym razie przesuń głowicę w prawo i powtórz START (szukanie
końca x).
LEFT: Jeżeli odczytasz 1, zastąp ją przez 0, przesuń głowicę w lewo i powtórz
LEFT, w przeciwnym razie symbol odczytany zastąp jedynką i
zatrzymaj się.
START ..b b1 1 b b...
START ...b b1 1 b b...
START ...b b1 1 b b...
LEFT ...b b1 1 b b...
LEFT ...b b 1 0 b b...
LEFT ...b b 0 0 b b...
START ...b 1 0 0 b b...
Złożoność maszyny Turinga - funkcja wyrażająca maksymalna liczbę ruchów
maszyny w zależności od rozmiaru danych wejściowych (tzn. liczby
klatek przez nie zajmowanych).
Maszyna Turinga jest automatem reagującym na sygnały wejściowe i zmieniającym
swój stan oraz wytwarzającym sygnał wyjściowy. Jest urządzeniem sterującym
ruchem głowicy zapisująco-odczytującej G, odbierającej sygnał wejściowy z komórek
taśmy T oraz programującym swoje działanie poprzez przekodowanie symboli
wejściowych i tworzenie nowych ciągów symboli
34
Automat
S *"{S0}
Skończony
�
alfabet
Sterowanie (przesuwnie)
symboli
"
ń
Drukowanie nowego
G
symbolu
Działanie maszyny określa:
- Skończony zbiór symboli taśmy �, podzbiór symboli wejściowych Ł oraz
wyróżniony symbol pusty b
- Skończony zbiór stanów S, zawierający wyróżniony stan początkowy S0 i dwa
wyróżnione stany końcowe Sy (odpowiedz
tak) oraz Sn (odpowiedz
nie)
- Program maszyny zadany funkcją przejść �(S\{Sy,Sn}) x � S x � x {-1,1}
- Dane wejściowe stanowi słowo x " Ł, elementy którego są w kolejnych
komórkach taśmy (w każdej komórce dokładnie jeden symbol). Pozostałe
komórki zawierają początkowo symbol pusty.
W chwili startu głowica odczytuje zawartość pierwszej komórki. Jeżeli
maszyna jest w stanie s " S\{Sy,Sn} a w komórce nad którą znajduje się
głowica jest symbol ł"�, to maszyna wykonuje czynność określoną przez
funkcję przejścia �(S, ł) = (s , ł ,"). Oznacza to, że głowica w miejsce
symbolu ł wpisuje symbol ł , przesuwa się o jedną komórkę w lewo " = -1, w
prawo " = 1, stan maszyny zmienia się na s . Wykonanie programu
realizowane jest do chwili, w której maszyna znajdzie się w jednym z dwóch
stanów Sy lub Sn.
Przykład
Należy napisać program umożliwiający maszynie sprawdzanie czy dana liczba
naturalna jest liczbą parzystą. A
atwo zauważyć, że jeżeli liczbę te zapiszemy
w systemie dwójkowym to wystarczy sprawdzić czy ostatnia jej pozycja jest 0.
Przyjmijmy, że � = {0,1,b}, Ł - {0,1} , S = {S0,S1,Sy,Sn}. Rozważmy program
zadany funkcją przejść.
x
0 1 b
S
S0 (S0,0,+1) (S0,1,+1) (S1,b,-1)
S1 (Sy,b,-1) (Sn,b,-1) (S0,b,+1)
Działanie programu przetestujmy na przykładzie liczby 13. W zapisie dwójkowym
mamy zatem słowo: 1101. Wykonanie programu zilustrowane zostało na rysunku.
35
S0
b 1 1 0 1 b
S0
b 1 1 0 1 b
S0
b 1 1 0 1 b
S0
b 1 1 0 1 b
S0
b 1 1 0 1 b
S1
b 1 1 0 1 b
Sn
b 1 1 0 b b
W podobny sposób można zaproponować programy wykrywające
parzystość liczby, jej podzielność, itp.
Każda maszyna Turinga jest abstrakcyjnym modelem jednofunkcyjnego komputera
o potencjalnie nieskończonej pamięci
NIEDETERMINISTYCZNA MASZYNA TURINGA  stan maszyny oraz odczyty
głowic nie określają ruchu w sposób jednoznaczny.
W szczególności, oznacza to, że maszyna rozpoczynając pracę nad
ustalonym słowem wejściowym, może przy pewnym wariancie obliczeń
zakończyć prace w stanie SY, przy innym w stanie SN, albo też prowadzić
obliczenia w nieskończoność.
Problem stopu  Dana jest maszyna Turinga. Dla jakich danych wejściowych
praca tej maszyny zakończy się po skończonym czasie?
36
Dwutaśmowa maszyna Turinga
Przykład
Rozpoznawanie palindromów (słowa czytane tak samo od przodu jak i
od tyłu, np. Ala , 0100010) nad alfabetem {0, 1}.
q q
0 1 1 1 0 b b . . .
0 1 1 1 0 b b . .
b b . . .
x 0 1 1 1 0 b .
q
0 1 1 1 0 b b . .
x 0 1 1 1 0 b
1. Pierwsza klatka taśmy 2 oznaczana jest specjalnym symbolem X , i całe
słowo wejściowe jest kopiowane z taśmy 1 na taśmę 2.
2. Głowica taśmy 2 przesuwa się do symbolu X
3. Iteracyjnie głowica taśmy 2 przesuwa się o jedna klatkę w prawo, a
głowica taśmy 1 o jedna klatkę w lewo oraz odpowiednie symbole czytane
przez głowice są porównywane.
Jeżeli słowo jest palindromem, maszyna przechodzi do stanu końcowego, w
przeciwnym razie maszyna znajdzie się w stanie, dla którego funkcja przejścia
jest już nie określona i nie może wykonać kolejnego kroku.
37
9. PRYMITYWNE MODELE ALGORYTMICZNE.
- Teza Churcha-Turinga.
Problem stopu  Dana jest maszyna Turinga. Dla jakich danych wejściowych praca
tej maszyny zakończy się po skończonym czasie?
Twierdzenie Turinga o
NIEROZSTRZYGALNOŚCI PROBLEMU STOPU (1935)
Problem stopu dla dostatecznie skomplikowanej maszyny
Turinga jest nierozstrzygalny.
Przykład
Dane: Równanie diofantyczne n zmiennych.
Program: Generuj kolejno uporządkowane n-tki liczb całkowitych.
Zatrzymaj się jeśli któraś z nich okaże się rozwiązaniem
równania.
Uwaga
Rozstrzygnięcie problemu stopu w tym wypadku zakłada
umiejętność rozstrzygania istnienia rozwiązania całkowitego (dla
dowolnego równania diofantycznego).
Przykład
"x "y (x=y '" x(" y) dziedzina liczb naturalnych / dziedzina liczb rzeczywistych
"x " y (y * y = x) obie dziedziny
Twierdzenie Tarskiego o
ROZSTRZYGALNOŚCI ELEMENTARNEJ ARYTMETYKI LICZB
RZECZYWISTYCH (1951)
Istnieje algorytm pozwalający o dowolnym zdaniu elementarnej
arytmetyki rozstrzygnąć czy jest ono prawdziwe w zbiorze liczb
rzeczywistych.
38
Twierdzenie Churcha o
NIEROZSTRZYGALNOŚCI ELEMENTARNEJ ARYTMETYKI LICZB
NATURALNYCH (1936)
Nie istnieje algorytm, który o dowolnym zdaniu elementarnej
arytmetyki pozwalałby rozstrzygać, czy jest ono prawdziwe w
zbiorze liczb naturalnych
Przykład
Czy równanie x2  2y3 = 1 ma rozwiązanie w zbiorze liczb
całkowitych; wystarcza sprawdzić czy któreś z poniższych zdań jest
prawdziwe w zbiorze liczb naturalnych
"x "y (x2  2y3 = 1) , "x "y (x2  2y3 = 1)
Uwaga
Istnienie algorytmu oznacza teoretyczną rozstrzygalność problemu.
Twierdzenia Churcha i Turinga ukazują obiektywne ograniczenia metod
algorytmicznej  matematyki zautomatyzować się nie da.
Jaki jest zatem związek maszyny Turinga z intuicyjnym pojęciem algorytmu.
TEZA CHURCHA
W obrębie liczb naturalnych intuicyjne pojecie algorytmu
może być utożsamiane z pojęciem maszyny Turinga
Oznacza to, że każdy problem rozwiązywalny algorytmicznie może być rozwiązany
na pewnej maszynie Turinga. I oczywiście na odwrót.
Teza Churcha nie jest twierdzeniem: postuluje ona bowiem zgodność formalnej
definicji z intuicją. Oznacza to, że nigdy nie będziemy jej w stanie udowodnić z
zachowaniem rygorów matematycznej ścisłości.
39
10 J
ZYKI SYSTEMÓW INFORMACYJNYCH.
- System informacyjny.
- Składania i semantyka języka.
- Reguły przekształcania termów.
SYSTEM INFORMACYJNY
" Skończony zbiór obiektów X, i skończony zbiór atrybutów A.
" Z każdym atrybutem a " A związany jest zbiór jego wartości Va nazywany
dziedziną atrybutu a.
" Przyjmuje się, że dziedzina każdego atrybutu jest co najmniej dwuelementowa
" System opisywany jest funkcją dwuargumentową g, która każdemu obiektowi
x " X i atrybutowi a " A przyporządkowuje wartość v należącą do dziedziny
Va atrybutu a.
System informacyjny jest czwórka uporządkowaną:
S = (X, A, V, g)
gdzie:
X  skończony zbiór obiektów
A  skończony zbiór atrybutów
V = *" Va
(a " A)
Va  dziedzina atrybutu a w systemie S
Va = { v " V | dla których istnieje a " X, takie że g(x,a) = v}
g  funkcja całkowita (określona dla wszystkich wartości argumentów x oraz a,
g: X x X V ; przy czym g(x,a) " Va dla każdego x " X oraz a " A.
Przykład
System informacyjny gdzie obiektami są ludzie a atrybutami ich nazwiska,
imiona, itd.
X NAZWISKO IMI
MIEJSCE ROK STAN
URODZENIA URODZENIA CYWILNY
X1 Kowalski Jan Kraków 1958 kawaler
X2 Nowak Jerzy Warszawa 1930 Wdowiec
X3 Lipinski Gabriel A
ódz
1960 żonaty
. . . . . . . . . . . . . . . . . .
X336 Baran A
ukasz Gdańsk 1977 kawaler
Deskryptor  para (a,v), gdzie a  atrybut, v " Va wartość atrybutu a należąca do
jego dziedziny.
Przykład
(NAZWISKO,Kowalski), (KOLOR OCZY, niebieski), itp.
40
Informacja o obiekcie x w systemie S (równoważnie: dane o obiekcie)
gx(a) = g(x,a).
Informacją o obiekcie w danym systemie S jest po prostu zbiór wartości
wszystkich atrybutów obiektu w danym systemie.
Przykład
NAZWISKO IMI
MIEJSCE ROK STAN
gx2 URODZENIA URODZENIA CYWILNY
Nowak Jerzy Warszawa 1930 Wdowiec
Opisem obiektu x w systemie S nazywamy zbiór deskryptorów wyznaczany
przez informacje o obiekcie x.
WA
ASNOŚCI SYSTEMÓW INFORMACYJNYCH
Oprócz pojęcia informacji o obiekcie systemu skorzystajmy z pojęcia informacji w
systemie.
Informacja w systemie - każda funkcja � o argumentach w zbiorze atrybutów A
oraz o wartościach należących do V, taka że �(a) " Va
Wszystkich możliwych (różnych) informacji w systemie jest " card (Va)
a" A
Przykład
Jeżeli w systemie występują trzy atrybuty a1 , a2 , a3 oraz atrybut a1 może
przyjmować dwie wartości, atrybut a2 - trzy wartości, atrybut a3  również trzy
wartości, to system taki ma 2* 3* 3 = 18 różnych informacji.
Informacją w systemie mogą być np. opisy:
(a1,v1), (a2,v2), (a3,v3)
(a1,u1), (a2,u2), (a3,u3)
(a1,w1), (a2,w2), (a3,w3)
Uwaga
Każda informacja � wyznacza pewien zbiór obiektów X� , takich że
X� = {x " X | �x =�}
tzn. obiektów mających w systemie jednakowa informacje (jednakowy opis).
Przedmioty o tym samym opisie są nierozróżnialne w systemie S (są
identyczne).
Przykład
41
" Każda informacja dotyczy tylko jednego obiektu  systemy telefoniczne
" Danemu opisowi odpowiada kilka obiektów  systemy biblioteczne
" Danej informacji nie odpowiada żaden obiekt w systemie - informacja pusta
X� = "
System informacyjny zupełny (kompletny)  gdy każda informacja jest nie pusta.
System informacyjny selektywny  gdy każdej informacji odpowiada co najwyżej
jeden obiekt.
Przykład
System informacji telefonicznej jest selektywny, natomiast system informacji
bibliotecznej (czy patentowej) jest na ogół nieselektywny.
Przykład
Niech system informacyjny S = (X,A,V,g), w którym
X = {x1, x2 , x3 , x4}
A = {a, b , c}
Va = {p1 , p2}
Vb = {q1 , q2 , q=3}
Vc = {r1 , r2 , r3}
Funkcja g jest określona za pomocą tablicy
X a b c
x1 p1 q2 r1
x2 p1 q3 r2
x3 p1 q2 r1
x4 p2 q1 r3
Funkcja � taka, że �(a) = p1 , �(b) = q2 , �(c) = r1 lub opis (a,p1), (b,q2), (c,r1)
jest informacją w systemie , oraz X� = {x1, x3}
Patrz tabela lub poniższe wyliczenia
X� = {x " X | gx = � } =
= {x " X | "(a"A) gx(a) = � (a)} =
= )" ({x"X | g(x,a) = � (a)} =
a"A)
= {x"X | g(x,a) = p1} )" {x"X | g(x,b) =q2} )" {x"X | g(x,c) = r1} =
42
= {x1, x2 , x3} )" {x1 , x3} )" {x1 , x3} =
= {x1, x3}.
System ten nie jest ani selektywny ani kompletny. Obiekty x1 , x3 mają jednakową
informację w tym samym systemie oraz istnieją w nim informacje, którym nie
odpowiadają żadne obiekty w systemie, np. (a,p1), (b,q1), (c,r1).
RÓWNOWAŻNOŚĆ OBIEKTÓW W SYSTEMIE
Wprowadz
my dwie relacje dwuargumentowe
Obiekty x,y"X są nierozróżnialne w systemie S ze względu na atrybut a"A
(symbolicznie x ~a y ) wtedy i tylko wtedy, gdy gx(a) = gy(a).
Obiekty x,y"X są w systemie S nierozróżnialne ze względu na każdy atrybut a"A
(albo krótko: są nie rozróżnialne w systemie S) symbolicznie x ~S y lub krótko x ~ y
wtedy i tylko wtedy, gdy gx = gy.
Przykład
Obiekty x1 , x4 są rozróżnialne ze względu na atrybut a, ponieważ
gx1(a) = gx2(a).
Natomiast obiekty x1, x3 są nierozróżnialne ze względu na każdy atrybut
systemu, ponieważ gx1 = gx2.
Własność
Dla każdego systemu informacyjnego S= {X, A , V, g} relacje ~a i ~ są
relacjami równoważności określonymi na zbiorze obiektów X i ponadto
spełniają one warunek
~S = )" ~a
(a " A)
Uwaga
" Każda relacja równoważności dzieli zbiór, na którym jest określona, na
rozłączne klasy  bloki
" Bloki podziału wyznaczonego przez relację ~S nazywane są blokami
(zbiorami) elementarnymi systemu informacyjnego S.
Przykład
Niech system informacyjny S = (X, A, V, g), w którym
X = {x1, x2 , x3 , x4 , x5 , x6}
A = {a, b}
Va = {p1 , p2}
Vb = {q1 , q2 }
43
Funkcja g jest określona za pomocą tablicy
X a b
x1 p1 q1
x2 p1 q1
x3 p1 q2
x4 p2 q1
x5 p2 q1
x6 p2 q2
Występują zatem następujące podziały
Atrybut a dzieli zbiór X na bloki
B1 = {x1 , x2 , x3 }
B2 = {x4 , x5 , x6}
Atrybut b dzieli zbiór X na bloki
B3 = {x1 , x2 , x4 , x5}
B4 = {x3 , x6}
Podział odpowiadający iloczynowi podziałów ~a i ~b składa się z bloków
B5 = {x1 , x2}
B6 = {x4 , x5}
B7 = {x3}
B8 = {x6}
Bloki B5  B8 sa blokami elementarnymi
x1 x2 x3 x1 x2 x3 x1 x2 x3
)" =
x4 x5 x6 x4 x5 x6 x4 x5 x6
~a ~b ~a )" ~b
44
Uwaga
Każdy system informacyjny wyznacza jednoznacznie pewien podział zbioru
obiektów (a więc pewną ich klasyfikację) i odwrotnie, każda klasyfikacja
obiektów oznacza pewien system informacyjny.
J
ZYKI SYSTEMÓW INFORMACYJNYCH
System informacyjny  języki zapytań
Pytania dotyczące zbiorów obiektów  pytania mnogościowe
Np. Podaj wszystkie książki z dziedziny X, wydane po roku Y w języku Z.
Pytania dotyczące związków miedzy obiektami  pytania relacyjne.
Np. podaj wszystkich spadkobierców X
Pytania dotyczące liczby elementów (zbiorów lub relacji)  pytania liczbowe
Np. Ile osób zna język angielski?
Pytania związane z koniecznością wykonania pewnych obliczeń  pytania
numeryczne.
Np. Podać średnie wynagrodzenie pracowników działu X w roku Y.
Pytania wymagające sprawdzenia zachodzenia pewnych warunków (relacji pomiędzy
obiektami)  pytania logiczne.
Np. Czy X jest autorem książki Y?
Język  jego konstrukcja może obejmować różne rodzaje pytań, może też dotyczyć
tylko jednego rodzaju pytań.
Rozważamy składnię języka na przykładzie pytań mnogościowych, tzn.
języka mnogościowego, którego odpowiedziami na pytania są pewne
zbiory obiektów systemu.
LS  język systemu informacyjnego S.
Składnię języka LS determinują reguły, według których budowane są wyrażenia
(termy) poprawne w tym języku.
Termy zbudowane są z symboli alfabetu, do którego należą:
1. deskryptory systemu, tj. pary symboli postaci (a,v), gdzie a"A, v"Va ;
2. stałe 0, 1;
3. symbole operacji ~, * , + , , zwane odpowiednio: negacja, koniunkcją,
alternatywą, implikacją i równoważnością.
Symbole operacji można uważać za skróty spójników logicznych:  nie ,  i ,
 lub ,  jeżeli& to ,  wtedy i tylko wtedy .
45
Uwaga
W języku tym nie ma zmiennych, a jedynie stałe oraz symbole operacji.
Wyrażeniami poprawnymi (termami języka LS) są zatem dowolne stałe i deskryptory
połączone symbolami operacji, tzn.:
1. stałe 0 , 1 są termami
2. deskryptory systemu S, tj. pary stałych (a,v), a"A, v"Va są termami
3. jeżeli t , t są termami, to również termami są
~t , t t , t + t , t t , t * t
Przykład
(NAZWISKO, Kowalski) inne oznaczenie (NAZWISKO = Kowalski)
(PA
EĆ=mężczyzna) * (WIEK=17)
Uwaga
Termy interpretowane są jako pytania. Zgodnie z wcześniej przyjętą intencją,
znaczeniem termu winien być pewien podzbiór zbioru obiektów, który stanowi
odpowiedz
na pytanie reprezentowane przez term.
Znaczenie termów w systemie jest więc określone przez funkcję �S, której
argumentami są termy języka LS, wartościami zaś podzbiory obiektów systemu S.
Funkcja ta nazywana jest semantyką języka LS.
Gdy system S jest ustalony, zamiast �S stosowana będzie notacja �.
Przykład
�S(0) = " , �S(1) = X
�S(a,v) = {x "X | �X(A) = v}
�S(~t) = X - �S(a,v)
�S(t+t ) = �S(t) *" �S(t ) , �S(t*t ) = �S(t) )" �S(t )
�S(t t ) = ~�S(t) *" �S(t )
�S(t t ) = �S(t t ) )" �S(t t )
46
Np. 0 - Odpowiedzią na pytanie reprezentowane przez stałą 0 jest zbiór
pusty.
1 - . . .
(OCZY=zielone) - zbiór wszystkich osób mających oczy zielone
~( OCZY=zielone) - zbiór osób posiadających oczy o kolorze różnym
od zielonego
(OCZY=zielone)+(WZROST=170)
(OCZY=zielone)*(WZROST=170)
(STANOWISKO=mistrz) (WYNAGRODZENIE=5000zł)
Przykład
(OCZY=niebieskie) (WA
OSY=blond)
jeżeli odpowiedzią jest zbiór wszystkich obiektów systemu, tzn.
�S[(OCZY=niebieskie) (WA
OSY=blond)] = X
to zbiory osób mających niebieskie oczy oraz blond włosy są
identyczne tzn.
(OCZY=niebieskie) = (WA
OSY=blond)
Przykład
Niech S będzie systemem informacyjnym
X a b c
x1 v1 w1 u2
x2 v2 w1 u3
x3 v1 w2 u1
x4 v1 w2 u1
x5 v2 w2 u3
x6 v1 w1 u3
Alfabet języka tworzą
" Stałe 0 , 1
" Symbole operacji ~, * , + , ,
" Atrybuty a , b , c
" Wartości v1 , v2 , w1 , w2 , w3 ,u1 , u2 , u3.
47
Rozważmy termy:
(a,v1) + (b,w2) * (c,u2)
~[(a,v2) * (a,v1)] + (c,u3)
(b,w1) + (c,u1)
(b,w1) (c,u3)
(b,v2) (c,w2)
Znaczeniem tych termów są w systemie S następujące zbiory:
�S((a,v1) + (b,w2) * (c,u2)) = {x1,x3,x4,x6} *" ({x3,x4,x5} )" {x1}) =
= {x1 , x3 , x4 , x6}
�S(~[(a,v2) * (a,v1)] + (c,u3)) = ~(") *" {x2, x5 , x6 } = X
�S((b,w1) + (c,u1)) = {x1 , x2 , x6} *" {x3,x4} = {x1, x2 , x3 ,x4 , x5}
�S((b,w1) (c,u3))= (X - {x1 , x2 , x6}) *" {x2,x5,x6} = {x2, x3 , x4 , x5 , x6}
�S((a,v1) (b,w3))= {x1 , x3 , x4 , x6} )" {x1, x2, x6} = {x1, x6}
Term t języka LS jest prosty, gdy t jest postaci:
(a1,v1) * (a2,v2) * & * (an,vn)
gdzie
a1,a2,..,an  wszystkie atrybuty ze zbioru A
v1 , v2, .. , vn - są pewnymi wartościami odpowiednio ze zbiorów
Va1 , Va2 , & ,Van.
48
11 J
ZYKI SYSTEMÓW INFORMACYJNYCH.
- Postać normalna termów.
- Dokładność i efektywność języka.
- Termy proste maja następującą własność:
Własność
Jeżeli t jest termem prostym w języku LS , to �S(t) jest zbiorem
elementarnym w systemie S lub zbiorem pustym.
Przykład
(PA
EĆ=mężczyzna) * (WYNAGRODZENIE=duże) * (WIEK=młody)
Uwaga
Termy proste stanowią opisy klas równoważności relacji ~S (zbiorów
elementarnych).
Przykład
Dla systemu S określonego tabelką:
X a b
x1 v1 u2
x2 v2 u3
x3 v1 u2
x4 v2 u1
Termami prostymi w języku LS są
(a,v1) * (b,u1)
(a,v1) * (b,u2)
(a,v1) * (b,u3)
(a,v2) * (b,u1)
(a,v2) * (b,u2)
(a,v2) * (b,u3)
Wartości tych termów są następujące:
�S((a,v1) * (b,u1)) = "
�S((a,v1) * (b,u2)) = {x1,x3}
�S((a,v1) * (b,u3)) = "
49
�S((a,v2) * (b,u1)) = {x4}
�S((a,v1) * (b,u2)) = "
�S((a,v1) * (b,u3)) = {x2}
Zbiorami elementarnymi w systemie są:
{x1,x3} , {x2} , {x4}
Reguły przekształcania termów
(t + p) + s = t + (p +s) (t * p) * s = t * (p * s)
t + p = p + t t * p = p * t
t * (p +s) = t * p + t * s . . .
~(t + p) = ~r * ~p
t + t = t
t + (t * s) = t
. . .
t p = ~t + p
t p = t * p + ~t * ~p
t p = ~t ~p
(a,v) * (a,u) = 0 , u,v " Va , u `" v dla każdego a " A,
Każdy obiekt ma dokładnie jedną wartość każdego atrybutu ((jeżeli coś
ma kolor czerwony to nie ma innego)
Ł (a,v) = 1 dla każdego a"A
v"Va
Każdy obiekt przyjmuje jedną z wartości każdego atrybutu. Jeśli
atrybutem jest KOLOR to każdy obiekt musi mieć jakiś kolor, który jest
wartością tego atrybutu.
~(a,v) = Ł (a , u) , u`" v , dla każdego a"A,
u"Va
Zamiast mówić, że obiekt nie ma jakiejś własności, można powiedzieć,
że ma on jedną z pozostałych własności
50
tS = 1 , tS  term charakterystyczny systemu S.
Z systemu wykluczone są elementy, których opisy nie występują jako
składniki termu charakterystycznego (termu będącego sumą niepustych
termów prostych).
POSTAĆ NORMALNA TERMÓW
Każdy term można przekształcić w term mu równoważny,
posiadający specjalną postać, zwaną postacią normalną 
pozwalającą każde pytanie przedstawić w jednolitej postaci,
umożliwiającej wygodny sposób znalezienia odpowiedzi.
Przykład
W systemie informacyjnym
X a b c
x1 v1 u1 w2
x2 v2 u1 w1
x3 v1 u1 w2
x4 v1 u2 w2
x5 v2 u1 w1
x6 v2 u1 w1
Istnieją trzy zbiory elementarne {x1,x3} , {x2, x5 , x6} , {x4}
(a,v1) * (b,u1) * (c,w2)
(a,v2) * (b,u1) * (c,w1)
(a,v1) * (b,u2) * (c,w2)
Term t jest w postaci normalnej wtedy i tylko wtedy, kiedy t = 0 , t = 1 lub
t = t1 + t2 + & tk , gdzie ti są termami prostymi.
Własność
Dla każdego termu t istnieje term t w postaci normalnej równoważny
t.
Przykład
Sprowadz
do postaci normalnej term (przyjmując, że system
informacyjny ma atrybuty a, b , c a zbiory ich wartości są
następujące):
51
Va ={v1,v2} , Vb ={u1,u2} , Vc ={w1,w2}
t1 = ~[(a,v1) * (b,u2)] + (b,u1)
Na podstawie reguły: ~(t * p) = ~t + ~p
Term t1 można przedstawić w postaci:
t2 = ~(a,v1) + ~(b,u2) + (b,u1)
Na podstawie reguły:
~(a,v) = Ł (a , u) , u`" v , dla każdego a"A,
u"Va
otrzymujemy:
t3 = (a,v2) + (b,u1) + (b, u1)
Stosując do termu t3 regułę: t + t = t
Otrzymamy:
t4 = (a,v2) + (b,u1)
Z kolei zgodnie z regułą :
Ł (a,v) = 1 dla każdego a"A
v"Va
Można zapisać:
(a,v1) + (a,v2) = 1
(b,u1) + (b,u2) = 1
(c,w1) + (c,w2) = 1
Na podstawie reguły: t * 1 = t
Term t4 można przedstawić w postaci:
t5 = [(a,v2) + (b,u1)] * [(a,v1) + (a,v2)] * [(b,u1) + (b,u2)] *
* [(c,w1) + (c,w2)]
Zgodnie z kolei z regułami:
t * (p +s) = t * p + t * s ; t + (p *s) = (t + p) + (t + s)
t * t = t oraz (a,v) * (a,u) = 0 , u,v "Va , u `"v dla każdego
a "A,
Otrzymuje się term:
52
t6 = (a,v1) * (b,u1) + (c,w1) +
+ (a,v1) * (b,u1) + (c,w2) +
+ (a,v1) * (b,u2) + (c,w1) +
+ (a,v1) * (b,u2) + (c,w2) +
+ (a,v2) * (b,u1) + (c,w1) +
+ (a,v2) * (b,u1) + (c,w2) +
+ (a,v2) * (b,u2) + (c,w1) +
+ (a,v2) * (b,u2) + (c,w2)
Przykład
W systemie informacyjnym
X a b c
x1 v1 u1 w2
x2 v2 u1 w1
x3 v1 u1 w2
x4 v1 u2 w2
x5 v2 u1 w1
x6 v2 u1 w1
Istnieją trzy zbiory elementarne {x1,x3} , {x2, x5 , x6} , {x4}
(a,v1) * (b,u1) * (c,w2)
(a,v2) * (b,u1) * (c,w1)
(a,v1) * (b,u2) * (c,w2)
którym odpowiadają termy proste
�S[(a,v1) * (b,u1) * (c,w2)] = {x1,x3}
�S[(a,v2) * (b,u1) * (c,w1)] = {x2,x5,x6}
�S[(a,v1) * (b,u2) * (c,w2)] = {x4}
natomiast wszystkie pozostałe termy proste są puste, tzn. odpowiadają im zbiory
puste.
A zatem
�S(t1) = {x1,x3,x3,x4,x5,x6} , tzn. t1 = 1.
Minimalna postać normalna termu t ze względu ma system S  postać , w której nie
występują termy puste.
53
Uwaga
" Postać normalna mówi, że odpowiedz
na dowolne pytanie jest zawsze sumą
teoriomnogościową pewnych zbiorów elementarnych.
" Wprowadzając pytanie w postaci normalnej, można łatwo znalez
ć
odpowiadające każdemu termowi prostemu zbiory elementarne i w ten
sposób otrzymać odpowiedz
na zadane pytanie.
DOKA
ADNOŚĆ I EFEKTYWNOŚĆ J
ZYKA
Intuicyjnie  język dokładniejszy pozwala otrzymać więcej odpowiedzi niż jezyk mniej
dokładny.
Im więcej w systemie jest zbiorów elementarnych, tym więcej dostępnych jest
zbiorów opisywanych w tym systemie. W konsekwencji, w systemie dokładniejszym
istnieje więcej odpowiedzi niż w systemie mniej dokładnym.
Dokładność języka (języka zapytań) odnosi się do związanego z nim systemu
informacyjnego.
Dokładność systemu informacyjnego:
2k
S = = 2k  card(X)
2 card(X)
gdzie:
k  liczba bloków elementarnych w systemie
X  zbiór wszystkich obiektów w systemie informacyjnym S.
Oznacza stosunek liczby wszystkich podzbiorów opisywanych w systemie do liczby
wszystkich możliwych podzbiorów zbioru obiektów w systemie S.
Przykład
W systemie informacyjnym
X a b c
x1 v1 u1 w2
x2 v2 u1 w1
x3 v1 u1 w2
x4 v1 u2 w2
x5 v2 u1 w1
x6 v2 u1 w1
Istnieją trzy zbiory elementarne {x1,x3} , {x2, x5 , x6} , {x4}
Można więc skonstruować 23 = 8 zbiorów opisywanych, tzn. możliwych jest w
systemie tylko 8 różnych odpowiedzi:
54
"
{x4}
{x1,x3}
{x2, x5 , x6}
{x1,x3}*" {x4}
{x2, x5 , x6}*" {x4}
{x1,x3} *" {x2, x5 , x6}
{x1,x3} *" {x2, x5 , x6} *" {x4}
Natomiast wszystkich podzbiorów zbioru obiektów systemu jest 26 = 64
Tak więc dokładność systemu wynosi:
23
S = = 2 3
2 6
Uwaga
Najdokładniejszy jest system selektywny jego dokładność wynosi S = 1.
Efektywność języka charakteryzuje stopień jego wykorzystania do zadawania
pytań. Wynika to z faktu, że wiele termów prostych języka w danym systemie
jest pustych.
Efektywność języka w systemie S
k
�S =
"card(Va)
a"A
gdzie:
k  liczba zbiorów elementarnych systemie S
oznacza stosunek liczby wszystkich termów prostych systemie S, do liczby termów
prostych niepustych.
0 < �S d" 1
Efektywność języka systemu zupełnego wynosi 1.
Uwaga
Każdy selektywny język ma największą dokładność, dokładność każdy system
zupełny  największą efektywności.
55
12. AUTOMATY.
" Układy sekwencyjne i kombinacyjne.
" Automaty
" Automaty Meale go i Moore a.
" Język wyrażeń regularnych.
Automat  urządzenie, którego istotna cecha jest samoczynne wykonywanie
czynności zgodnie z jakimś z góry zadanym algorytmem działania.
x1 y1
x2 A y2
. .
. .
. .
xk yn
y1 = f(x1,x2,...,xk)
y2 = f(x1,x2,...,xk)
. . . .
yk = f(x1,x2,...,xk)
Y(t) = F(X(t))
Funkcja przełączająca  funkcja która jest określona na argumentach
przyjmujących wartości ze zbioru {0,1} i która sama
również przyjmuje tylko wartości z tego zbioru.
y = f(x1,x2,...,xn)
Uwaga
Liczba k możliwych wartości funkcji f dla n zmiennych k =2n
Liczba funkcji F określona na k ciągach wynosi 2k
Wyrażenia strukturalne  wyrażenia opisujące funkcje przełączające.
56
Rozkład wyrażeń strukturalnych
Rozkład jedności
x (" Źx �!1
x1 (" Źx1 �!1 ; x2 (" Źx2 �!1
1 �!1 '" 1
1 �! (x1 (" Źx1) '" (x2 (" Źx2)
1 �! x2 '" x1 (" x2 '" Źx1 (" Źx2 '" x1(" Źx2 '" Źx1
Uwaga
Jedność można przedstawić jako sumę składników, z których każdy jest
jedną ze wszystkich możliwych kombinacji wszystkich zmiennych lub
ich negacji. (suma elementarnych iloczynów zupełnych).
Rozkład zera
x '" Źx �!0
x1 '" Źx1 �! 0 ; x2 '" Źx2 �! 0
0 �!0 (" 0
0 �! (x1 '" Źx1) (" (x2 '" Źx2)
0 �! (Źx2 (" Źx1) '" (Źx2 (" x1 ) '" (x2 (" Źx1) '" (x2 (" x1)
Uwaga
Zero można przedstawić jako iloczyn czynników, z których każdy jest
jedną ze wszystkich możliwych kombinacji wszystkich zmiennych lub
ich negacji (iloczyn elementarnych sum zupełnych).
ROZKA
AD FUNKCJI WZGL
DEM SKA
ADNIKÓW JEDNOŚCI
Każda funkcja przełączająca może być przedstawiona w postaci sumy
wybranych iloczynów elementarnych zupełnych, przy czym postać taka dla
danej funkcji jest tylko jedna i nosi nazwę postaci normalnej zupełnej sumy.
57
Postać rozkładu dowolnej funkcji przełączającej
f(xn,xn-1,...,x2,x1) = f(1,1,...,1,1) xn'"xn-1'",...,'"x2'"x1 ("
("f(1,1,...,1,0) xn'"xn-1'",...,'"x2, '"Źx1 ("
(" f(1,1,...,0,1) xn'"xn-1'",..., '"Źx2'"x1 (" ...
...
...(" f(0,0,...,0,1) Źxn'" Źxn-1'",..., '"Źx2'"x1 ("
(" f(0,0,...,0,1) Źxn'"Źxn-1'",..., '"Źx2'" Źx1
Przykład
Dana jest funkcja trzech zmiennych
y = f(x3,x2,x1) = x3 '" (Źx2 (" Źx1) (" Źx3 '" x1
należy podać postać normalną zupełną sumy tej funkcji.
Dla x3 = 0 , x2 = 0 , x1 = 0
y = x3(Źx2 (" Źx1) (" Źx3 '" x1 = 0 '" (1 (" 1) (" 1 '" 0 = 0
zatem
y = x3 '" (Źx2 (" Źx1) (" Źx3 '" x1 = 0 '"Źx3 '"Źx2 '"Źx1 ("
(" 1 '"Źx3 '"Źx2 '"x1 (" 0 '"Źx3 '"x2 '"Źx1 (" 1 '"Źx3 '"x2 '"x1 ("
(" 1 '"x3 '"Źx2 '"Źx1 (" 1 '"x3 '"Źx2 '"x1 (" 1 '"x3 '"x2 '"Źx1 ("
(" 0 '"x3 '"x2 '"x1 =
= Źx3 '"Źx2 '"x1 (" Źx3 '"x2 '"x1 (" x3 '"Źx2 '"Źx1 (" x3 '"Źx2 '"x1
(" x3 '"x2 '"Źx1
58
Schematy logiczne funkcji dla postaci uproszczonej a) i postaci normalnej zupełnej
sumy b)
a)
Źx3
'"
x1
y
ŹX2
(" ("
Źx1
'"
x3
b)
X3
'"
x2
ŹX2
x3
'"
ŹX2
x1
y
("
X3
Źx2 '"
ŹX2
Źx3
'"
X2
x1
ŹX3
'"
Źx2
x1
59
ROZKA
AD FUNKCJI WZGL
DEM CZYNNIKÓW ZERA
Każda funkcja przełączająca może być przedstawiona w postaci iloczynu
wybranych sum elementarnych zupełnych, przy czym postać taka dla danej
funkcji jest tylko jedna i nosi nazwę postaci normalnej zupełnej iloczynu.
Postać rozkładu dowolnej funkcji przełączającej
f(xn,xn-1,...,x2,x1) = [f(0,0,...,0,0) ("( xn("xn-1(",...,("x2("x1)] '"
'" [f(0,0,...,0,1) (" (xn("xn-1(",...,("x2, ("Źx1 )] '"
'"...
...
... '" [f(1,1,...,1,1) (" (Źxn(" Źxn-1(",..., ("Źx2("Źx1 )] '"
'" f(0,0,...,0,1) Źxn'"Źxn-1'",..., '"Źx2'" Źx1
Przykład
y = x3 '" (Źx2 (" Źx1) (" Źx3 '" x1 = (0 ("x3 ("x2 ("x1) '"
'" (1 ("x3 ("x2 ("Źx1) '" ( 0 ("x3 ("Źx2 ("x1) '" (1 ("x3 ("Źx2 ("Źx1 ) '"
'" (1 ("Źx3 ("x2 ("x1 ) '" (1("x3 ("x2 ("Źx1) '" (1 ("Źx3 ("'"Źx2 ("x1 ) '"
'" (0 ("Źx3 ("Źx2 ("Źx1) =
= (x3 ("x2 ("x1) '" (x3 ("Źx2 ("x1) '" (x3 ("Źx2 ("Źx1 ) '" (Źx3 ("Źx2 ("Źx1)
Uwaga
Czy obie postacie sa sobie równoważne?
Źx3 '"Źx2 '"x1 (" Źx3 '"x2 '"x1 (" x3 '"Źx2 '"Źx1 (" x3 '"Źx2 '"x1 ("
(" x3 '"x2 '"Źx1 = (x3 ("x2 ("x1) '" (x3 ("Źx2 ("x1) '" (x3 ("Źx2 ("Źx1 ) '"
'" (Źx3 ("Źx2 ("Źx1)
Wniosek
Każda funkcję przełączająca można przedstawić za pomocą dwóch
postaci:
60
" Postaci normalnej zupełnej sumy, której elementami są elementarne
iloczyny zupełne. (sumę składników jedności) (iloczyn czynników
zera)
" Postaci normalnej zupełnej iloczynu, której czynnikami są
elementarne sumy zupełnej. (suma składników jedności)
Automaty bez pamięci  nie zachodzi potrzeba zapamiętywania informacji
wprowadzonej lub przekształconej.
Układy kombinacyjne  działanie których zależy od wzajemnej kombinacji wartości
zmiennych tworzących informacje.
Przykład
Dane są trzy zbiorniki wyposażone w trzy sygnalizatory dwupołożeniowe
podające informacje o poziomach cieczy.
Należy zasygnalizować dwa przypadki:
" Gdy wszystkie zbiorniki osiągną określony poziom
" Gdy co najmniej dwa zbiorniki osiągną ten poziom
Notując odpowiednie informacje przez a, b, c warunki te można zapisać:
" a'"b'"c
" a'"b ; a'"c ; b'"c
Odpowiednia funkcja przełączająca ma postać:
y = a'"b'"c (" a'"b (" a'"c (" b'"c
Rozszerzając to wyrażenie do postaci elementarnych iloczynów zupełnych
y = a'"b'"c (" a'"b'"1 (" a'"1'"c (" 1'"b'"c =
= a'"b'"c (" a'"b'"(c("Źc) (" a'"(b("Źb) '"c (" (a("Źa) '"b'"c =
= a'"b'"c (" a'"b'"Źc (" a'"Źb '"c (" Źa '"b'"c
i przeprowadzając jej minimalizacje
y = a'"b (" a'"c (" b '"c = c'"(a (" b) (" a'"b
Otrzymujemy schemat logiczny układu
61
("
y
'"
c
("
b
a
'"
Przykład
Dane są informacje z trzech punktów: a, b c. Sygnalizowane maja być
sytuacje gdy na wejściach a lub c lub na dwóch dowolnych pojawi się 1.
a b c y
o o o o
o o 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0
Zestawiając funkcję dla warunków działania otrzymujemy
y0 = = Źa'"Źb'"c (" a'"Źb'"Źc (" Źa'"b '"c (" a '"Źb'"c (" a '"b '"Źc
Przeprowadzając minimalizację otrzymujemy:
y0 = Źb'"c'"(a("Źa) (" a'"Źb'"(c("Źc) (" a'"Ź c'"(b("Źb) (" Źa'"c'"(b("Źb) =
= Źb'"c(" a'"Źb(" a'"Ź c(" Źa'"c
co odpowiada zestawieniu funkcji dla warunków niedziałania
y1 = (a("b("c) '" (a("Źb("c) '" (Źa("b("c) =
= Źb'"c(" a'"Źb(" a'"Ź c(" Źa'"c = y1
Co po doprowadzeniu do odpowiedniej postaci nawiasowej
62
y = y1 = y0 = a'"(Źb ("Źc) (" c'"(Źa ("Źb)
prowadzi do schematu strukturalnego układu
Ź
("
Ź '"
y
c
("
b
("
a
Ź '"
Automat z pamięcią
Automat skończony
A = (X,Y,S,.s0, ą(X,S),(X,S))
Gdzie
X  zbiór słów wejściowych
Y zbiór słów wyjściowych
S zbiór stanów
s0  stan początkowy
ą(X,S)  funkcja przejść określająca zmiany stanów automatu
(X,S)  funkcja przejść określająca zmiany słów wyjściowych
Uwaga
Zarówno funkcja wyjść jak i funkcja przejść są funkcjami rekurencyjnymi
dla zmiennych dyskretnych
63
Układ kombinacyjny
Y
X
. . . Automat bez pamięci
. . .
Pa
Zamykanie
Opuszczanie
Zamykanie ukończone
Otwieranie Zamykanie Otwarte
Zamknięte
Otwieranie Podnosze Otwieranie ukończone
nie
64
Przykład
b
b
a
0 1
a a
2 a 3
b b
Stan bieżący Symbol bieżący Stan kolejny Pozostałe symbole
0 a 1 baa
1 b 1 aa
1 a 3 a
3 a 2
2
Język wyrażeń regularnych
Przykład
a b
0 1 0
1 3 2
2 1 3
3 3 3
S0 = 0 , Sk = {2}
b a
1
0
a
b
a
3
2
b b
65
Automat Meale a
S(t+1) = ą(X(t),S(t))
Y(t) = (X(t),S(t))
Automat Moore a
S(t+1) = ą(X(t),S(t))
Y(t+1) = (X(t+1))
13. AUTOMATY.
" Realizacje automatów.
" Synteza abstrakcyjna z wykorzystaniem charakterystyki wejście-
wyjście.
14. SIECI PETRIEGO.
" Definicja i klasyfikacje sieci Petriego.
" Reprezentacje teoriomnogościowa, graficzna i macierzowa.
" Modelowanie - przykłady zastosowań.
15. SIECI PETRIEGO
" Analiza właściwości  żywotność strukturalna i funkcjonalna.
" Zjawiska blokady i konfuzji.
" Niezmienniki.
" Rozszerzenia sieci  czasowe, kolorowane, stochastyczne
66