- promocja
Algorytmy bez tajemnic - ebook
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!
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
- Algorytm Dijkstry
- 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
- Kody Huffmana
- 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
Kategoria: | Programowanie |
Zabezpieczenie: |
Watermark
|
ISBN: | 978-83-283-6737-1 |
Rozmiar pliku: | 5,7 MB |