Podstawy algorytmów z przykładami w C.pdf

(3030 KB) Pobierz
C:\Andrzej\PDF\ABC nagrywania p³yt CD\1 strona.cdr
IDZ DO
PRZYK£ADOW Y ROZDZIA£
Podstawy algorytmów
SPIS TRECI
z przyk³adami w C++
KATALOG KSI¥¯EK
Autorzy: Richard Neapolitan, Kumarss Naimipour
T³umaczenie: Bart³omiej Garbacz, Pawe³ Gonera,
Artur Szczepaniak, Miko³aj Szczepaniak
ISBN: 83-7361-429-X
Using C++ Pseudocode
Format: B5, stron: 648
KATALOG ONLINE
ZAMÓW DRUKOWANY KATALOG
TWÓJ KOSZYK
DODAJ DO KOSZYKA
Algorytmy s¹ jednym z fundamentów programowania. Prawid³owo zaprojektowany
algorytm jest podstaw¹ efektywnego i niezawodnego programu. Opisanie problemu
w postaci algorytmu nie jest prostym zadaniem — wymaga wiedzy z zakresu
matematyki, umiejêtnoci oceny z³o¿onoci obliczeniowej i znajomoci zasad
optymalizacji obliczeñ. Istnieje wiele metod projektowania algorytmów.
Znajomoæ tych metod znacznie u³atwia analizê zagadnienia i przedstawienie go
w postaci zalgorytmizowanej.
Ksi¹¿ka „Podstawy algorytmów z przyk³adami w C++” to kompletny podrêcznik
powiêcony tym w³anie zagadnieniom. Przedstawia sposoby podejcia
do rozwi¹zywania zagadnieñ projektowych, udowadnia, ¿e sporo z nich mo¿na
zrealizowaæ ró¿nymi metodami, a tak¿e uczy, jak dobraæ w³aciw¹ metodê
do postawionego problemu. Materia³ podzielony jest na wyk³ady, zilustrowane
pseudokodem przypominaj¹cym jêzyk C++, co bardzo u³atwia zastosowanie
poznanej wiedzy w praktyce.
• Wprowadzenie do projektowania algorytmów
• Zastosowanie techniki dziel i zwyciê¿aj
• Algorytmy programowania dynamicznego
• Analiza z³o¿onoci obliczeniowej algorytmów na przyk³adzie
lgorytmów sortowania i przeszukiwania
• Algorytmy z zakresu teorii liczb
• Algorytmy kompresji danych i kryptografii
• Programowanie równoleg³e
Wyk³ady powiêcone algorytmom s¹ uzupe³nione dodatkami, zawieraj¹cymi
kompendium niezbêdnej wiedzy z dziedziny matematyki, technik rekurencyjnych
i algebry zbiorów.
„Podstawy algorytmów z przyk³adami w C++” to doskona³y podrêcznik dla uczniów,
studentów i wszystkich, którzy chc¹ poznaæ tê dziedzinê wiedzy.
CENNIK I INFORMACJE
ZAMÓW INFORMACJE
O NOWOCIACH
ZAMÓW CENNIK
CZYTELNIA
FRAGMENTY KSI¥¯EK ONLINE
Wydawnictwo Helion
ul. Chopina 6
44-100 Gliwice
tel. (32)230-98-63
e-mail: helion@helion.pl
215914926.007.png 215914926.008.png 215914926.009.png
Spis treci
O Autorach..............................................................................................9
Przedmowa............................................................................................11
Rozdział 1. Algorytmy — wydajno, analiza i rz d ...................................................17
1.1. Algorytmy......................................................................................................................... 18
1.2. Znaczenie opracowywania wydajnych algorytmów......................................................... 25
1.2.1. Wyszukiwanie sekwencyjne a wyszukiwanie binarne ........................................... 26
1.2.2. Ci#g Fibonacciego .................................................................................................. 28
1.3. Analiza algorytmów.......................................................................................................... 33
1.3.1. Analiza zło'ono(ci.................................................................................................. 33
1.3.2. Zastosowanie teorii................................................................................................. 41
1.3.3. Analiza poprawno(ci .............................................................................................. 42
1.4. Rz#d.................................................................................................................................. 42
1.4.1. Intuicyjne wprowadzenie do problematyki rz,du................................................... 43
1.4.2. Formalne wprowadzenie do problematyki rz,du ................................................... 45
1.4.3. Wykorzystanie granic do okre(lenia rz,du............................................................. 56
1.5. Zarys dalszej tre(ci ksi#'ki............................................................................................... 59
.wiczenia................................................................................................................................. 60
Rozdział 2. Dziel i zwyci$%aj.....................................................................................65
2.1. Wyszukiwanie binarne...................................................................................................... 66
2.2. Sortowanie przez scalanie................................................................................................. 71
2.3. Podej(cie typu dziel i zwyci,'aj........................................................................................ 77
2.4. Sortowanie szybkie (sortowanie przez podstawienie podziałów)..................................... 78
2.5. Algorytm Strassena mno'enia macierzy........................................................................... 85
2.6. Arytmetyka wielkich liczb całkowitych............................................................................ 90
2.6.1. Reprezentacja wielkich liczb całkowitych: dodawanie i inne operacje
wykonywane w czasie liniowym ......................................................................... 91
2.6.2. Mno'enie wielkich liczb całkowitych .................................................................... 91
2.7. Okre(lanie warto(ci progowych........................................................................................ 97
2.8. Przeciwwskazania do u'ywania podej(cia dziel i zwyci,'aj.......................................... 101
.wiczenia............................................................................................................................... 103
Rozdział 3. Programowanie dynamiczne .................................................................111
3.1. Współczynnik dwumianowy........................................................................................... 112
3.2. Algorytm Floyda okre(lania najkrótszej drogi w grafie.................................................. 117
3.3. Programowanie dynamiczne a problemy optymalizacyjne............................................. 125
3.4. Ła:cuchowe mno'enie macierzy .................................................................................... 127
3.5. Optymalne drzewa wyszukiwania binarnego.................................................................. 136
3.6. Problem komiwoja'era.................................................................................................... 145
.wiczenia............................................................................................................................... 152
 
215914926.001.png
6
Podstawy algorytmów z przykładami w C++
Rozdział 4. Podejcie 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%onoci obliczeniowej: problem sortowania............285
7.1. Zło'ono(A 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
 
215914926.002.png
Spis treci
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%onoci 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(A ......................................................................................................................... 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(A została udowodniona............................................... 410
9.3.3. Problemy, których trudno(A nie została udowodniona, jednak nie udało si,
znale=A 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(A................................................................. 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(A ............................................................................................................. 569
A.8.2. Warto(A 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
215914926.003.png 215914926.004.png 215914926.005.png 215914926.006.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin