Algorytmy i struktury danych (MOBI) Wrocław

Jądrem informatyki jest algorytmika, a najważniejszym elementem procesu tworzenia dobrego programu komputerowego jest właściwy dobór algorytmów i struktur danych szczególnie pod kątem ich wydajności. Algorytmy i struktury danych są tematem jednego z podstawowych przedmiotów wykładanych na każdych studiach informatycznych. Książka została sprawdzona dydaktyczne na zajęciach prowadzonych ze studentami informatyki Uniwersytetu Warszawskiego, jak też wielu innych uczelni informatycznych w kraju. Informacja o autorze/ redaktorze: Autorzy są informatykami o uznanym w świecie dorobku naukowym, edukacyjnym i popularyzatorskim. W latach osiemdziesiątych XX wieku tworzyli podwaliny algorytmiki w Uniwersytecie Warszawskim. Mają na swoim koncie wiele znakomitych prac algorytmicznych opublikowanych w najlepszych wydawnictwach naukowych poświęconych informatyce teoretycznej. Spis treści: Okładka Strona tytułowa Strona redakcyjna Spis treści Przedmowa do nowego wydania Przedmowa do pierwszego wydania 1. Podstawowe zasady analizy algorytmów 1.1. Złożoność obliczeniowa 1.2. Równania rekurencyjne 1.3. Funkcje tworzące 1.4. Poprawność semantyczna 1.5. Podstawowe struktury danych 1.5.1. Lista 1.5.2. Zbiór 1.5.3. Graf 1.5.4. Notacja funkcyjna dla atrybutów obiektów 1.5.5. Drzewo 1.6. Eliminacja rekursji 1.7. Koszt zamortyzowany operacji w strukturze danych 1.8. Metody układania algorytmów 1.8.1. Metoda dziel i zwyciężaj 1.8.2. Programowanie dynamiczne 1.8.3. Metoda zachłanna 1.8.4. Inne metody Zadania 2. Sortowanie 2.1. Selectionsort sortowanie przez selekcję 2.2. Insertionsort sortowanie przez wstawianie 2.3. Quicksort sortowanie szybkie 2.4. Dolne ograniczenie na złożoność problemu sortowania 2.5. Sortowanie pozycyjne 2.6. Kolejki priorytetowe i algorytm heapsort 2.7. Drzewa turniejowe i zadania selekcji 2.8. Szybkie algorytmy wyznaczania k-tego największego elementu w ciągu 2.9. Scalanie ciągów uporządkowanych 2.10. Sortowanie zewnętrzne 2.10.1. Scalanie wielofazowe z 4 plikami 2.10.2. Scalanie wielofazowe z 3 plikami Zadania 3. Słowniki 3.1. Implementacja listowa nieuporządkowana 3.2. Implementacja listowa uporządkowana 3.3. Drzewa poszukiwań binarnych 3.3.1. Drzewa AVL 3.3.2. Samoorganizujące się drzewa BST 3.4. Mieszanie 3.4.1. Wybór funkcji mieszającej 3.4.2. Struktury danych stosowane do rozwiązywania problemu kolizji 3.5. Wyszukiwanie pozycyjne 3.5.1. Drzewa RST 3.5.2. Drzewa TRIE 3.5.3. Drzewa PATRICIA 3.6. Wyszukiwanie zewnętrzne 3.6.1. Pliki nieuporządkowane 3.6.2. Pliki z funkcją mieszającą 3.6.3. Sekwencyjne pliki indeksowane 3.6.4. B-drzewo jako wielopoziomowy indeks rzadki 3.6.5. B-drzewo jako wielopoziomowy indeks gęsty Zadania 4. Złożone struktury danych dla zbiorów elementów 4.1. Problem sumowania zbiorów rozłącznych 4.1.1. Implementacja listowa 4.1.2. Implementacja drzewowa 4.2. Złączalne kolejki priorytetowe Zadania 5. Algorytmy tekstowe 5.1. Problem wyszukiwania wzorca 5.1.1. Algorytm N (naiwny) 5.1.2. Algorytm KMP (Knutha-Morrisa-Pratta) 5.1.3. Algorytm liniowy dla problemu wyszukiwania wzorca dwuwymiarowego, czyli algorytm Bakera 5.1.4. Algorytm GS (wersja algorytmu Galila-Seiferasa dla pewnej klasy wzorców) 5.1.5. Algorytm KMR (Karpa-Millera-Rosenberga) 5.1.6. Algorytm KR (Karpa-Rabina) 5.1.7. Algorytm BM (Boyera-Moorea) 5.1.8. Algorytm FP (Fishera-Patersona) 5.2. Drzewa sufiksowe i grafy podsłów 5.2.1. Niezwarta reprezentacja drzewa sufiksowego 5.2.2. Tworzenie drzewa sufiksowego 5.2.3. Tworzenie grafu podsłów 5.3. Inne algorytmy tekstowe 5.3.1. Obliczanie najdłuższego wspólnego podsłowa 5.3.2. Obliczanie najdłuższego wspólnego podciągu 5.3.3. Wyszukiwanie słów podwójnych 5.3.4. Wyszukiwanie słów symetrycznych 5.3.5. Równoważność cykliczna 5.3.6. Algorytm Huffmana 5.3.7. Obliczanie leksykograficznie maksymalnego sufiksu 5.3.8. Jednoznaczne kodowanie 5.3.9. Liczenie liczby podsłów Zadania 6. Algorytmy równoległe 6.1. Równoległe obliczanie wyrażeń i prostych programów sekwencyjnych 6.2. Sortowanie równoległe Zadania 7. Algorytmy grafowe 7.1. Spójne składowe 7.2. Dwuspójne składowe 7.3. Silnie spójne składowe i silna orientacja 7.4. Cykle Eulera 7.5. 5-kolorowanie grafów planarnych 7.6. Najkrótsze ścieżki i minimalne drzewo rozpinające Zadania 8. Algorytmy geometryczne 8.1. Elementarne algorytmy geometryczne 8.2. Problem przynależności 8.3. Wypukła otoczka 8.4. Metoda zamiatania 8.4.1. Najmniej odległa para punktów 8.4.2. Pary przecinających się odcinków Zadania Bibliografia Przypisy