Książki do nauki algorytmów i struktur danych

Patrząc na ilość wątków, w których ludzie pytają się, „z czego uczyć się algorytmiki” postanowiłem napisać artykuł, w którym byłaby opisana literatura do nauki algorytmów nienumerycznych oraz tego, co jest potrzebne do jej studiowania, czyli matematyki dyskretnej. Algorytmika w porównaniu z innymi działami informatyki nie starzeje się. Książka z lat 70 może służyć bardzo dobrze również w dzisiejszych czasach. Tylko żeby ktoś nie myślał, że nie ma obecnie postępu w tym najstarszym dziale informatyki. Owszem jest, ale jest najczęściej dokumentowany w różnych pracach naukowych lub w najnowszej literaturze specjalistycznej, która jest najczęściej dostępna tylko w języku angielskim.

Przegląd literatury będzie podzielony na kategorie – początkujący, średniozaawansowany i zaawansowany, które oznaczają wiedzę potrzebną do czytania książek (nie zawsze algorytmiczną, lecz czasami np. matematyczną).

Początkujący:

Jeżeli ma być to twoja pierwsza lektura z algorytmiki, to tutaj znajdziesz coś dla siebie. Przydaje się znajomość programowania w jakimś języku (najczęściej Pascal lub C/C++), ale często nie jest konieczna.

Algorytmy

Autor: Maciej Marek Sysło
Wydawnictwo: WSIP
Rok wydania: 2008
Ilość stron: 288
Gdzie kupić: dostępna w sprzedaży
Język: Pascal

Książka zawiera wiedzę z algorytmiki na poziomie szkoły średniej. Nie jest wymagana żadna wiedza na temat programowania, przydaje się jedynie znajomość języka Pascal, ale nie jest konieczna. Algorytmy są opisane w postaci listy kroków, czasami w Pascalu (wszystkie kody w tym języku można pobrać ze strony wydawcy), a czasami w ELI – programie do tworzenia schematów blokowych. Książka jest bardzo dobra dla osoby, która jeszcze dokładnie nie wie, co to jest algorytm oraz dla przygotowującej się do matury. Na końcu zawiera zadania maturalne z omówieniem.

Rozdziały:

1. Algorytmy i sposoby ich przedstawiania
2. Algorytmy liniowe
3. Algorytmy z rozgałęzieniami
4. Porządkowanie kilku liczb
5. O czym mówią dane — algorytmy iteracyjne
6. Porządkowanie ciągu elementów
7. Inne algorytmy iteracyjne — schemat Hornera, algorytm Euklidesa, sito Eratostenesa
8. Algorytmy rekurencyjne
9. Dziel i zwyciężaj
10. Porządkowanie ciągu elementów
11. Wychodzenie z labiryntu i pakowanie plecaka
12. Własności algorytmów — podsumowanie
13. Problemy
14. Gdzie szukać dalszych informacji o algorytmach
15. Algorytmika w zadaniach maturalnych

Algorytmy + struktury danych = programy

Autor: Niklaus Wirth
Wydawnictwo: WNT
Rok wydania: 2004
Ilość stron: 382
Gdzie kupić: allegro, antykwariaty
Język: Pascal

Niklaus Wirth, twórca języka Pascal przedstawia nam algorytmikę od podstaw. Jedynym wymaganiem jest pewne obycie z językiem Pascal, wystarczą podstawy, ponieważ autor wyjaśnia elementy języka związane ze strukturami danych. Polecana przez wielu, klasyczna lektura z podstaw algorytmów i struktur danych.

Rozdziały:

1.Podstawowe struktury danych
2. Sortowanie
3. Algorytmy rekurencyjne
4. Dynamiczne struktury informacyjne
5. Struktury językowe i kompilatory

Perełki oprogramowania / Perełki programowania

Autor: Jon Bentley
Wydawnictwo: WNT/Helion
Rok wydania: 2008 WNT/2011 (w planach)
Ilość stron: 300
Gdzie kupić: dostępne w sprzedaży (od wydawnictwa Helion)/allegro (od wydawnictwa WNT)
Język: C/C++

Książka omawia algorytmy, najczęściej praktyczne. Jest to pozycja wyróżniająca się, ponieważ opowiada o tym jak praktycznie pisać szybkie programy. Jest to zbiór artykułów Jona Bentley’a, które autor postanowił zebrać w całość. Autor przytacza różne historie, które przydarzyły mu się podczas jego kariery programisty. Wymagana znajomość dowolnego języka, ale najlepiej C i C++, w których są pisane programy. Istnieje również inna książka tego samego autora „Więcej perełek oprogramowania. Wyznania programisty”, powinny po nią sięgnąć osoby, którym spodobała się ta książka.

Część I. Podstawowe wiadomości
Rozdział 1. Otwieranie ostrygi
Rozdział 2. Algorytmy typu Aha!
Rozdział 3. Programy podporządkowane strukturom danych
Rozdział 4. Pisanie poprawnych programów
Rozdział 5. Drobna kwestia programowania

Część II. Efektywność programów
Rozdział 6. O efektywności ogólnie
Rozdział 7. Obliczenia na odwrocie koperty
Rozdział 8. Techniki projektowania algorytmów
Rozdział 9. Doskonalenie kodu
Rozdział 10. Ograniczanie wykorzystywanej pamięci

Część III. Produkt
Rozdział 11. Sortowanie
Rozdział 12. Przykładowy problem
Rozdział 13. Wyszukiwanie
Rozdział 14. Kopce
Rozdział 15. Sznury perełek

Więcej perełek oprogramowania. Wyznania programisty

Autor: Jon Bentley
Wydawnictwo: WNT
Rok wydania: 2008
Ilość stron: 260
Gdzie kupić: allegro
Język: C/C++, Awk

Kolejny zbiór artykułów Jona Bentley’a. Tym razem autor czasami używa również języka Awk.

Rozdziały:

Część I. Metody programowania
Rozdział 1. Systemy profilowania
Rozdział 2. Tablice asocjacyjne
Rozdział 3. Wyznania programisty
Rozdział 4. Samoopisujące się dane

Część II. Zawodowe sztuczki
Rozdział 5. Przecinanie węzła gordyjskiego
Rozdział 6. Informatyczne slogany
Rozdział 7. Powrót koperty
Rozdział 8. Memorandum Furbelowa

Część III. Wejście-wyjście dostosowane do ludzi
Rozdział 9. Małe języki
Rozdział 10. Projektowanie dokumentu
Rozdział 11. Wyjście graficzne
Rozdział 12. Sondaż sondaży

Część IV. Algorytmy
Rozdział 13. Przykład błyskotliwości
Rozdział 14. Narodziny numeryka
Rozdział 15. Wybór

Algorytmy, struktury danych i techniki programowania

Autor: Piotr Wróblewski
Wydawnictwo: Helion
Rok wydania: 2015
Ilość stron: 376
Gdzie kupić: w sprzedaży
Język: C++

Książka wprowadza do tematu projektowania i analizy algorytmów. Zawiera podstawy, które każdy programista powinien umieć. Zawiera tematykę najczęściej pomijaną przy innych książkach do nienumerycznego przetwarzania danych: wprowadzenie do sztucznej inteligencji, kodowanie i kompresja danych oraz algorytmy numeryczne.

Rozdziały:
Rozdział 1. Zanim wystartujemy
Rozdział 2. Rekurencja
Rozdział 3. Typy i struktury danych
Rozdział 4. Analiza złożoności algorytmów
Rozdział 5. Derekursywacja i optymalizacja algorytmów
Rozdział 6. Algorytmy sortowania
Rozdział 7. Algorytmy przeszukiwania
Rozdział 8. Przeszukiwanie tekstów
Rozdział 9. Zaawansowane techniki programowania
Rozdział 10. Elementy algorytmiki grafów
Rozdział 11. Algorytmy numeryczne
Rozdział 12. Czy komputery mogą myśleć?
Rozdział 13. Kodowanie i kompresja danych
Rozdział 14. Zadania różne

C++. Algorytmy i struktury danych

Autor: Adam Drozdek
Wydawnictwo: Helion
Rok wydania: 2004
Ilość stron: 616
Gdzie kupić: czasami dostępne na allegro
Język: C++

Książka omawia od podstaw algorytmy i struktury danych z wykorzystaniem języka C++. Czytelnik powinien potrafić pisać programy strukturalne w C++.

Rozdziały:
Rozdział 1. Programowanie obiektowe w C++
Rozdział 2. Analiza złożoności
Rozdział 3. Listy
Rozdział 4. Stosy i kolejki
Rozdział 5. Rekurencja
Rozdział 6. Drzewa binarne
Rozdział 7. Drzewa wielokierunkowe
Rozdział 8. Grafy
Rozdział 9. Sortowanie
Rozdział 10. Mieszanie
Rozdział 11. Kompresja danych
Rozdział 12. Zarządzanie pamięcią

Algorytmy i struktury danych

Autor: Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman
Wydawnictwo: Helion
Rok wydania: 2003
Ilość stron: 448
Gdzie kupić: allegro
Język: Pascal (pseudokod)

Klasyczna pozycja omawiająca podstawy projektowania i analiza algorytmów. Autorzy traktują tematykę od podstaw.

Rozdziały:
Rozdział 1. Projektowanie i analiza algorytmów
Rozdział 2. Podstawowe abstrakcyjne typy danych
Rozdział 3. Drzewa
Rozdział 4. Podstawowe operacje na zbiorach
Rozdział 5. Zaawansowane metody reprezentowania zbiorów
Rozdział 6. Grafy skierowane
Rozdział 7. Grafy nieskierowane
Rozdział 8. Sortowanie
Rozdział 9. Techniki analizy algorytmów
Rozdział 10. Techniki projektowania algorytmów
Rozdział 11. Struktury danych i algorytmy obróbki danych zewnętrznych
Rozdział 12. Zarządzanie pamięcią

Rzecz o istocie informatyki - Algorytmika

Autorzy: David Harel, Yishai Feldman
Wydawnictwo: WNT
Rok wydania: 2008
Ilość stron: 594
Gdzie kupić: w sprzedaży
Język: pseudokod

Książka ta różni się od reszty pozycji informatycznych. Bardziej można ją uznać za książkę popularnonaukową opowiadającą o informatyce ze szczególnym naciskiem na algorytmikę. Książkę może równie dobrze czytać zarówno osoba nieobeznania z informatyką jak i specjalista. Jest to doskonały wstęp do informatyki.

Rozdziały:

Część I. Wstęp

1. Wprowadzenie i przegląd historyczny
2. Algorytmy idane
3. Języki i paradygmaty programowania

Część II. Metody i analiza
4. Metody algorytmiczne
5. Poprawność algorytmów
6. Sprawność algorytmów

Część III. Ograniczenia i odporność
7. Nieefektywność i nierozwiązywalność
8. Nieobliczalność i nierozstrzygalność
9. Algorytmiczna uniwersalność i odporność

Część IV. Osłabianie reguł
10. Równoległość, współbieżność i modele alternatywne
11. Algorytmy probabilistyczne
12. Kryptografia i niezawodna interakcja

Część V. Szersze spojrzenie
13. Inżynieria oprogramowania
14. Systemy reaktywne
15. Algorytmika i inteligencja

Średniozaawansowani:

Literatura dla osób, które mają już pewne obeznanie z algorytmiką. Często wymagana jest znajomość matematyki wyższej na pewnym poziomie. Są to książki bardziej szczegółowe i trudniejsze od wyżej wymienionych.

Wprowadzenie do algorytmów

Autorzy: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Wydawnictwo: WNT (starsze wydania) / PWN (nowe wydanie)
Rok wydania: 1997 - 2012
Ilość stron: 1117/1196/1300
Gdzie kupić: dostępna w sprzedaży
Język: Pseudokod (przypominający C, C++, Javę i Pythona w nowym wydaniu, w starym podobny Pascala)

Jeśli szukasz książki, która dokładnie tłumaczy trudną sztukę projektowania i analizy algorytmów, to trafiłeś na dobry adres. Książka opisuje większość działów algorytmiki. Na początku wkraczasz w świat matematyki dyskretnej (uzupełnione w dodatku). Następnie poznajesz metody sortowania, struktury danych, zaawansowane techniki projektowania algorytmów, teorię grafów i wybrane zagadnienia, które przedstawiają kilka wybranych działów algorytmiki. Książka właściwie przez wszystkich polecana.

Rozdziały:

Część I. Podstawy
Wprowadzenie

1. Rola algorytmów w obliczeniach
2. Zaczynamy
3. Rzędy wielkości funkcji
4. Metoda „dziel i zwyciężaj”
5. Analiza probabilistyczna i algorytmy randomizowane

Część II. Sortowanie i statystyki pozycyjne
6. Heapsort - sortowanie przez kopcowanie
7. Quicksort - sortowanie szybkie
8. Sortowanie w czasie liniowym
9. Mediany i statystyki pozycyjne

Część III. Struktury danych
10. Elementarne struktury danych
11. Tablice z haszowaniem
12. Drzewa wyszukiwań binarnych
13. Drzewa czerwono-czarne
14. Wzbogacanie struktur danych

Część IV. Zaawansowanie metody konstruowania i analizowania algorytmów
15. Programowanie dynamiczne
16. Algorytmy zachłanne
17. Analiza kosztu zamortyzowanego

Część V. Złożone struktury danych
18. B-drzewa
19. Kopce Fibonacciego
20. Drzewa van Emde Boasa
21. Struktury danych dla zbiorów rozłącznych

Część VI. Algorytmy grafowe
22. Podstawowe algorytmy grafowe
23. Minimalne drzewa rozpinające
24. Najkrótsze ścieżki z jednym źródłem
25. Najkrótsze ścieżki między wszystkimi parami wierzchołków
26. Maksymalny przepływ

Część VII. Wybrane zagadnienia
27. Algorytmy wielowątkowe
28. Operacje na macierzach
29. Programowanie liniowe
30. Wielomiany i FFT
31. Algorytmy teorioliczbowe
32. Wyszukiwanie wzorca
33. Geometria obliczeniowa
34. NP- zupełność
35. Algorytmy aproksymacyjne

Część VIII. Dodatek: Podstawy matematyczne
Wprowadzenie
A. Sumy
B. Zbiory i nie tylko
C. Zliczanie i prawdopodobieństwo
D. Macierze

Algorytmy. Wydanie IV

Autorzy: Robert Sedgewick, Kevin Wayne
Wydawnictwo: Helion
Rok wydania: 2012
Ilość stron: 952
Gdzie kupić: dostępna w sprzedaży
Język: Java

Podręcznik do algorytmiki, który bywa porównywany z „Wprowadzeniem do algorytmów”. Wprowadza w podstawy i szerzej omawia działy: sortowanie, wyszukiwanie, teorię grafów i operacje na tekstach.

Rozdziały:

1. Podstawy
2. Sortowanie
3. Wyszukiwanie
4. Grafy
5. Łańcuchy znaków
6. Kontekst

Algorytmy i struktury danych

Autorzy: L. Banachowski, K. Diks, W. Rytter
Wydawnictwo: WNT
Rok wydania: 2006
Ilość stron: 290
Gdzie kupić: w sprzedaży
Język: Pascal (pseudokod)

Początkowo skrypt do przedmiotu algorytmy i struktury danych, który wkrótce przerodził się w książkę. Na początku mamy podstawy, następnie sortowanie, słowniki, struktury danych, algorytmy tekstowe, równoległe, grafowe i geometryczne. Czasami autorzy chcieli upchać za dużo rzeczy na małej ilości stron, przez co nie dostajemy wszystkiego podanego na tacy, lecz część opisów jest na wysokim poziomie. Polecana jako uzupełnienie „Wprowadzenia do algorytmów”.
Rozdziały:

1. Podstawowe zasady analizy algorytmów
2. Sortowanie
3. Słowniki
4. Złożone struktury danych dla zbiorów elementów
5. Algorytmy tekstowe
6. Algorytmy równoległe
7. Algorytmy grafowe
8. Algorytmy geometryczne

Projektowanie i analiza algorytmów / Projektowanie i analiza algorytmów komputerowych

Wydawnictwo: Helion/PWN
Rok wydania: 2003/1983
Ilość stron: 488/588
Gdzie kupić: allegro
Język: Pascal (pseudokod)

Klasyczna pozycja na temat algorytmiki. Omawia algorytmy i struktury danych z różnych działów m.in.: sortowanie, teoria grafów, operacje na macierzach, FFT czy teoria liczb.

Rozdziały:

1. Modele obliczania
2. Projektowanie efektywnych algorytmów
3. Sortowanie i statystyka pozycyjna
4. Struktury danych dla zadań operujących na zbiorach
5. Algorytmy na grafach
6. Mnożenie macierzy i pokrewne operacje
7. Szybkie przekształcenie Fouriera z zastosowaniami
8. Arytmetyka na liczbach całkowitych i wielomianach
9. Algorytmy dopasowania wzorców
10. Problemy NP-zupełne
11. Problemy niełatwe na podstawie dowodu
12. Ograniczenia dolne liczby operacji arytmetycznych

Algorytmy w C++

Wydawnictwo: RM
Autor: Robert Sedgewick
Rok wydania: 1999, 2003
Ilość stron: 634 (tom I), 472 (tom V)
Gdzie kupić: allegro (rzadko dostępna, należy raczej szukać w bibliotece, szczególnie tomu V)
Język: C++

Autor przedstawia algorytmy i prezentuje od razu praktyczną implementację w C++. Niestety na język polski został przetłumaczony tylko tom I i V. W tomie I można znaleźć podstawy algorytmiki, a w tomie V mnóstwo informacji o algorytmach grafowych.

Rozdziały:

Tom I
1 Podstawy
2 Dane strukturalne
3 Sortowanie
4 Wyszukiwanie

Tom V – Grafy
Rozdział 17. Rodzaje grafów i ich własności
Rozdział 18. Przeszukiwanie grafów
Rozdział 19. Grafy skierowane i dagi
Rozdział 20. Minimalne drzewa rozpinające
Rozdział 21. Najkrótsze ścieżki
Rozdział 22. Przepływ sieci

Algorytmika praktyczna. Nie tylko dla mistrzów

Wydawnictwo: PWN
Autor: Piotr Stańczyk
Rok wydania: 2009
Ilość stron: 312
Gdzie kupić: w sprzedaży
Język: C++

Książka ta jest inna niż wcześniej wymienione pozycje. Nie znajdziesz w niej analizy algorytmu. Znajdziesz za to opis i dokładną implementację w C++ algorytmów, które najczęściej występują na konkursach algorytmiczno-programistycznych. Wymagana jest znajomość C++ wraz z biblioteką STL. Autor omawia działy informatyki najczęściej występujące na konkursach i jednocześnie podaje literaturę, w której znajdziemy teoretyczny opis algorytmu. Praktyczne nastawienie do tematu miała również książka „Wyzwania programistyczne” która, niestety, jest niedostępna w sprzedaży, nie ma jej nawet na allegro.

Rozdziały:

1. Algorytmy grafowe
2. Geometria obliczeniowa na płaszczyźnie
3. Kombinatoryka
4. Teoria liczb
5. Struktury danych
6. Algorytmy tekstowe
7. Algebra liniowa
8. Elementy strategii podczas zawodów

Wyzwania programistyczne

Wydawnictwo: WSIP
Autor: Steven S. Skiena, Miguel A. Revilla
Rok wydania: 2004
Ilość stron: 352
Gdzie kupić: raczej nie do kupienia, jedynie można szukać w bibliotekach
Język: Java, C, C++, Pascal

Jest to książka, która również skupia się na przygotowaniach do konkursów informatycznych. Książka składa się z kilkunastu rozdziałów, dotyczących różnych działów algorytmiki, w tym: sortowania, teorii liczb, przeszukiwania grafów, algorytmów grafowych, przeszukiwania z nawrotami, programowania dynamicznego, geometrii obliczeniowej. Niestety obecnie nie do dostania – należy szukać w bibliotekach.

Algorytmy

Wydawnictwo: PWN
Autorzy: Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani
Rok wydania: 2011
Ilość stron: 360
Gdzie kupić: w sprzedaży
Język: pseudokod

Autorzy omawiają po kolei różne działy algorytmiki. Jako jedna z nielicznych zawiera wprowadzenie do algorytmów kwantowych.

Rozdziały:
0. Prolog

1. Algorytmy na liczbach
2. Algorytmy "dziel i zwyciężaj"
3. Dekompozycje grafów
4. Scieżki w grafach
5. Algorytmy zachłanne
6. Programowanie dynamiczne
7. Programowanie liniowe i redukcje
8. Problemy NP-zupełne
9. Jak radzić sobie z NP-zupełnością
10. Algorytmy kwantowe

Olimpiada informatyczna (niebieskie książeczki) I - XVIII

Wydawnictwo: Komitet Główny Olimpiady Informatycznej
Autorzy: Profesorowie i byli olimpijczycy
Rok wydania: 1994 - 2012
Gdzie kupić: część w sprzedaży, wszystkie do pobrania (na stronie olimpiady)
Język: pseudokod, Pascal, C, C++

Książeczki z olimpiady informatycznej zwane niebieskimi książeczkami zawierają informacje o przebiegu olimpiady, oraz – co najważniejsze – omówienie każdego zadania. Bardzo przydatne, ponieważ można się nauczyć jak w praktyce wykorzystać wiedzę algorytmiczną.

Zaawansowani:

Literatura dla osób, które mają już pewną wiedzę z różnych działów algorytmiki. i szukają bardziej specjalistycznych opracowań.

Sztuka programowania

Wydawnictwo: WNT
Autorzy: Donald E. Knuth
Rok wydania: 2002 - 2008
Gdzie kupić: allegro (czasami)
Język: asembler

Dzieło Donalda Knutha jest uznawane za jedną z najlepszych książek informatycznych w historii. Jest to dzieło napisane wybitnie dla specjalistów. Każdy algorytm opisany w książce został dokładnie przeanalizowany. Polecam każdemu kto ma już doświadczenie w projektowaniu i analiza algorytmów i chce pogłębić swoją wiedzę.

Rozdziały:

Tom I – Algorytmy podstawowe
Rozdział 1. Pojęcia podstawowe
Rozdział 2. Struktury danych

Tom 1 zeszyt 1 MMIX - Komputer na nowe tysiąclecie

Tom II – Algorytmy seminumeryczne
Rozdział 3. Liczby losowe
Rozdział 4. Arytmetyka

Tom III – Sortowanie i wyszukiwanie
Rozdział 5 - Sortowanie
Rozdział 6 – Wyszukiwanie

Tom IV zeszyt 2 - Generowanie wszystkich krotek i permutacji
Rozdział 7 – Wyszukiwanie kombinatoryczne (tylko część druga rozdziału)

Kombinatoryka dla programistów

Wydawnictwo: WNT
Autor: Witold Lipski
Rok wydania: 2003
Ilość stron: 276
Gdzie kupić: w sprzedaży
Język: Pascal, C++

W książce przedstawiono kombinatorykę, która jest przydatna informatykom. Każdy algorytm został opisany, przeanalizowany i zapisany w języku Pascal (tylko w ostatnim rozdziale są pseudokody). Dodatkowo w nowym wydaniu na końcu można znaleźć kod algorytmów w C++ napisany przez znanego Polskiego programistę Tomasza Czajkę. Nie jest to lektura łatwa, ale przydatna dla każdego kto chce lepiej poznać algorytmy kombinatoryczne.

1. Wprowadzenie do kombinatoryki
2. Algorytmy grafowe
3. Znajdowanie najkrótszych dróg w grafie
4. Przepływy w sieciach i zagadnienia pokrewne
5. Matroidy

Geometria obliczeniowa algorytmy i zastosowania

Wydawnictwo: WNT
Autorzy: M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf
Rok wydania: 2007
Ilość stron: 432
Gdzie kupić: w sprzedaży
Język: Pseudokod

Geometria obliczeniowa znajduje w dzisiejszych czasach szerokie zastosowanie w wielu dziedzinach nauki. Autorzy przybliżają geometrię obliczeniową wraz z zastosowaniami. Wymagana jest podstawowa wiedza z algorytmów i struktur danych, ale nie jest wymagana jakaś szczególna wiedza z geometrii.

Rozdziały:

1. Geometria obliczeniowa
2. Przecinanie się odcinków Nakładanie map tematycznych
3. Triangulacja wielokąta. Ochrona galerii sztuki
4. Programowanie liniowe Produkcja z użyciem form odlewniczych
5. Przeszukiwanie obszarów ortogonalnych Zadawanie pytań bazie danych
6. Lokalizacja punktu. Wiedza o tym, gdzie się znajdujemy
7. Diagramy Yoronoi. Problem urzędu pocztowego
8. Układy i dualność. Superpróbkowanie w śledzeniu promieni
9. Triangulacje Delaunaya. Interpolacja wysokości
10. Więcej geometrycznych struktur danych. Okienkowanie
11. Otoczka wypukła. Pomieszanie sprawy
12. Binarne podziały przestrzeni. Algorytm malarza
13. Planowanie ruchu robota. Docieranie tam, gdzie chcemy być
14. Drzewa ćwiartek. Tworzenie niejednolitych siatek
15. Grafy widzialności. Znajdywanie najkrótszej drogi
16. Przeszukiwanie obszarów sympleksowych Okienkowanie jeszcze raz

Geometria obliczeniowa. Wprowadzenie

Wydawnictwo: Helion
Autorzy: M Franco P. Preparata, Michael Ian Shamos
Rok wydania: 2003
Ilość stron: 392
Gdzie kupić: allegro (rzadko dostępne, lepiej poszukać w bibliotekach)
Język: Pascal

Jest to książka szczegółowo wprowadzająca w tematykę geometrii obliczeniowej. Jest to rozwinięcie doktoratu jednego z autorów.

Rozdziały:

1. Wprowadzenie
2. Przeszukiwanie geometryczne
3. Otoczki wypukłe: algorytmy podstawowe
4. Otoczki wypukłe: rozszerzenia i zastosowanie
5. Bliskość: algorytmy podstawowe
6. Bliskość: odmiany i uogólnienia
7. Przecięcia
8. Geometria prostokątów

Algorytmy aproksymacyjne

Wydawnictwo: WNT
Autor: Vijay V. Vazarini
Rok wydania: 2005
Ilość stron: 384
Gdzie kupić: w sprzedaży
Język: Pseudokod

Problemy NP-zupełne od wielu lat dręczą informatyków. Algorytmy wykładnicze są zbyt wolne, aby używać je dla sensownej liczby danych. W takim przypadku pozostaje nam zaprojektowanie algorytmu wielomianowego, który by dawał przybliżone rozwiązanie problemu (ale często wystarczające), czyli algorytmu aproksymacyjnego. O tym właśnie traktuje ta książka. Nie jest to lektura łatwa, ale w sam raz dla osoby, która umie już sporo algorytmiki i matematyki dyskretnej i chce pogłębić wiedzę na temat algorytmów aproksymacyjnych i klasy problemów NP-zupełnych.

Rozdziały:

Rozdział 1. Wstęp

Część I. Algorytmy kombinatoryczne
Rozdział 2. Pokrycie zbioru
Rozdział 3. Drzewo Steinera i problem komiwojażera
Rozdział 4. Przekrój wielokrotny i k-przekrój
Rozdział 5. Problem k-centrum
Rozdział 6. Rozcyklający zbiór wierzchołków
Rozdział 7. Najkrótsze nadsłowo
Rozdział 8. Problem plecakowy
Rozdział 9. Pakowanie
Rozdział 10. Najkrótsze uszeregowanie
Rozdział 11. Euklidesowy problem komiwojażera

Część II. Algorytmy oparte na programowaniu liniowym
Rozdział 12. Wprowadzenie do dualności programowania liniowego
Rozdział 13. Dopasowanie dualne dla problemu pokrycia zbioru
Rozdział 14. Zastosowanie zaokrąglania do problemu pokrycia zbioru
Rozdział 15. Schemat prymalno—dualny dla problemu pokrycia zbioru
Rozdział 16. Maksymalna spełnialność
Rozdział 17. Szeregowanie zadań na niezależnych maszynach
Rozdział 18. Multiprzekrój i całkowitoliczbowy przepływ wielotowarowy w drzewach
Rozdział 19. Przekrój wielokrotny
Rozdział 20. Multiprzekrój w dowolnych grafach
Rozdział 21. Najbardziej rozrzedzony przekrój
Rozdział 22. Las Steinera
Rozdział 23. Sieć Steinera
Rozdział 24. Problem lokalizacji
Rozdział 25. Problem k-mediany
Rozdział 26. Programowanie półokreślone

Część III. Inne zagadnienia
Rozdział 27. Najkrótszy wektor
Rozdział 28. Zliczanie
Rozdział 29. Trudność aproksymacji
Rozdział 30. Problemy otwarte

Rozdział A. Przegląd teorii złożoności obliczeniowej
Rozdział B. Podstawowe fakty z teorii prawdopodobieństwa

Matematyka używana przy projektowaniu i analizie algorytmów:

Pierwsze algorytmy powstały jeszcze zanim pojawiły się pierwsze komputery – były przydatne do obliczeń matematycznych. Nikt zajmujący się algorytmiką nie może się obyć bez podstawowego aparatu matematycznego.

Matematyka konkretna

Wydawnictwo: PWN
Autorzy: Ronald L. Graham, Donald E. Knuth, Oren PatashnikRok wydania: 2008
Ilość stron: 720
Rok wydania: 2008
Gdzie kupić: w sprzedaży

Jest to książka, w której autorzy starają się nauczyć czytelnika umiejętności rachunkowych. Po przeczytaniu tej książki nikomu nie powinna być straszna nawet największa suma. W dodatku autorzy robią to z humorem – sądzą, że matematyka nie musi być wcale szalenie poważną dziedziną i można się przy niej dobrze bawić.

Rozdziały:

1. Problemy rekurencyjne
2. Sumy
3. Funkcje całkowitoliczbowe
4. Teoria liczb
5. Współczynniki dwumianowe
6. Liczby szczególne
7. Funkcje tworzące
8. Prawdopodobieństwo dyskretne
9. Asymptotyka

Matematyka dyskretna

Wydawnictwo: PWN
Autorzy: Ronald Kennweth A. Ross, Charles R.B. Wright
Ilość stron: 900
Rok wydania: 2008
Gdzie kupić: w sprzedaży

Książka przedstawia całą podstawową matematykę przydatną informatykom. Na początku przedstawione są rozdziały podstawowe, dzięki czemu osoba o słabszym przygotowaniu matematycznym będzie mogła łatwiej rozpocząć studiowanie tej książki.

Rozdziały:

1. Zbiory, ciągi i funkcje
2. Elementy logiki
3. Relacje
4. Indukcja i rekurencja
5. Zliczanie
6. Wprowadzenie do grafów i drzew
7. Rekurencja, drzewa i algorytmy
8. Grafy skierowane
9. Rachunek prawdopodobieństwa
10. Algebry Boole’a
11. Więcej o relacjach
12. Struktury algebraiczne
13. Rachunek predykatów i zbiory nieskończone

Wprowadzenie do teorii grafów

Wydawnictwo: PWN
Autorzy: Robin J. Wilson
Ilość stron: 224
Rok wydania: 2007
Gdzie kupić: w sprzedaży

Jest to książka łagodnie wprowadzająca w problematykę teorii grafów. Duża ilość przykładów i rysunków pozwala na stosunkowo łatwe przyswojenie materiału.

Rozdziały:

1. Wprowadzenie
2. Definicje i przykłady
3. Drogi i cykle
4. Drzewa
5. Planarność
6. Kolorowanie grafów
7. Digrafy
8. Skojarzenia, małżeństwa i twierdzenie Mengera
9. Matroidy

Aspekty kombinatoryki

Wydawnictwo: WNT
Autorzy: Victor Bryant
Ilość stron: 290
Rok wydania: 2007
Gdzie kupić: allegro

Książka omawia kombinatorykę. Zawiera bardzo dużo informacji o teorii grafów. Oprócz kombinatoryki zawiera również inne tematy z matematyki dyskretnej.

Rozdziały:

1. Współczynniki dwumianowe
2. Ile jest drzew?
3. Twierdzenie o małżeństwach
4. Trzy podstawowe zasady
5. Kwadraty łacińskie
6. Pierwsze twierdzenie teorii grafów
7. Kolorowe krawędzi
8. Haremy i turnieje
9. Twierdzenia minimaksowe
10. Rekurencja
11. Kolorowanie wierzchołków
12. Wielomiany szachowe
13. Grafy planarne
14. Kolorowanie map
15. Konfiguracje i kody
16. Teoria Ramseya

Wykłady z kombinatoryki

Wydawnictwo: WNT
Autorzy: Zbigniew Palka, Andrzej Ruciński
Ilość stron: 199
Rok wydania: 2007
Gdzie kupić: w sprzedaży

Pozycja przedstawia zagadnienia matematyki dyskretnej kładąc szczególny nacisk na kombinatorykę.

Rozdziały:

1. Czym zajmuje się kombinatoryka?
2. Prawa i metody przeliczania
3. Schematy wyboru
4. Ciągi binarne i współczynniki dwumianowe
5. Równania rekurencyjne i funkcje tworzące
6. Zasada włączania i wyłączania
7. Wybory z ograniczeniami
8. Podziały
9. Przeliczanie grafów oznaczonych
   10.Przeliczanie struktur nieoznaczonych