1 Obliczalność czyli co da się policzyć i jak Model obliczeń sieci liczącedr Kamila Barylska
2 Wykład 1: Obliczalność. Maszyna licznikowa. Plan zajęć Wykład 1: Obliczalność. Maszyna licznikowa. Ćwiczenia 1: Programy na maszynę licznikową. Wykład 2: Maszyna Turinga. Problemy, których nie da się rozwiązać. Ćwiczenia 2: Programy na maszynę Turinga. Wykład 3: Liczące sieci Petriego. Ćwiczenia 3: Konstruowanie sieci liczących.
3 Sieci Petriego – formalna definicjaSieć Petriego (w skrócie p/t-sieć) to czwórka S=(P,T,F,M0), gdzie: P i T - skończone, niepuste i rozłączne zbiory P - zbiór miejsc T - zbiór akcji elementy zbioru PT - strzałki wejściowe elementy zbioru TP - strzałki wyjściowe funkcja wagowa F: (PT)(TP) N określa wagi strzałek obu typów M0 - wielozbiór nad P (czyli funkcją M0: P N), zwany markowaniem
4 Sieci Petriego – interpretacja graficznamiejsca - okręgi akcje - prostokąty strzałki jako strzałki pomijamy strzałki o wadze równej 0 przy strzałkach o wadze równej 1 nie piszemy liczby wagowej przy strzałkach o wadze większej niż 1 piszemy liczbę wagową markingi reprezentujemy przez wstawienie właściwej liczby żetonów (kropek) do odpowiednich miejsc a b 3 4 2
5 Sieci Petriego – działanieAkcja może się wykonać (czyli jest umożliwiona), jeśli w każdym jej miejscu wejściowym jest „wystarczająco dużo żetonów” (czyli przynajmniej tyle ile wynosi waga na strzałce z danego miejsca do tej akcji). Wykonanie akcji zmienia bieżący marking: żetony są zabierane z miejsc wejściowych i dodawane do miejsc wyjściowych (zgodnie z wagami na strzałkach). a b 3 4 2
6 Sieci Petriego – działanieAkcja może się wykonać (czyli jest umożliwiona), jeśli w każdym jej miejscu wejściowym jest „wystarczająco dużo żetonów” (czyli przynajmniej tyle ile wynosi waga na strzałce z danego miejsca do tej akcji). Wykonanie akcji zmienia bieżący marking: żetony są zabierane z miejsc wejściowych i dodawane do miejsc wyjściowych (zgodnie z wagami na strzałkach). a b 3 4 2
7 Sieci Petriego – działanieAkcja może się wykonać (czyli jest umożliwiona), jeśli w każdym jej miejscu wejściowym jest „wystarczająco dużo żetonów” (czyli przynajmniej tyle ile wynosi waga na strzałce z danego miejsca do tej akcji). Wykonanie akcji zmienia bieżący marking: żetony są zabierane z miejsc wejściowych i dodawane do miejsc wyjściowych (zgodnie z wagami na strzałkach). a b 3 4 2
8 Sieci Petriego – działanieAkcja może się wykonać (czyli jest umożliwiona), jeśli w każdym jej miejscu wejściowym jest „wystarczająco dużo żetonów” (czyli przynajmniej tyle ile wynosi waga na strzałce z danego miejsca do tej akcji). Wykonanie akcji zmienia bieżący marking: żetony są zabierane z miejsc wejściowych i dodawane do miejsc wyjściowych (zgodnie z wagami na strzałkach). a b 3 4 2
9 Sieci Petriego – działanieAkcja może się wykonać (czyli jest umożliwiona), jeśli w każdym jej miejscu wejściowym jest „wystarczająco dużo żetonów” (czyli przynajmniej tyle ile wynosi waga na strzałce z danego miejsca do tej akcji). Wykonanie akcji zmienia bieżący marking: żetony są zabierane z miejsc wejściowych i dodawane do miejsc wyjściowych (zgodnie z wagami na strzałkach). a b 3 4 2
10 Sieci liczące – formalna definicjaSieć licząca lub obliczająca - (krótko p/t-obliczak) - sieć z wyróżnionymi podzbiorami miejsc: argumentowych Ps = p1,…,pn roboczych Pr i wyróżnionym miejscem wynikowym pf oraz roboczym markowaniem początkowym Mr.
11 Sieci liczące – działanieJak działa sieć licząca n-argumentową funkcję f:Nn→N? wstawiamy kolejne argumenty do miejsc p1,…,pn „uruchamiamy sieć” jeśli uda nam się osiągnąć „pusty marking”, czyli taki, w którym wszystkie miejsca (poza miejscem wynikowym pf) są puste, to w miejscu wynikowym pf znajduje się liczba żetonów odpowiadająca wynikowi. Uwaga: Nie może dojść do sytuacji, że osiągamy „pusty marking”, zaś w miejscu wynikowym znajduje się niewłaściwa liczba żetonów.
12 Sieci liczące – przykład – f(x,y)=x+yy żetonów x żetonów a b pf
13 Sieci liczące – przykład – f(x,y)=x+yb p1 p2 pf
14 Sieci liczące – przykład – f(x,y)=x+yb pf
15 Sieci liczące – przykład – f(x,y)=x+yb Które akcje są umożliwione? pf
16 Sieci liczące – przykład – f(x,y)=x+yb Jeśli dwie akcje są umożliwione, wybieramy, którą chcemy wykonać! pf
17 Sieci liczące – przykład – f(x,y)=x+yb pf
18 Sieci liczące – przykład – f(x,y)=x+yb pf
19 Sieci liczące – przykład – f(x,y)=x+yb pf
20 Sieci liczące – przykład – f(x,y)=x+yb pf
21 Sieci liczące – przykład – f(x,y)=x+yb pf
22 Sieci liczące – przykład – f(x,y)=x+yb pf
23 Sieci liczące – przykład – f(x,y)=x+yb pf
24 Sieci liczące – przykład – f(x,y)=x+yb pf
25 Sieci liczące – przykład – f(x,y)=x+yb pf
26 Sieci liczące – przykład – f(x,y)=x+yb pf
27 Sieci liczące – przykład – f(x,y)=x+yb pf
28 Sieci liczące – przykład – f(x,y)=x+yb pf
29 Sieci liczące – przykład – f(x,y)=x+yb pf
30 Sieci liczące – przykład – f(x,y)=x+yb pf
31 Sieci liczące – przykład – f(x,y)=x+yb pf
32 Sieci liczące – przykład – f(x,y)=x+yb pf
33 Sieci liczące – przykład – f(x,y)=x+yb pusty marking pf
34 Sieci liczące – przykład – f(x,y)=x+yb pusty marking pf
35 Sieci liczące – przykład – f(x,y)=x+yb pusty marking WYNIK: f(2,3)=5 pf
36 Sieci liczące – ograniczeniaP/t sieci liczące mają ograniczoną moc obliczeniową! Nie jesteśmy w stanie stworzyć sieci liczącej, która prawidłowo oblicza mnożenie. f(x,y)=x y nie da się policzyć z pomocą p/t-sieci liczącej CO ZROBIĆ? musimy rozszerzyć nasze sieci o dodatkowe łuki
37 a b Sieci inhibitorowe Sieci inhibitorowe są rozszerzeniem p/t-sieci.Powstają przez dodanie krawędzi inhibitorowych prowadzących od miejsc do akcji oraz modyfikację reguł umożliwienia akcji. W sieci inhibitorowej akcja jest umożliwiona jeśli: każde miejsce wejściowe połączone z nią zwykłą krawędzią ma „wystarczającą” liczbę żetonów, każde miejsce wejściowe połączone z nią krawędzią inhibitorową jest puste. a b 3 2 4
38 a b Sieci inhibitorowe Sieci inhibitorowe są rozszerzeniem p/t-sieci.Powstają przez dodanie krawędzi inhibitorowych prowadzących od miejsc do akcji oraz modyfikację reguł umożliwienia akcji. W sieci inhibitorowej akcja jest umożliwiona jeśli: każde miejsce wejściowe połączone z nią zwykłą krawędzią ma „wystarczającą” liczbę żetonów, każde miejsce wejściowe połączone z nią krawędzią inhibitorową jest puste. 4 2 3 a b
39 a b Sieci inhibitorowe Sieci inhibitorowe są rozszerzeniem p/t-sieci.Powstają przez dodanie krawędzi inhibitorowych prowadzących od miejsc do akcji oraz modyfikację reguł umożliwienia akcji. W sieci inhibitorowej akcja jest umożliwiona jeśli: każde miejsce wejściowe połączone z nią zwykłą krawędzią ma „wystarczającą” liczbę żetonów, każde miejsce wejściowe połączone z nią krawędzią inhibitorową jest puste. 4 2 3 a b
40 a b Sieci inhibitorowe Sieci inhibitorowe są rozszerzeniem p/t-sieci.Powstają przez dodanie krawędzi inhibitorowych prowadzących od miejsc do akcji oraz modyfikację reguł umożliwienia akcji. W sieci inhibitorowej akcja jest umożliwiona jeśli: każde miejsce wejściowe połączone z nią zwykłą krawędzią ma „wystarczającą” liczbę żetonów, każde miejsce wejściowe połączone z nią krawędzią inhibitorową jest puste. 4 2 3 a b
41 a b Sieci inhibitorowe Sieci inhibitorowe są rozszerzeniem p/t-sieci.Powstają przez dodanie krawędzi inhibitorowych prowadzących od miejsc do akcji oraz modyfikację reguł umożliwienia akcji. W sieci inhibitorowej akcja jest umożliwiona jeśli: każde miejsce wejściowe połączone z nią zwykłą krawędzią ma „wystarczającą” liczbę żetonów, każde miejsce wejściowe połączone z nią krawędzią inhibitorową jest puste. 4 2 3 a b
42 Inhibitorowe sieci licząceInhibitorowe liczące mają moc obliczeniową równą mocy: maszyn licznikowych maszyn Turinga. f(x,y)=x y można policzyć z pomocą inhibitorowej sieci liczącej CO WIĘCEJ: WSZYSTKO CO DA SIĘ POLICZYĆ MOŻNA POLICZYĆ Z UŻYCIEM INHIBITOROWYCH SIECI LICZĄCYCH!!!
43 Zadanie 1 Skonstruować sieć Petriego obliczającą funkcje:Zadania Zadanie 1 Skonstruować sieć Petriego obliczającą funkcje: f(x,y,z) = x f(x) = x 3 f(x,y,z) = 0 f(x) = x 3 f(x,y,z) = x+z f(x,y,z) = 5x+4y+3 f(x) = x k f(x) = x 2 f(x) = x 2 f(x,y) = xy Zadanie dodatkowe Skonstruować sieć inhibitorową obliczającą funkcję f(x,y)=xy.