Algorytmy bez tajemnic - ebook

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!

• 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