PROBLEMY NIEROZSTRZYGALNE Zestaw 1: T Przykład - problem domina T Czy podanym zestawem kafelków można pokryć dowolny płaski obszar zachowując odpowiedniość kolorów na styku kafelków? (dysponujemy nieograniczoną liczbą kafelków w każdym z rodzajów, ale ich zestaw jest Zestaw 2: zadany) T Dla zestawu 1. - TAK ! T Dla zestawu 2. - NIE M.Rawski Wstęp do Informatyki 1 PROBLEMY NIEROZSTRZYGALNE cd T Twierdzenie T Dla każdego algorytmu (zapisanego w dającym się efektywnie wykonać języku programowania), który byłby przeznaczony do rozstrzygania problemu domina, istnieje nieskończenie wiele dopuszczalnych zestawów danych wejściowych, dla których algorytm ten będzie działał w nieskończoność lub poda błędną odpowiedz. T Wniosek T Problem domina jest problemem nierozstrzygalnym M.Rawski Wstęp do Informatyki 2 PROBLEMY NIEROZSTRZYGALNE cd W ogóle nie istnieją algorytmy PROBLEMY NIEROZSTRZYGALNE (LUB NIEOBLICZALNE) Nie istnieją PROBLEMY TRUDNO wielomianowe ROZWIZYWALNE algorytmy PROBLEMY AATWO Istnieją rozsądne ROZWIZYWALNE (wielomianowe) algorytmy " nieograniczoność liczby przypadków do sprawdzenia nie jest dostatecznym warunkiem nierozstrzygalności problemu! " jeśli nierozstrzygalność się pojawia, to wynika z natury problemu i jest często sprzeczna z intuicją M.Rawski Wstęp do Informatyki 3 Problem węża domino T Czy dysponując skończonym zbiorem typów kafelków można połączyć dwa dane punkty nieskończonej siatki całkowitoliczbowej wężem domino ? T Jeżeli postawimy problem węża domino na pewnym obszarze R, to: " dla R ograniczonego problem jest oczywiście rozstrzygalny " dla R będącego całą płaszczyzną problem Y jest rozstrzygalny X " dla R będącego półpłaszczyzną problem jest nierozstrzygalny M.Rawski Wstęp do Informatyki 4 Problem stopu w algorytmie Mając jako dane wejściowe tekst poprawnego programu zapisanego w pewnym języku, sprawdzić(tzn. zbudować algorytm, który by sprawdzał), czy program zatrzyma się dla pewnych dopuszczalnych dla niego danych. T X " N T X " N T Algorytm 1 T Algorytm 2 T 1.dopóki X `" 1 wykonuj X ! X - 2 T 1. dopóki X `" 1 wykonuj: T 1.1.dla X parzystego X ! X / 2 T 2. zatrzymaj obliczenia T 1.2. dla X nieparzystego X ! 3* X + 1 T 2. zatrzymaj obliczenia " dla wszystkich sprawdzanych liczb " algorytm zatrzymuje się dla X algorytm zatrzymywał się nieparzystych " nie udowodniono, że zatrzymuje się dla " nie zatrzymuje się dla X parzystych dowolnej liczby naturalnej M.Rawski Wstęp do Informatyki 5 Problem stopu w algorytmie cd T np. dla X = 7 generuje ciąg wartości: 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 program lub dopuszczalne T algorytm dane R X czy program R czy istnieje zatrzymuje się dla taki danych X ? program? TAK NIE T Problem stopu jest nierozstrzygalny. M.Rawski Wstęp do Informatyki 6 Odmiany problemu domina Odmiany problemu domina Odmiany problemu domina Odmiany problemu domina Czy podanym zestawem kafelków można pokryć obszar T zachowując odpowiedniość kolorów na styku kafelków? " T = prostokąt C x N (tzw. problem ograniczony ze stałą szerokością) " T = kwadrat N x N (tzw. problem ograniczony) " T jest nieskończony (tzw. problem nieograniczony) " T jest nieskończony i wskazany kafelek ma się powtórzyć nieskończenie wiele razy (tzw. problem okresowy) T Rodzaj problemu domina Status algorytmiczny ograniczony ze stałą szerokościąłatwo rozwiązywalny ograniczony trudno rozwiązywalny nieograniczony nierozstrzygalny okresowy wysoce nierozstrzygalny M.Rawski Wstęp do Informatyki 7 Klasy problemów Klasy problemów Klasy problemów Klasy problemów algorytmicznych algorytmicznych algorytmicznych algorytmicznych Klasy problemów algorytmicznych WYSOCE NIEROZSTRZYGALNE NIEROZSTRZYGALNE TRUDNO ROZWIZYWALNE AATWO ROZWIZYWALNE Nie można Teoria Praktyka PROBLEMY sprowadzić do tych, WYSOCE dla których nie NIEROZSTRZYGALNE istnieją algorytmy W ogóle nie istnieją PROBLEMY algorytmy NIEROZSTRZYGALNE Nie istnieją rozsądne PROBLEMY TRUDNO algorytmy ROZWIZYWALNE PROBLEMY AATWO Istnieją rozsądne ROZWIZYWALNE (wielomianowe) algorytmy M.Rawski Wstęp do Informatyki 8 KOMPUTER PROSTY I UNIWERSALNY T Jak dalece można uprościć struktury danych? T Przykład tablicy dwuwymiarowej 7 45 -3 91 0 12 -15 11 17 7 * 45 * -3 * * 91 * 0 * 12 * * -15 * 11 * 17 I T Przykład drzewa N F O R M A T Y K A I * * N * F * O * * R * M * A * T * * Y * K * A M.Rawski Wstęp do Informatyki 9 Linearyzacja struktur danych T Każdą strukturę danych da się zlinearyzować tzn. zapisać na jednowymiarowej taśmie # # # # T T Przyjmujemy najprostszy model pamięci: " nieskończona jednowymiarowa taśma " dopuszczalny zestaw symboli (alfabet), które mogą być zapisywane w komórkach taśmy " pusta komórka oznaczana symbolem # M.Rawski Wstęp do Informatyki 10 KOMPUTER PROSTY I UNIWERSALNY T Jak dalece można uprościć struktury sterujące? symbole alfabetu T znajdowanie się procesora w stan a aktualny możliwe określonym miejscu programu b stany nazywamy jego stanem następne c T przejście do innego miejsca (stanu) zależy od stanu aktualnego i od wartości pewnych jednostek danych M.Rawski Wstęp do Informatyki 11 Maszyna Turinga STEROWANIE (diagram przejść pomiędzy stanami) pojedynczy głowica symbol odczytująco alfabetu -zapisująca # ## # nieskończona taśma Części składowe: " skończony alfabet symboli (do zapisywania danych) " skończony zbiór stanów, w których może znajdować się maszyna " nieskończona taśma podzielona na komórki przechowujące pojedyncze symbole alfabetu " krokowo poruszająca się głowica odcztująco-zapisująca " diagram przejść miedzy stanami, który steruje głowicą tak, że zmiany następują po każdym jej zatrzymaniu " stan początkowy i stany końcowe (elementy uzupełniające w diagramie przejść) M.Rawski Wstęp do Informatyki 12 Diagram przejść - graf skierowany T Podstawowe elementy diagramu przejść: etykieta akcja stan (wierzchołek grafu) przejście a / b L nazwa stanu kierunek przesunięcia symbol alfabetu - głowicy (L lub P) wyzwalacz przejścia symbol alfabetu zapisywany w komórce T maszyna jest deterministyczna tzn. z żadnego stanu nie wychodzi więcej niż jedno przejście z tym samym wyzwalaczem T jeden ze stanów jest wyróżniony jako stan początkowy nazwa stanu T stany, z których nie wychodzą żadne przejścia, nazywane są stanami końcowymi T w stanie początkowym głowica jest ustawiona na pierwszej od lewej niepustej komórce taśmy nazwa stanu T M.Rawski Wstęp do Informatyki 13 Wykrywanie polindromów T Przykład diagramu przejść dla maszyny Turinga # / # L ruch dla a test dla a a / # L b / b L b / b P a / # P a / a L a / a P b / b L # / # L # / # L zaznacz TAK NIE powrót # / # L a / a L b / b P b / # P a / a P b / # L # / # L ruch dla b test dla b # / # P M.Rawski Wstęp do Informatyki 14 Wykrywanie polindromów T Przykład działania maszyny Turinga 1 2 3 4 # # a b b a # # # # # b b a # # # # # b b a # # # # # b b a # # M.Rawski Wstęp do Informatyki 15 TEZA CHURCHA-TURINGA T Maszyna Turinga: " ma skończenie wiele stanów " zapisuje po jednym symbolu na liniowej taśmie Co można zrobić za pomocą maszyny Turinga? Wszystko! Maszyna Turinga potrafi rozwiązać każdy efektywnie rozwiązywalny problem algorytmiczny! Teza CT M.Rawski Wstęp do Informatyki 16 Modele komputera uniwersalnego T Różne inne modele komputera uniwersalnego: " rachunek lambda (Church) " system produkcji dla symboli (Post) " klasa funkcji rekurencyjnych (Kleen) " ... i wiele innych Wszystkie modele są równoważne w sensie klasy problemów algorytmicznych, które rozwiązują! M.Rawski Wstęp do Informatyki 17 Algorytm uniwersalny algorytm A program P realizujący program P dane X T Konsekwencją tezy CT jest algorytm A napisany w uniwersalnym języku L2 istnienie algorytmów uniwersalny program U wykonaj program P napisany w języku L1 - uniwersalnych na danych X symuluje wynik programu w języku L2 na jego danych wyniki (jeśli są) " można zbudować uniwersalną maszynę Turinga, która może symulować działanie dowolnej maszyny Turinga na dowolnych danych (trzeba opisać na taśmie zlinearyzowany diagram przejść, reprezentując każde przejście jako parę stanów z podaną etykietą przejścia) M.Rawski Wstęp do Informatyki 18 Algorytm uniwersalny T Rozwijając tezę CT można dojść do wniosku, że: T jeśli jakiś (szybki) komputer rozwiązuje pewien problem w czasie O(f(N)), to istnieje równoważna mu maszyna Turinga, która potrzebuje na rozwiązanie tego problemu nie więcej niż O(p(f(N))) czasu, dla pewnej ustalonej funkcji wielomianowej p T Zatem: " klasa problemów obliczalnych (rozstrzygalnych) jest silna tj. niewrażliwa na zmianę modelu obliczeń lub języka zapisu algorytmu " klasa problemów łatwo rozwiązywalnych P jest także silna (tzw. teza obliczania sekwencyjnego, czyli wykonywanego krok po kroku) " klasa NP jest silna " klasa problemów o wykładniczej złożoności czasowej jest silna " klasa problemów o liniowej złożoności czasowej nie jest silna tzn. złożoność tych problemów może zależeć od przyjętego modelu obliczeń M.Rawski Wstęp do Informatyki 19 Klasy problemów P i NP - Klasy problemów P i NP - Klasy problemów P i NP - Klasy problemów P i NP - formalnie formalnie formalnie formalnie T Formalnie klasy problemów P i NP definiuje się w kategoriach obliczeń na maszynie Turinga: " problemy z klasy P są rozwiązywalne przez zwykłe maszyny Turinga w czasie wielomianowym " problemy z klasy NP są rozwiązywalne przez niedeterministyczne maszyny Turinga w czasie wielomianowym a / b P T Na mocy tezy CT wystarczyło by pokazać, że ? pewien problem NP-zupełny nie może być rozwiązany za pomocą maszyny Turinga w a / b L czasie krótszym niż wykładniczy, aby wykazać, że P `" NP . `" `" `" przejście niedeterministyczne M.Rawski Wstęp do Informatyki 20 Obliczenia współbieżne " rozwiązywanie problemu algorytmicznego za pomocą współpracujących ze sobą wielu procesorów " wykorzystanie komputerów równoległych, składających się z wielu rozłącznych elementów przetwarzających " modele obliczeń i przetwarzania informacji w środowiskach rozproszonych (sieci telekomunikacyjne, systemy rezerwacji biletów lotniczych, długoterminowe prognozy pogody wyznaczane równolegle w wielu centrach obliczeniowych) algorytm sekwencyjny algorytm równoległy X ! 3 X ! 3 Y ! 4 Y ! 4 2 kroki 1 krok X ! 3 X ! 3 Y ! X Y ! X M.Rawski Wstęp do Informatyki 21 Przykład sumowania zarobków w czasie logarytmicznym T Naturalny algorytm sekwencyjny o koszcie O(N): dodawanie N razy do sumy bieżącej T Algorytm równoległy o koszcie O(log N): krok 1 krok 2 krok log 2 N N/2 procesorów N/4 procesorów 1 procesor 11 000 Ł 35 300 24 300 Ł 63 300 17 100 Ł 28 000 10 900 Ł 547 200 Ł 75 800 15 500 Ł 31 900 16 400 M.Rawski Wstęp do Informatyki 22 Obliczenia współbieżne T O szybkości algorytmów równoległych, oczywiście poza liczbą dostępnych procesorów, decydują także struktury danych i metody komunikacji! T W algorytmie sumowania N liczb: " dla osiągnięcia redukcji z O(N) do O(log N) potrzebujemy N/2 procesorów " mając do dyspozycji ustaloną liczbę procesorów poprawimy przetwarzanie tylko o stałą (np. 100 razy szybciej), ale nie o rząd wielkości " uzyskanie poprawy rzędu wielkości wymaga rozszerzającej się równoległości tzn. liczba procesorów rośnie proporcjonalnie do N M.Rawski Wstęp do Informatyki 23 Sortowanie równoległe T Rozważmy sekwencyjny algorytm sortowania przez scalanie: T procedura sortuj-listę L; T jeśli L zawiera tylko jeden element, to jest posortowana; T w przeciwnym razie wykonaj co następuje: T podziel listę L na dwie połowy L1 i L2; T wywołaj sortuj-listę L1; T wywołaj sortuj-listę L2; T scal listy L1 i L2 w jedną posortowaną listę; T wróć do poziomu wywołania. T - złożoność czasowa O(N log N)
M.Rawski Wstęp do Informatyki 24 Sortowanie równoległe T Rozważmy sekwencyjny algorytm sortowania przez scalanie: T procedura sortuj-listę L; T jeśli L zawiera tylko jeden element, to jest posortowana; T w przeciwnym razie wykonaj co następuje: T podziel listę L na dwie połowy L1 i L2; T wywołaj równocześnie równolegle-sortuj-listę L1 i równolegle- sortuj-listę L2 ; T wróć do poziomu wywołania. M.Rawski Wstęp do Informatyki 25 Sortowanie równoległe -Analiza złożoności 15 7 45 8 12 11 4 34 N/2 par scalanie w czasie 1 porównania 7 15 8 45 11 12 4 34 N/4 par scalanie w czasie 3 porównań N/8 par 7 8 15 45 4 11 12 34 scalanie w czasie 7 porównań 1 para scalanie w czasie N - 1 porównań 4 7 8 11 12 15 34 45 T zatem całkowita liczba porównań wyniesie: T 1 + 3 + 7 + 15 + ... + ( N - 1 ) d" 2 N - liczba rzędu O(N) M.Rawski Wstęp do Informatyki 26 Złożoność iloczynowa T Złożoność iloczynowa: liczba procesorów czas
" złożoność rozmiaru algorytmu " najlepsza złożoność iloczynowa nie będzie lepsza niż dolne ograniczenie sekwencyjnej złożoności problemu Rodzaj Nazwa algorytmu Liczba procesorów Czas (najgorszy Iloczyn algorytmu (rozmiar) przypadek) (rozmiar czas)
równoległe sortowanie O(N) O(N) O(N 2) przez scalanie równoległy sieć sortująca parzysto- O((log N)2) O(N O(N (log N)4) (log N)2)
nieparzyście optymalna sieć sortująca O(N) O(log N) O(N log N)
M.Rawski Wstęp do Informatyki 27 Co można, a czego nie Co można, a czego nie Co można, a czego nie Co można, a czego nie T Co można, a czego nie można osiągnąć równoległością: T wiele problemów można rozwiązać szybciej niż sekwencyjnie T można niektóre problemy rozwiązywać szybciej nawet o rząd wielkości, jeśli da się zastosować rozszerzającą się równoległość T dla problemów nierozstrzygalnych nie da się skonstruować algorytmu równoległego - klasa problemów rozwiązywalnych jest niewrażliwa na dodanie równoległości T wszystkie problemy klasy NP mają rozwiązania równoległe znajdowane w czasie wielomianowym, ale T liczba procesorów potrzebnych do rozwiązania problemu NP-zupełnego w rozsądnym czasie rośnie wykładniczo T do końca nie wiadomo, czy problemy klasy NP są rzeczywiście trudno rozwiązywalne i trzeba szukać ratunku w równoległości T rzeczywiste komputery równoległe mają silne ograniczenia związane z przepustowością połączeń pomiędzy procesorami T nie wiadomo, czy można zastosować równoległość, nawet z niewielomianową liczbą procesorów, do rozwiązania w czasie wielomianowym problemu o udowodnionej sekwencyjnej złożoności wykładniczej M.Rawski Wstęp do Informatyki 28