Polski
ebook
Algorytmy
Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani
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.
Ten produkt nie ma jeszcze opinii
Twoja opinia
aby wystawić opinię.
- Przesyłka email dla e-book 0.00 zł brutto
Opis produktu
- Tytuł
- Algorytmy
- Autorzy
- Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani
- Język
- polski
- Wydawnictwo
- Wydawnictwo Naukowe PWN
- ISBN
- 978-83-01-16278-8
- Rok wydania
- 2010 Warszawa
- Wydanie
- 1
- Liczba stron
- 360
- Format
- Spis treści
- 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
