Algorytmy

• Druk: Warszawa, 2010
• Autor: Christos Papadimitriou, Sanjoy Dasgupta, Umesh Vazirani
• Wydawca: Wydawnictwo Naukowe PWN

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.

• Kategorie:
  1. Ebooki i Audiobooki »
  2. Ebooki »
  3. Ebooki popularnonaukowe i specjalistyczne »
  4. Informatyka
• Język wydania: polski
• ISBN: 978-83-01-16278-8
• ISBN druku: 978-83-01-16278-8
• Liczba stron: 360

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