podstawy algorytmów z przykładami w c++ helion.pdf

(46117 KB) Pobierz
6
Podstawy algorytmów z przykładami w C++
Rozdział 4. Podejście zachłanne ............................................................................157
4.1. Minimalne drzewo rozpinające....................................................................................... 161
4.1.1. Algorytm Prima .................................................................................................... 163
4.1.2. Algorytm Kruskala ............................................................................................... 169
4.1.3. Porównanie algorytmu Prima z algorytmem Kruskala......................................... 173
4.1.4. Dyskusja końcowa ................................................................................................ 173
4.2. Algorytm Dijkstry najkrótszych dróg z jednego źródła ................................................. 174
4.3. Szeregowanie.................................................................................................................. 177
4.3.1. Minimalizacja całkowitego czasu w systemie ...................................................... 178
4.3.2. Szeregowanie z terminami granicznymi............................................................... 180
4.4. Kod Huffmana ................................................................................................................ 188
4.4.1. Kody prefiksowe................................................................................................... 189
4.4.2. Algorytm Huffmana.............................................................................................. 190
4.5. Podejście zachłanne a programowanie dynamiczne: problem plecakowy ..................... 194
4.5.1. Podejście zachłanne do problemu plecakowego 0-1 ............................................ 195
4.5.2. Podejście zachłanne do ułamkowego problemu plecakowego ............................. 196
4.5.3. Podejście programowania dynamicznego do problemu plecakowego 0-1........... 197
4.5.4. Poprawiona wersja algorytmu programowania dynamicznego
dla problemu plecakowego 0-1 .......................................................................... 197
Ćwiczenia ............................................................................................................................... 201
Rozdział 5. Algorytmy z powrotami.........................................................................207
5.1. Techniki algorytmów z powrotami................................................................................. 208
5.2. Problem n-królowych ..................................................................................................... 215
5.3. Zastosowanie algorytmu Monte Carlo do oszacowania wydajności
algorytmu z powrotami ................................................................................................ 219
5.4. Problem sumy podzbiorów ............................................................................................. 223
5.5. Kolorowanie grafu .......................................................................................................... 228
5.6. Problem cyklu Hamiltona ............................................................................................... 232
5.7. Problem plecakowy 0-1 .................................................................................................. 235
5.7.1. Algorytm z powrotami dla problemu plecakowego 0-1 ....................................... 235
5.7.2. Porównanie algorytmu programowania dynamicznego
z algorytmem z powrotami do rozwiązywania problemu plecakowego 0-1......... 244
Ćwiczenia ............................................................................................................................... 245
Rozdział 6. Metoda podziału i ograniczeń ...............................................................251
6.1. Ilustracja metody podziału i ograniczeń dla problemu plecakowego 0-1 ...................... 253
6.1.1. Przeszukiwanie wszerz z przycinaniem metodą podziału i ograniczeń ............... 253
6.1.2. Przeszukiwanie typu najpierw najlepszy z przycinaniem
metodą podziału i ograniczeń............................................................................. 258
6.2. Problem komiwoja era ................................................................................................... 264
6.3. Wnioskowanie abdukcyjne (diagnozowanie) ................................................................. 272
Ćwiczenia ............................................................................................................................... 281
Rozdział 7. Wprowadzenie do złożoności obliczeniowej: problem sortowania ............285
7.1. Zło oność obliczeniowa ................................................................................................. 286
7.2. Sortowanie przez wstawianie i sortowanie przez wybieranie ........................................ 288
7.3. Dolne ograniczenia dla algorytmów usuwających co najwy ej jedną inwersję
dla jednej operacji porównania .................................................................................... 294
7.4. Przypomnienie algorytmu sortowania przez scalanie..................................................... 297
7.5. Przypomnienie algorytmu szybkiego sortowania........................................................... 303
7.6. Sortowanie stogowe........................................................................................................ 305
7.6.1. Stogi i podstawowe na nich operacje.................................................................... 305
7.6.2. Implementacja algorytmu sortowania stogowego ................................................ 309
Spis treści
7
7.7. Zestawienie algorytmów sortowania przez scalanie, sortowania szybkiego
i sortowania stogowego................................................................................................ 316
7.8. Dolne ograniczenia dla algorytmów sortujących wyłącznie na podstawie
operacji porównania kluczy ......................................................................................... 317
7.8.1. Drzewa decyzyjne dla algorytmów sortujących ................................................... 317
7.8.2. Dolne ograniczenia dla najgorszego przypadku ................................................... 320
7.8.3. Dolne ograniczenia dla średniego przypadku....................................................... 323
7.9. Sortowanie przez podział (sortowanie pozycyjne) ......................................................... 328
Ćwiczenia ............................................................................................................................... 332
Rozdział 8. Więcej o złożoności obliczeniowej: problem przeszukiwania ...................339
8.1. Dolne ograniczenia dla przeszukiwania wyłącznie na podstawie
porównywania wartości kluczy.................................................................................... 340
8.1.1. Dolne ograniczenia dla najgorszego przypadku ................................................... 343
8.1.2. Dolne ograniczenia dla średniego przypadku....................................................... 345
8.2. Przeszukiwanie przez interpolację.................................................................................. 351
8.3. Przeszukiwanie w drzewach ........................................................................................... 354
8.3.1. Drzewa wyszukiwania binarnego ......................................................................... 355
8.3.2. B-drzewa............................................................................................................... 360
8.4. Mieszanie........................................................................................................................ 361
8.5. Problem wyboru: wprowadzenie metody dyskusji z adwersarzem ................................ 367
8.5.1. Znajdowanie największego klucza ....................................................................... 367
8.5.2. Znajdowanie zarówno najmniejszego, jak i największego klucza ....................... 369
8.5.3. Znajdowanie drugiego największego klucza ........................................................ 376
8.5.4. Znajdowanie k-tego najmniejszego klucza........................................................... 381
8.5.5. Algorytm probabilistyczny dla problemu wyboru................................................ 390
Ćwiczenia ............................................................................................................................... 395
Rozdział 9. Złożoność obliczeniowa i trudność problemów:
wprowadzenie do teorii o zbiorze NP .....................................................401
9.1. Trudność ......................................................................................................................... 402
9.2. Ponowne omówienie zagadnienia rozmiaru danych wejściowych................................. 404
9.3. Trzy główne kategorie problemów ................................................................................. 409
9.3.1. Problemy, dla których wynaleziono algorytmy wielomianowe ........................... 409
9.3.2. Problemy, których trudność została udowodniona............................................... 410
9.3.3. Problemy, których trudność nie została udowodniona, jednak nie udało się
znaleźć rozwiązujących je algorytmów wielomianowych................................. 411
9.4. Teoria o zbiorze NP ........................................................................................................ 411
9.4.1. Zbiory P i NP ........................................................................................................ 414
9.4.2. Problemy NP-zupełne........................................................................................... 419
9.4.3. Problemy NP-trudne, NP-łatwe i NP-równowa ne .............................................. 431
9.5. Sposoby rozwiązywania problemów NP-trudnych ........................................................ 435
9.5.1. Algorytm przybli ony dla problemu komiwoja era............................................. 436
9.5.2. Przybli ony algorytm dla problemu pakowania ................................................... 441
Ćwiczenia ............................................................................................................................... 446
Rozdział 10. Algorytmy teorii liczb ...........................................................................449
10.1. Przegląd teorii liczb....................................................................................................... 450
10.1.1. Liczby zło one i liczby pierwsze ...................................................................... 450
10.1.2. Największy wspólny dzielnik............................................................................ 451
10.1.3. Rozkładanie liczb całkowitych na czynniki pierwsze ....................................... 455
10.1.4. Najmniejsza wspólna wielokrotność ................................................................. 457
10.2. Wyznaczanie największego wspólnego dzielnika......................................................... 457
10.2.1. Algorytm Euklidesa........................................................................................... 458
10.2.2. Rozszerzenie algorytmu Euklidesa.................................................................... 462
8
Podstawy algorytmów z przykładami w C++
10.3. Przegląd arytmetyki modularnej.................................................................................... 465
10.3.1. Teoria grup ........................................................................................................ 465
10.3.2. Kongruencja modulo n ...................................................................................... 467
10.3.3. Podgrupy ........................................................................................................... 473
10.4. Rozwiązywanie modularnych równań liniowych ......................................................... 479
10.5. Obliczanie modularnych potęg...................................................................................... 485
10.6. Znajdowanie wielkich liczb pierwszych ....................................................................... 488
10.6.1. Szukanie liczby pierwszej ................................................................................. 488
10.6.2. Sprawdzanie, czy dana liczba całkowita jest liczbą pierwszą........................... 489
10.7. System szyfrowania RSA z publicznym kluczem......................................................... 508
10.7.1. Systemy szyfrowania z kluczem publicznym.................................................... 508
10.7.2. System szyfrowania RSA .................................................................................. 509
Ćwiczenia ............................................................................................................................... 512
Rozdział 11. Wprowadzenie do algorytmów równoległych..........................................517
11.1. Architektury równoległe................................................................................................ 521
11.1.1. Mechanizm sterowania...................................................................................... 521
11.1.2. Organizacja przestrzeni adresowej .................................................................... 522
11.1.3. Sieci łączące ...................................................................................................... 524
11.2. Model PRAM ................................................................................................................ 527
11.2.1. Projektowanie algorytmów dla modelu CREW PRAM.................................... 531
11.2.2. Projektowanie algorytmów dla modelu CRCW PRAM.................................... 538
Ćwiczenia ............................................................................................................................... 541
Dodatek A Przegląd niezbędnej wiedzy matematycznej...........................................543
A.1. Notacja............................................................................................................................ 543
A.2. Funkcje ........................................................................................................................... 545
A.3. Indukcja matematyczna .................................................................................................. 546
A.4. Twierdzenia i lematy ...................................................................................................... 553
A.5. Logarytmy....................................................................................................................... 554
A.5.1. Definicja i właściwości logarytmów.................................................................... 554
A.5.2. Logarytm naturalny.............................................................................................. 557
A.6. Zbiory ............................................................................................................................. 559
A.7. Permutacje i kombinacje................................................................................................. 560
A.8. Prawdopodobieństwo...................................................................................................... 563
A.8.1. Losowość ............................................................................................................. 569
A.8.2. Wartość oczekiwana ............................................................................................ 573
Ćwiczenia ............................................................................................................................... 575
Dodatek B Rozwiązywanie równań rekurencyjnych
na potrzeby analizy algorytmów rekurencyjnych ....................................581
B.1. Rozwiązywanie rekurencji za pomocą indukcji ............................................................. 581
B.2. Rozwiązywanie rekurencji z zastosowaniem równań charakterystycznych................... 585
B.2.1. Homogeniczna rekurencja liniowa....................................................................... 585
B.2.2. Niehomogeniczna rekurencja liniowa.................................................................. 594
B.2.3. Zamiana zmiennej (przekształcenie dziedziny) ................................................... 600
B.3. Rozwiązywanie rekurencji przez podstawianie.............................................................. 603
B.4. Rozszerzanie wyników dla n będącego potęgą dodatniej stałej b
do wyników dla dowolnego n ...................................................................................... 605
B.5. Dowody twierdzeń.......................................................................................................... 611
Ćwiczenia ............................................................................................................................... 614
Dodatek C Struktury danych dla zbiorów rozłącznych .............................................621
Dodatek D Bibliografia ..........................................................................................631
Rozdział 3.
Programowanie
dynamiczne
Jak zapewne Czytelnik pamięta, liczba składników obliczanych przez algorytm
typu
dziel i zwycię aj
w celu określenia
n-tego
wyrazu ciągu Fibonacciego (algo-
rytm 1.6) jest wykładnicza w stosunku do
n.
Wynika to z faktu, e podejście typu
dziel i zwycię aj
rozwiązuje realizację problemu poprzez jej podział na mniejsze
realizacje, a następnie bezpośrednie rozwiązywanie owych mniejszych realizacji. Jak
stwierdzono w rozdziale 2., jest to podejście zstępujące. Sprawdza się ono w przy-
padku problemów w rodzaju sortowania przez scalanie, gdzie mniejsze instancje nie
są ze sobą powiązane. Dzieje się tak, poniewa ka da z nich składa się z tablicy
kluczy, które muszą zostać posortowane niezale nie. Jednak e w przypadku pro-
blemów takich, jak
n-ty
wyraz ciągu Fibonacciego, mniejsze instancje są ze sobą
powiązane. Przykładowo, zgodnie z tym, co przedstawiono w podrozdziale 1.2,
obliczenie piątego wyrazu ciągu Fibonacciego wymaga obliczenia wyrazu trze-
ciego i czwartego. Jednak procesy określania czwartego i trzeciego wyrazu są ze
sobą związane o tyle, e oba wymagają znajomości wyrazu drugiego. Ze względu
na fakt, e algorytm typu
dziel i zwycię aj
wykonuje oba procesy niezale nie, drugi
wyraz ciągu Fibonacciego jest obliczany wielokrotnie. W przypadku problemów,

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin