Algorytmy
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.
Odpowiedzialność: | Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani ; przekład z języka angielskiego Iwona Cieślik, Katarzyna Grygiel, Michał Staromiejski, Bartosz Walczak. |
Seria: | Fundamenty Informatyki |
Hasła: | Algorytmy Podręczniki |
Adres wydawniczy: | Warszawa : Wydawnictwo Naukowe PWN, 2012. |
Wydanie: | Wyd. 1, 3 dodr. |
Opis fizyczny: | XII, 335 s. : il. ; 24 cm. |
Uwagi: | Bibliogr. s. 330-332. Skorowidz. |
Twórcy: | Cieślik, Iwona. Tł. Grygiel, Katarzyna. Tł. Papadimitriou, Christos H. (1949- ). Staromiejski, Michał. Tł. Vazirani, Umesh Virkumar. Walczak, Bartosz. Tł. |
Skocz do: | Dodaj recenzje, komentarz |
- Przedmowa
- 0. Prolog
- 0.1. Książki i algorytmy
- 0.2. Wkracza Fibonacci
- 0.3. Notacja O
- Ćwiczenia
- 1. Algorytmy na liczbach
- 1.1. Podstawowa arytmetyka
- 1.2. Arytmetyka modularna
- 1.3. Testy pierwszości
- 1.4. Kryptografia
- 1.5. Haszowanie uniwersalne
- Ćwiczenia
- 2. Algorytmy „dziel i zwyciężaj”
- 2.1. Mnożenie
- 2.2. Zależności rekurencyjne
- 2.3. Sortowanie przez scalanie
- 2.4. Mediany
- 2.5. Mnożenie macierzy
- 2.6. Szybka transformata Fouriera
- Ćwiczenia
- 3. Dekompozycje grafów
- 3.1. Dlaczego grafy?
- 3.2. Przeszukiwanie w głąb grafu nieskierowanego
- 3.3. Przeszukiwanie w głąb grafu skierowanego
- 3.4. Składowe silnie spójne
- Ćwiczenia
- 4. Ścieżki w grafach
- 4.1. Odległości w grafach
- 4.2. Przeszukiwanie grafu wszerz
- 4.3. Długości krawędzi
- 4.4. Algorytm Dijkstry
- 4.5. Implementacja kolejki priorytetowej
- 4.6. Najkrótsze ścieżki dla grafów z ujemnymi krawędziami
- 4.7. Najkrótsze ścieżki w acyklicznych grafach skierowanych
- Ćwiczenia
- 5. Algorytmy zachłanne
- 5.1. Minimalne drzewo rozpinające
- 5.2. Kodowanie Huffmana
- 5.3. Formuły hornowskie
- 5.4. Pokrycie zbioru
- Ćwiczenia
- 6. Programowanie dynamiczne
- 6.1. Najkrótsze ścieżki w dagach po raz drugi
- 6.2. Najdłuższy podciąg rosnący
- 6.3. Odległość edycyjna
- 6.4. Problem plecakowy
- 6.5. Mnożenie łańcucha macierzy
- 6.6. Najkrótsze ścieżki
- 6.7. Zbiory niezależne w drzewach
- Ćwiczenia
- 7. Programowanie liniowe i redukcje
- 7.1. Wprowadzenie do programowania liniowego
- 7.2. Przepływy w sieciach
- 7.3. Skojarzenia dwudzielne
- 7.4. Dualność
- 7.5. Gry o sumie zerowej
- 7.6. Algorytm sympleks
- 7.7. Postscriptum: ewaluacja układów logicznych
- Ćwiczenia
- 8. Problemy NP-zupełne
- 8.1. Problemy przeszukiwania
- 8.2. Problemy NP-zupełne
- 8.3. Redukcje
- Ćwiczenia
- 9. Jak radzić sobie z NP-zupełnością
- 9.1. Inteligentne przeszukiwanie
- 9.2. Algorytmy aproksymacyjne
- 9.3. Heurystyki oparte na przeszukiwaniu lokalnym
- Ćwiczenia
- 10. Algorytmy kwantowe
- 10.1. Kubity, superpozycja i pomiar
- 10.2. Plan
- 10.3. Kwantowa transformata Fouriera
- 10.4. Okresowość
- 10.5. Kwantowe układy liczące
- 10.6. Rozkład na czynniki jako okresowość
- 10.7. Kwantowy algorytm rozkładu na czynniki
- Ćwiczenia
Zobacz spis treści
Sprawdź dostępność, zarezerwuj (zamów):
(kliknij w nazwę placówki - więcej informacji)