Algorytmy
Tyt. oryg.: "Algorithms, ".
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.
Zobacz pełny opis| Odpowiedzialność: | Sanjoy Dasgupta, Christos Papadmitriou, Umesh Vazirani ; przekład z angielskiego Iwona Cieślik, Katarzyna Grygiel, Michał Staromiejski, Bartosz Walczak. |
| Seria: | Fundamenty Informatyki |
| Hasła: | Algorytmy Programowanie liniowe Podręczniki |
| Adres wydawniczy: | Warszawa : Wydawnictwo Naukowe PWN, 2010. |
| Opis fizyczny: | 335, [2] s. : il. ; 24 cm. |
| Uwagi: | Bibliogr. s. 330-332. Indeks. |
| Twórcy: | Cieślik, Iwona. Tłumaczenie Grygiel, Katarzyna. Tłumaczenie Papadimitriou, Christos H. Staromiejski, Michał. Tłumaczenie Vazirani, Umesh Virkumar. Walczak, Bartosz M. Tłumaczenie |
| Powiązane zestawienia: | Matematyka Informatyka |
| Skocz do: | Dodaj recenzje, komentarz |
- Spis tekstów w ramkach
- Przedmowa
- 0. Prolog
- 0.1. Książki i algorytmy
- 1 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
- Noty historyczne i literatura uzupełniająca
- Skorowidz
Zobacz spis treści
Sprawdź dostępność, zarezerwuj (zamów):
(kliknij w nazwę placówki - więcej informacji)