Algorytmy bez tajemnic

Każdy program działa według określonego algorytmu - Twoja nawigacja GPS, system płatności elektronicznych, wyszukiwarka Google. Algorytmy są jak przepisy kucharskie: zrób to, sprawdź tamto. Jednak konsekwencje popełnienia błędu w algorytmie są zupełnie inne niż w przypadku niesprawdzonego przepisu. To właśnie algorytmy decydują o czasie wykonania skomplikowanych operacji przez programy komputerowe, a ich odpowiednia lub nieodpowiednia implementacja może sprawić, że Twój projekt wart miliony odniesie sukces lub poniesie porażkę.

Dzięki tej książce będziesz mógł bezboleśnie wkroczyć w świat algorytmów. W trakcie lektury dowiesz się, czym tak naprawdę są algorytmy, jak się je projektuje i prezentuje. Po wstępie teoretycznym poznasz najpopularniejsze algorytmy sortowania i wyszukiwania, algorytmy znajdowania najkrótszej ścieżki oraz algorytmy operujące na ciągach znaków. Następnie przejdziesz do najciekawszych zagadnień związanych z kryptografią i kompresją danych. Zastanawiasz się, czy są miejsca, w których znane algorytmy nie radzą sobie zbyt dobrze? To problemy NP-zupełne - z nimi też będziesz mógł się zaznajomić. Książka ta jest interesującym przewodnikiem po świecie algorytmów, a zarazem przyjemną lekturą dla każdego programisty i pasjonata informatyki.

Poznaj algorytmy:

• sortujące i wyszukujące
• znajdowania najkrótszej ścieżki
• kryptograficzne
• kompresujące

Dowiedz się, jak działają aplikacje kompresujące i szyfrujące.

Spis treści:

1. Co to są algorytmy i dlaczego warto poświęcać im uwagę? (15)

• Poprawność (16)
• Użytkowanie zasobów (17)
• Algorytmy komputerowe dla niekomputerowców (19)
• Algorytmy komputerowe dla komputerowców (20)
• Co czytać dalej (21)

2. Jak opisywać i oceniać algorytmy komputerowe (23)

• Jak opisywać algorytmy komputerowe (23)
• Jak charakteryzować czasy działania (29)
• Niezmienniki pętli (33)
• Rekursja (34)
• Co czytać dalej (36)

3. Algorytmy sortowania i wyszukiwania (37)

• Wyszukiwanie binarne (39)
• Sortowanie przez wybieranie (43)
• Sortowanie przez wstawianie (46)
• Sortowanie przez scalanie (50)
• Sortowanie szybkie (59)
• Podsumowanie (66)
• Co czytać dalej (69)

4. Dolne ograniczenie sortowania i sposoby jego przezwyciężenia (71)

• Reguły sortowania (71)
• Dolne ograniczenie sortowania przez porównania (72)
• Pokonywanie ograniczenia dolnego w sortowaniu przez zliczanie (73)
• Sortowanie pozycyjne (79)
• Co czytać dalej (81)

5. Skierowane grafy acykliczne (83)

• Skierowane grafy acykliczne (87)
• Sortowanie topologiczne (87)
• Jak reprezentować graf skierowany (90)
• Czas działania sortowania topologicznego (92)
• Ścieżka krytyczna w diagramie PERT (92)
• Najkrótsza ścieżka w skierowanym grafie acyklicznym (96)
• Co czytać dalej (100)

6. Najkrótsze ścieżki (101)

• Algorytm Dijkstry (102)
• Algorytm Bellmana-Forda (111)
• Algorytm Floyda-Warshalla (115)
• Co czytać dalej (123)

7. Algorytmy napisowe (125)

• Najdłuższy wspólny podciąg (125)
• Zamiana napisu na inny (130)
• Dopasowywanie napisów (137)
• Co czytać dalej (144)

8. Podstawy kryptografii (145)

• Proste szyfry podstawieniowe (146)
• Kryptografia z kluczem symetrycznym (147)
• Kryptografia z kluczem jawnym (151)
• Kryptosystem RSA (153)
• Kryptosystemy hybrydowe (160)
• Obliczanie liczb losowych (161)
• Co czytać dalej (162)

9. Kompresja danych (163)

• Kody Huffmana (164)
• Faksy (170)
• Kompresja LZW (171)
• Co czytać dalej (180)

10. Trudne (?) problemy (181)

• Brązowe furgonetki (181)
• Klasy P i NP oraz NP-zupełność (184)
• Problemy decyzyjne i redukcje (186)
• Problem matka (189)
• Próbnik problemów NP-zupełnych (191)
• Ogólne strategie (204)
• Perspektywy (206)
• Problemy nierozstrzygalne (208)
• Podsumowanie (210)
• Co czytać dalej (211)