katalog
wydawnictwa
- Wydawnictwo Naukowe PWN
- Oficyna Wydawnicza IMPULS
- Wolters Kluwer Polska
- Wydawnictwo Uniwersytetu Jagiellońskiego
- Wydawnictwo Lekarskie PZWL
- Wydawnictwo WAM
- Wydawnictwa Naukowo-Techniczne
- Wydawnictwa Uniwersytetu Warszawskiego
- Wydawnictwo Naukowe Scholar
- Wydawnictwo Uniwersytetu Kardynała Stefana Wyszyńskiego
- Wydawnictwa Komunikacji i Łączności
- Academica Wydawnictwo SWPS
- Wydawnictwo Akademii Ekonomicznej im. Karola Adamieckiego w Katowicach
- Wydawnictwo Naukowe Akademii Pomorskiej w Słupsku
- Wydawnictwo Uniwersytetu Łódzkiego
- Wydawnictwo Naukowe Uniwersytetu Pedagogicznego w Krakowie
- Wydawnictwo Uniwersytetu Przyrodniczego w Poznaniu
- Scion Publishing Ltd.
- Wydawnictwo Uniwersytetu Kazimierza Wielkiego w Bydgoszczy
- Wydawnictwo Naukowe Uniwersytetu im. Adama Mickiewicza w Poznaniu
- Oficyna Wydawnicza Politechniki Wrocławskiej
- Biblioteka Analiz
Algorytmy
Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani
2010, Wydawnictwo Naukowe PWNLiczba stron: 360
ISBN: 978-83-01-16278-8
XML: format ONIX
Bardzo dobry kurs podstaw algorytmiki. Autorzy, rozpoczynając od zagadnień najprostszych (algorytmów na liczbach, pierwszości i rozkładu na czynniki), omówili w niej m.in. algorytmy dziel i zwyciężaj, sortowania i znajdowania mediany, szybką transformatę Fouriera oraz struktury danych i grafy.
W sposób nowatorski książka opisuje programowanie dynamiczne i programowanie liniowe (intuicyjne ujęcie algorytmu sympleks, dualności i redukcji do problemu podstawowego). Przedstawia też sposoby rozwiązywania problemów NP-zupełnych, wykorzystując przeszukiwanie zachłanne i lokalne algorytmy poszukiwania.
Ostatni rozdział opisuje algorytmy kwantowe. Autorzy robią krótkie wprowadzenie do fizyki kwantowej, co pozwoli na zrozumienie tego rozdziału również czytelnikom, którym tematyka ta była dotychczas nieznana.
| Spis tekstów w ramkach | X |
| Przedmowa | XI |
| 0. Prolog | 1 |
| 0.1. Książki i algorytmy | 1 |
| 0.2. Wkracza Fibonacci | 2 |
| 0.3. Notacja O | 6 |
| Ćwiczenia | 8 |
| 1. Algorytmy na liczbach | 11 |
| 1.1. Podstawowa arytmetyka | 11 |
| 1.2. Arytmetyka modularna | 16 |
| 1.3. Testy pierwszości | 25 |
| 1.4. Kryptografia | 31 |
| 1.5. Haszowanie uniwersalne | 36 |
| Ćwiczenia | 40 |
| 2. Algorytmy „dziel i zwyciężaj” | 47 |
| 2.1. Mnożenie | 47 |
| 2.2. Zależności rekurencyjne | 50 |
| 2.3. Sortowanie przez scalanie | 52 |
| 2.4. Mediany | 55 |
| 2.5. Mnożenie macierzy | 58 |
| 2.6. Szybka transformata Fouriera | 60 |
| Ćwiczenia | 73 |
| 3. Dekompozycje grafów | 83 |
| 3.1. Dlaczego grafy? | 83 |
| 3.2. Przeszukiwanie w głąb grafu nieskierowanego | 86 |
| 3.3. Przeszukiwanie w głąb grafu skierowanego | 91 |
| 3.4. Składowe silnie spójne | 95 |
| Ćwiczenia | 99 |
| 4. Ścieżki w grafach | 109 |
| 4.1. Odległości w grafach | 109 |
| 4.2. Przeszukiwanie grafu wszerz | 110 |
| 4.3. Długości krawędzi | 112 |
| 4.4. Algorytm Dijkstry | 113 |
| 4.5. Implementacja kolejki priorytetowej | 119 |
| 4.6. Najkrótsze ścieżki dla grafów z ujemnymi krawędziami | 122 |
| 4.7. Najkrótsze ścieżki w acyklicznych grafach skierowanych | 125 |
| Ćwiczenia | 126 |
| 5. Algorytmy zachłanne | 133 |
| 5.1. Minimalne drzewo rozpinające | 133 |
| 5.2. Kodowanie Huffmana | 145 |
| 5.3. Formuły hornowskie | 150 |
| 5.4. Pokrycie zbioru | 152 |
| Ćwiczenia | 154 |
| 6. Programowanie dynamiczne | 163 |
| 6.1. Najkrótsze ścieżki w dagach po raz drugi | 163 |
| 6.2. Najdłuższy podciąg rosnący | 164 |
| 6.3. Odległość edycyjna | 166 |
| 6.4. Problem plecakowy | 171 |
| 6.5. Mnożenie łańcucha macierzy | 175 |
| 6.6. Najkrótsze ścieżki | 178 |
| 6.7. Zbiory niezależne w drzewach | 183 |
| Ćwiczenia | 184 |
| 7. Programowanie liniowe i redukcje | 195 |
| 7.1. Wprowadzenie do programowania liniowego | 195 |
| 7.2. Przepływy w sieciach | 206 |
| 7.3. Skojarzenia dwudzielne | 213 |
| 7.4. Dualność | 214 |
| 7.5. Gry o sumie zerowej | 218 |
| 7.6. Algorytm sympleks | 222 |
| 7.7. Postscriptum: ewaluacja układów logicznych | 231 |
| Ćwiczenia | 233 |
| 8. Problemy NP-zupełne | 243 |
| 8.1. Problemy przeszukiwania | 243 |
| 8.2. Problemy NP-zupełne | 255 |
| 8.3. Redukcje | 259 |
| Ćwiczenia | 276 |
| 9. Jak radzić sobie z NP-zupełnością | 283 |
| 9.1. Inteligentne przeszukiwanie | 284 |
| 9.2. Algorytmy aproksymacyjne | 288 |
| 9.3. Heurystyki oparte na przeszukiwaniu lokalnym | 297 |
| Ćwiczenia | 306 |
| 10. Algorytmy kwantowe | 310 |
| 10.1. Kubity, superpozycja i pomiar | 310 |
| 10.2. Plan | 314 |
| 10.3. Kwantowa transformata Fouriera | 316 |
| 10.4. Okresowość | 318 |
| 10.5. Kwantowe układy liczące | 322 |
| 10.6. Rozkład na czynniki jako okresowość | 323 |
| 10.7. Kwantowy algorytm rozkładu na czynniki | 324 |
| Ćwiczenia | 327 |
| Noty historyczne i literatura uzupełniająca | 330 |
| Skorowidz | 333 |
