ScanImage022

WPROWADZENIE

, Ż *****^imi *** ^ ⁸⁸⁸¹ '***

priorytetowych, .selekcji i scalania. Wiele z nich zostanie wykorzystanych w innych algorytmach w dalszej części lej książki.

Część 4 (pt „Algorytmy wyszukiwania”) dotyczy metody wyszukiwania konkretnych danych w' dużych ich zbiorach. Zagadnienia wyszukiwania należą również do tych o fundamentalnym znaczeniu. Omawiamy podstawowe i zaawansowane metody przeszukiwania drzew i transformacji kluczy cyfrowych, w tym binarnych drzew poszukiwań, drzew zrównoważonych, mieszania, cyfrowych drzew poszukiwań oraz metod nadających się do zastosowania na ogromnych plikach. Opisujemy zależności między tymi metodami, porównujemy parametry wydajnościowe i podobieństwa do metod sortowania.

Części od 5 do 8, które zostały umieszczone w osobnym tomie, dotyczą zaawansowanych zastosowań opisanych tutaj algorytmów w różnorakich aplikacjach. Zawierają one drugi poziom abstrakcji typowy dla pewnej liczby ważnych obszarów zastosowań. Prezentowany tam materiał zawiera również bardziej wnikliwe omówienie technik konstrukcji i analizy algorytmów. Wiele problemów, które poruszamy, stanowi przedmiot nieustających badań naukowych.

Część Sjest poświęcona algorytmom do przetwarzania łańcuchów znaków. Opisuje ona szereg metod przetwarzania (długich) sekwencji znaków. Wyszukiwanie ciągów znaków prowadzi do dopasowywania wzorców', które z kolei wiedzie do analizy syntaktyczncj. Omawiamy również techniki kompresji plików'. Znów-prezentując kilka elementarnych problemów-, zapewniamy wyprowadzenie do tematów bardziej zaawansowanych.

Część 6 dotyczy algorytmów geometrycznych, czyli metod rozwiązywania zadań, w których występują punkty, proste, odcinki i inne figury geometryczne. Badamy algorytmy wyznaczające otoczkę wypukłą dla zbioru punktów, wyszukujące przecięcia figur geometrycznych, znajdujące najbliżej położone punkt)' i realizujące wyszukiwanie wielowymiarowe. Wiele z tych metod stanowi harmonijne uzupełnienie bardziej elementarnych metod sortowania i wyszukiwania.

Część 7 omawia algorytmy grafowe, wykorzystywane do rozwiązywania sporej puli zadań z bardzo różnych dziedzin życia. Wyprowadzamy ogólną strategię przechodzenia przez graf i pokazujemy, jak ją zastosować do podstawowych problemów' spójności, w tym do problemu wyznaczania najkrótszej ścieżki, problemu minimalnego drzewa rozpinającego, przepływu sieciowego i problemu skojarzeń. Zunifikowane traktowanie tych algorytmów pokazuje, że wszystkie one wykorzystują tę samą procedurę - jej kształt zależy od abstrakcyjnego typu danych, na jakim oparto kolejkę priorytetowy.

Część 8 zawiera informacje o zagadnieniach zaawansowanych. Jej celem jest powiązanie materiału tej książki z innymi zaawansowanymi dziedzinami badan. Zaczynamy od głównych rozwiązań w^f zakresie konstrukcji i analizy algorytmów', w rym od zasady „dziel i rządź”, programowania dynamicznego, randomizacji i amortyzacji. Analizujemy programowanie liniowe, szybką transformację Fouriera, NP-zupełność i inne zaawansowane tematy - wszystko z punktu widzenia nowicjusza w tej dziedzinie. Prezentując proste przykłady, staramy się pozyskać zainteresowanie niezwykle interesującymi zaawansowanymi dziedzinami badań współczesnej informatyki.

24