class: center, middle, inverse, title-slide .title[ # Optymalizacja dyskretna <br>(w tym algorytmy heurystyczne) ] .subtitle[ ## Złożoność obliczeniowa ] .author[ ### Jakub Nowosad <br><a href="https://jakubnowosad.com/" class="uri">https://jakubnowosad.com/</a> ] --- # Złożoność obliczeniowa - Teoria złożoność obliczeniowej (ang. *computational complexity theory*) zajmuje się określaniem ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych - Rozważa ona takie zasoby jak czas (złożoność czasowa), liczba procesorów czy pamięć (złożoność pamięciowa) - Złożoność pamięciowa ma współcześnie mniejsze znaczenie niż złożoność czasowa --- class: inverse, left, bottom # Przykłady złożoności --- # Złożoność liniowa - Wzrost złożoności rośnie zgodnie ze wzrostem elementów - Jest to złożoność liniowa - `\(n\)` --- # Złożoność kwadratowa - Problem porównania par - Np., mamy `\(n\)` drużyn sportowych i każda z drużyn musi zagrać z każdą inną - Jest to złożoność kwadratowa --- # Złożoność kwadratowa - Problem porównania par - Np., mamy `\(n\)` drużyn sportowych i każda z drużyn musi zagrać z każdą inną - Jest to złożoność kwadratowa - Dla `\(n=2\)` jest jedna para, dla `\(n=3\)` są trzy pary, dla `\(n=4\)` jest sześć par, ... --- # Złożoność kwadratowa - Problem porównania par - Np., mamy `\(n\)` drużyn sportowych i każda z drużyn musi zagrać z każdą inną - Jest to złożoność kwadratowa - Dla `\(n=2\)` jest jedna para, dla `\(n=3\)` są trzy pary, dla `\(n=4\)` jest sześć par, ... ``` ## [,1] [,2] [,3] [,4] [,5] ## [1,] 1 1 1 1 1 ## [2,] 1 1 1 1 1 ## [3,] 1 1 1 1 1 ## [4,] 1 1 1 1 1 ## [5,] 1 1 1 1 1 ``` --- # Złożoność kwadratowa - Problem porównania par - Np., mamy `\(n\)` drużyn sportowych i każda z drużyn musi zagrać z każdą inną - Jest to złożoność kwadratowa - Dla `\(n=2\)` jest jedna para, dla `\(n=3\)` są trzy pary, dla `\(n=4\)` jest sześć par, ... ``` ## [,1] [,2] [,3] [,4] [,5] ## [1,] NA 1 1 1 1 ## [2,] 1 NA 1 1 1 ## [3,] 1 1 NA 1 1 ## [4,] 1 1 1 NA 1 ## [5,] 1 1 1 1 NA ``` --- # Złożoność kwadratowa - Problem porównania par - Np., mamy `\(n\)` drużyn sportowych i każda z drużyn musi zagrać z każdą inną - Jest to złożoność kwadratowa - Dla `\(n=2\)` jest jedna para, dla `\(n=3\)` są trzy pary, dla `\(n=4\)` jest sześć par, ... ``` ## [,1] [,2] [,3] [,4] [,5] ## [1,] NA NA NA NA NA ## [2,] 1 NA NA NA NA ## [3,] 1 1 NA NA NA ## [4,] 1 1 1 NA NA ## [5,] 1 1 1 1 NA ``` --- # Złożoność kwadratowa - Problem porównania par - Np., mamy `\(n\)` drużyn sportowych i każda z drużyn musi zagrać z każdą inną - Jest to złożoność kwadratowa - Dla `\(n=2\)` jest jedna para, dla `\(n=3\)` są trzy pary, dla `\(n=4\)` jest sześć par, ... ``` ## [,1] [,2] [,3] [,4] [,5] ## [1,] NA NA NA NA NA ## [2,] 1 NA NA NA NA ## [3,] 1 1 NA NA NA ## [4,] 1 1 1 NA NA ## [5,] 1 1 1 1 NA ``` - `$$n^2 - n / 2$$` --- # Złożoność wykładnicza - Problem wybierania podzbiorów z `\(n\)` elementów - Np., mamy `\(n\)` znaków i chcemy sprawdzić wszystkie potencjalne hasła, które można z nich ułożyć - Jest to złożoność wykładnicza --- # Złożoność wykładnicza - Problem wybierania podzbiorów z `\(n\)` elementów - Np., mamy `\(n\)` znaków i chcemy sprawdzić wszystkie potencjalne hasła, które można z nich ułożyć - Jest to złożoność wykładnicza - Dla `\(n=1\)` są to dwa podzbiory, dla `\(n=2\)` są cztery podzbiory, dla `\(n=3\)` jest osiem podzbiorów, ... --- # Złożoność wykładnicza - Problem wybierania podzbiorów z `\(n\)` elementów - Np., mamy `\(n\)` znaków i chcemy sprawdzić wszystkie potencjalne hasła, które można z nich ułożyć - Jest to złożoność wykładnicza - Dla `\(n=1\)` są to dwa podzbiory, dla `\(n=2\)` są cztery podzbiory, dla `\(n=3\)` jest osiem podzbiorów, ... ``` ## [,1] [,2] [,3] ## [1,] 0 0 0 ## [2,] 0 0 1 ## [3,] 0 1 0 ## [4,] 0 1 1 ## [5,] 1 0 0 ## [6,] 1 0 1 ## [7,] 1 1 0 ## [8,] 1 1 1 ``` --- # Złożoność wykładnicza - Problem wybierania podzbiorów z `\(n\)` elementów - Np., mamy `\(n\)` znaków i chcemy sprawdzić wszystkie potencjalne hasła, które można z nich ułożyć - Jest to złożoność wykładnicza - Dla `\(n=1\)` są to dwa podzbiory, dla `\(n=2\)` są cztery podzbiory, dla `\(n=3\)` jest osiem podzbiorów, ... ``` ## [,1] [,2] [,3] ## [1,] 0 0 0 ## [2,] 0 0 1 ## [3,] 0 1 0 ## [4,] 0 1 1 ## [5,] 1 0 0 ## [6,] 1 0 1 ## [7,] 1 1 0 ## [8,] 1 1 1 ``` - `$$2^n$$` --- # Złożoność wykładnicza https://imgs.xkcd.com/comics/password_strength.png <img src="https://imgs.xkcd.com/comics/password_strength.png" width="65%" style="display: block; margin: auto;" /> https://www.hivesystems.io/blog/are-your-passwords-in-the-green --- # Złożoność silnia - Problem komiwojażera - Np., mamy `\(n\)` miast - na ile sposobów możemy przemieścić się między nimi? - Jest to złożoność silnia --- # Złożoność silnia - Problem komiwojażera - Np., mamy `\(n\)` miast - na ile sposobów możemy przemieścić się między nimi? - Jest to złożoność silnia .pull-left[ <img src="03-complexity_files/figure-html/unnamed-chunk-8-1.png" width="40%" style="display: block; margin: auto;" /> ] .pull-right[ <img src="03-complexity_files/figure-html/unnamed-chunk-9-1.png" width="40%" style="display: block; margin: auto;" /><img src="03-complexity_files/figure-html/unnamed-chunk-9-2.png" width="40%" style="display: block; margin: auto;" /> ] --- # Złożoność silnia - Problem komiwojażera - Np., mamy `\(n\)` miast - na ile sposobów możemy przemieścić się między nimi? - Jest to złożoność silnia .pull-left[ <img src="03-complexity_files/figure-html/unnamed-chunk-10-1.png" width="40%" style="display: block; margin: auto;" /> ] .pull-right[ <img src="03-complexity_files/figure-html/unnamed-chunk-11-1.png" width="40%" style="display: block; margin: auto;" /><img src="03-complexity_files/figure-html/unnamed-chunk-11-2.png" width="40%" style="display: block; margin: auto;" /> ] - Dla `\(n=3\)` jest jedna trasa, dla `\(n=4\)` są trzy trasy, dla `\(n=5\)` jest dwanaście tras, ... --- # Złożoność silnia - Problem komiwojażera - Np., mamy `\(n\)` miast - na ile sposobów możemy przemieścić się między nimi? - Jest to złożoność silnia .pull-left[ <img src="03-complexity_files/figure-html/unnamed-chunk-12-1.png" width="40%" style="display: block; margin: auto;" /> ] .pull-right[ <img src="03-complexity_files/figure-html/unnamed-chunk-13-1.png" width="40%" style="display: block; margin: auto;" /><img src="03-complexity_files/figure-html/unnamed-chunk-13-2.png" width="40%" style="display: block; margin: auto;" /> ] - Dla `\(n=3\)` jest jedna trasa, dla `\(n=4\)` są trzy trasy, dla `\(n=5\)` jest dwanaście tras, ... - `$$(n - 1)! / 2$$` <!-- dlaczego szyfry to nie optymalizacja --> <!-- problemy optymalizacyjne vs problemy decyzyjne --> <!-- transformacja wielomainowa, pseudowielomianowa --> --- class: inverse, left, bottom # Złożoność czasowa --- # Złożoność czasowa - Algorytm wyczerpujący (ang. *exhaustive search*) <img src="03-complexity_files/figure-html/unnamed-chunk-15-1.png" style="display: block; margin: auto;" /> --- # Złożoność czasowa - Algorytm wyczerpujący (ang. *exhaustive search*) <img src="03-complexity_files/figure-html/unnamed-chunk-16-1.png" style="display: block; margin: auto;" /> --- # Złożoność czasowa - Algorytm wyczerpujący (ang. *exhaustive search*) <img src="03-complexity_files/figure-html/unnamed-chunk-17-1.png" style="display: block; margin: auto;" /> --- # Notacja O <!-- https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/ --> - Notacja O (*big O*) to sposób opisu wydajności lub złożoności algorytmu - Opisuje ona najgorszy scenariusz opisujący wymagany czas wykonania algorytmu lub zużycia przez niego zasobów (dysku czy pamięci) --- # Notacja O <!-- https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/ --> - Notacja O (*big O*) to sposób opisu wydajności lub złożoności algorytmu - Opisuje ona najgorszy scenariusz opisujący wymagany czas wykonania algorytmu lub zużycia przez niego zasobów (dysku czy pamięci) Przykładowo: - **O(1)** - stały czas wykonywania algorytmu - **O(N)** - liniowy wzrost czasu wykonywania algorytmu wraz ze wzrostem rozmiaru danych wejściowych - **O(N²)** - potęgowy wzrost czasu wykonywania algorytmu wraz ze wzrostem rozmiaru danych wejściowych - **O(2^N)** - wykładniczy wzrost czasu wykonywania algorytmu wraz ze wzrostem rozmiaru danych wejściowych - **O(N!)** - silnia wzrost czasu wykonywania algorytmu wraz ze wzrostem rozmiaru danych wejściowych <!-- https://stackoverflow.com/questions/1592649/examples-of-algorithms-which-has-o1-on-log-n-and-olog-n-complexities --> https://stackoverflow.com/a/487278 --- # Notacja o - Istnieje jeszcze notacja małego o (*little o*) - Różnica między dużym O a małym o: - Duże O - jest analogiczne do `≤` - określa najgorszy scenariusz (włącznie) (algorytm będzie w najgorszym wypadku taki) - małe o - jest analogiczne do `<` - określa najgorszy scenariusz (wyłącznie) (algorytm w najgorszym wypadku będzie mniej złożony niż) https://stackoverflow.com/q/1364444/2602477 --- # Klasy złożoności problemów - Zbiory problemów obliczeniowych o podobnej złożoności - Istnieją [setki klas złożoności problemów](https://complexityzoo.net/Complexity_Zoo). - **P** - ang. *polynomial* - łatwo znaleźć rozwiązanie, łatwo zweryfikować rozwiązanie - np. mnożenie - **NP** - ang. *nondeterministic polynomial* - łatwo zweryfikować rozwiązanie <!--huge sudoku--> - np. problem komiwojażera - **NP-C** - ang. *nondeterministic polynomial-complete* - trudniejsze problemy niż NP - np. problem plecakowy - **NP-Hard** - ang. *nondeterministic polynomial-hard* - trudniejsze problemy niż NP-C - **EXP** ang. *exponential* - np. najlepszy ruch w szachach - **R** - ang. *recursive* - można rozwiązać w skończonym czas Wideo: - P vs. NP and the Computational Complexity Zoo - https://www.youtube.com/watch?v=YX40hbAHx3s - Beyond Computation: The P vs NP Problem - Michael Sipser - https://www.youtube.com/watch?v=msp2y_Y5MLE <!-- https://www.geeksforgeeks.org/algorithms-gq/np-complete-gq/ --> <!-- - https://www.youtube.com/watch?v=moPtwq_cVH8 --> <!-- - https://www.youtube.com/watch?v=msp2y_Y5MLE --> --- class: inverse, left, bottom # Problemy NP-trudne --- # Problemy NP-trudne - Czas znalezienia optymalnego rozwiązania rośnie bardzo szybko (wykładniczo) wraz ze wzrostem rozmiaru problem <!--przykład--> - Oznacza to, że dla sytuacji o typowych rozmiarach nie jest możliwe znalezienie rozwiązania w realnym czasie --- # Prawo Moore'a - Ogólnie klasa P obejmuje problemy kwadratowe - Klasa NP obejmuje problemy wykładnicze czy silnia - Co kilka lat następuje dwukrotny wzrost mocy komputerów --- # Prawo Moore'a - Ogólnie klasa P obejmuje problemy kwadratowe - Klasa NP obejmuje problemy wykładnicze czy silnia - Co kilka lat następuje dwukrotny wzrost mocy komputerów Zmiana czasu wraz ze wzrostem technologicznym: - **Złożoność liniowa** - 100 obliczeń na godzinę dziś - 200 obliczeń na godzinę za kilka lat -- - **Złożoność kwadratowe** - 100 obliczeń na godzinę dziś - ok. 140 obliczeń na godzinę za kilka lat -- - **Złożoność wykładnicza** - 100 obliczeń na godzinę dziś - 101 obliczeń na godzinę za kilka lat -- - **Złożoność silnia** - 100 obliczeń na godzinę dziś - nadal 100 obliczeń na godzinę za kilka lat (komputer powinien być 101 razy szybszy, aby wykonać kolejne obliczenie) --- class: inverse, left, bottom # Przykłady problemów NP-trudnych --- # Przykłady problemów NP-trudnych Możliwe są w nich rozwiązania heurstyczne (ludzkie podejście) lub jako rozwiązania problemów optymalizacyjnych. - Ułożenie planu zajęć - Rozmieszczenie rycin w tekście - Znalezienie identycznych fragmentów w sekwencjach DNA - Ustalenie kolejności składania samochodów na taśmie produkcyjnej - Stworzenie harmonogramu wyłączania i konserwacji elektrowni - Określenie kolejności i czasu nadawania reklam w TV - Połączenie ludzi w zespoły na podstawie ich kompetencji - Zaprojektuj najlepsze skrzydło samolotu --- # Przykłady problemów NP-trudnych Możliwe są w nich rozwiązania heurstyczne (ludzkie podejście) lub jako rozwiązania problemów optymalizacyjnych. <!--kryteria--> - Rozmieszczenie biur w budynku firmy - Wybranie najlepszego przebiegu linii tramwajowej - Umieszczenie przystanków autobusowych w najkorzystniejszych miejscach - Przeprowadzenie sieci internetowej najtaniej łączącej budynki - Przypisanie szpitali do posiadanych lokalizacji - Określenie trajektorii lotu satelitów/samolotów - Określenie jakie rodzaje zbóż i w jakiej ilości uprawiać w danym roku - [Ustalenie trasy rozwozu towarów ze sklepu](http://optifacility.mooncoder.com/)