Podstawy algorytmow z przykladami 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
Tytu³ orygina³
u:
Foundations of Algorithms.
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
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
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
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
Plik z chomika:
kronos78
Inne pliki z tego folderu:
Asembler dla procesorow Intel Vademecum profesjonalisty.pdf
(400 KB)
Asembler cwiczenia praktyczne.pdf
(358 KB)
Architektura systemow zarzadzania przedsiebiorstwem Wzorce projektowe.pdf
(829 KB)
Architektura oprogramowania Metody oceny oraz analiza przypadkow.pdf
(429 KB)
Aplikacje w Visual C++ 2005 Przyklady.pdf
(296 KB)
Inne foldery tego chomika:
!!!!!!!!ze słowackiego radia, niektore opisanie, inne nie
# - Wzory CV
▶ Porady remontowo - budowlane
▶ Remont domu - poradnik
• AGD - kody błędów pralek automatycznych
Zgłoś jeśli
naruszono regulamin