Rok wydania: 2013
Oprawa: miękka
Ilość stron:224
Format:16,5 x 23,5 cm
Algorytmy bez tajemnic
Thomas H. Cormen
Poznaj świat algorytmów!
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
- Przedmowa
Czego się nauczysz z tej książki?
Co wypadałoby zawczasu wiedzieć, aby zrozumieć zamieszczony tu materiał?
Zgłaszanie błędów
Podziękowania
- 1. Co to są algorytmy i dlaczego warto poświęcać im uwagę?
Poprawność
Użytkowanie zasobów
Algorytmy komputerowe dla niekomputerowców
Algorytmy komputerowe dla komputerowców
Co czytać dalej
- 2. Jak opisywać i oceniać algorytmy komputerowe
Jak opisywać algorytmy komputerowe
Jak charakteryzować czasy działania
Niezmienniki pętli
Rekursja
Co czytać dalej
- 3. Algorytmy sortowania i wyszukiwania
Wyszukiwanie binarne
Sortowanie przez wybieranie
Sortowanie przez wstawianie
Sortowanie przez scalanie
Sortowanie szybkie
Podsumowanie
Co czytać dalej
- 4. Dolne ograniczenie sortowania i sposoby jego przezwyciężenia
Reguły sortowania
Dolne ograniczenie sortowania przez porównania
Pokonywanie ograniczenia dolnego w sortowaniu przez zliczanie
Sortowanie pozycyjne
Co czytać dalej
- 5. Skierowane grafy acykliczne
Skierowane grafy acykliczne
Sortowanie topologiczne
Jak reprezentować graf skierowany
Czas działania sortowania topologicznego
Ścieżka krytyczna w diagramie PERT
Najkrótsza ścieżka w skierowanym grafie acyklicznym
Co czytać dalej
- 6. Najkrótsze ścieżki
Algorytm Dijkstry
Prosta realizacja tablicowa
Realizacja z kopcem binarnym
Realizacja z użyciem kopca Fibonacciego
Algorytm Bellmana-Forda
Algorytm Floyda-Warshalla
Co czytać dalej
- 7. Algorytmy napisowe
Najdłuższy wspólny podciąg
Zamiana napisu na inny
Dopasowywanie napisów
Co czytać dalej
- 8. Podstawy kryptografii
Proste szyfry podstawieniowe
Kryptografia z kluczem symetrycznym
Podkładka jednorazowa
Szyfry blokowe i łańcuchowanie
Uzgadnianie wspólnych informacji
Kryptografia z kluczem jawnym
Kryptosystem RSA
Jak wykonywać działania arytmetyczne na wielkich liczbach
Jak znajdować duże liczby pierwsze
Jak znaleźć liczbę względnie pierwszą z inną
Jak obliczyć odwrotność multiplikatywną w arytmetyce modularnej
Jak szybko podnieść liczbę do potęgi całkowitej
Wykazanie, że funkcje FP i FS są wzajemnie odwrotnymi
Kryptosystemy hybrydowe
Obliczanie liczb losowych
Co czytać dalej
- 9. Kompresja danych
Kody Huffmana
Adaptacyjne kody Huffmana
Faksy
Kompresja LZW
Ulepszenia LZW
Co czytać dalej
- 10. Trudne (?) problemy
Brązowe furgonetki
Klasy P i NP oraz NP-zupełność
Problemy decyzyjne i redukcje
Problem matka
Próbnik problemów NP-zupełnych
Spełnialność 3-CNF
Klika
Pokrycie wierzchołkowe
Cykl Hamiltona i ścieżka Hamiltona
Komiwojażer
Najdłuższa ścieżka prosta
Suma podzbioru
Podział
Plecak
Ogólne strategie
Przechodź od ogółu do szczegółu
Skorzystaj z ograniczeń problemu, który redukujesz
Poszukuj przypadków specjalnych
Wybierz odpowiedni problem do redukcji
Ustanawiaj duże nagrody i kary
Projektuj gadżety
Perspektywy
Problemy nierozstrzygalne
Podsumowanie
Co czytać dalej
- Literatura