57415 ScanImage021 (4)

1.5. ZESTAWIENIE ZAGADNIEŃ

i

Zadania

1.25.    Załóżmy, że dysponujemy dwoma komputerami, nowym i starym, przy czym nowy jest 10 razy szybszy od starego. Załóżmy także, że używamy zrównoważonego algorytmu szybkiego scalania. Ile więcej czasu zajmie nowemu komputerowi przetwarzanie dziesięciokrotnie większej liczby połączeń niż staremu pierwotnej ich liczby?

1.26.    Wykonaj zadanie 1.25 dla przypadku, w którymi używany algorytm wymagań' instrukcji.

1.5. Zestawienie zagadnień

Na ten podrozdział składają się krótkie opisy większych części składowych tej książki. Zawarto w nim omówienie poruszanych tematów oraz informacje pozwalające zorientować się w ogólnej tematyce przedstawionego materiału. W podręczniku chcemy omówić tyje podstawowych algorytmów komputerowych, ile to tylko możliwe. Niektóre dziedziny, o których piszemy, należą, do rudymentów informatyki - tymi zajmujemy się dokładniej, ponieważ, stanowią okazję do bliższego poznania podstawowych algorytmów o szerokim spektrum zastosowań. Inne opisywane przez nas algorytmy pochodzą z zaawansowanych obszarów badań informatycznych i dziedzin pokrewnych, takich jak analiza numeryczna czy badania operacyjne - poruszane przez nas zagadnienia należy¹ traktować jako wprowadzenia do tych dziedzin wiedzy i zachętę do zajmowania się nimi w formie analizy' podstawowych metod.

Pierwsze cztery części tej książki, które zostały zawarte w tym tomie¹, dotyczą najbardziej rozpowszechnionych algorytmów- i struktur danych. Zaw-ierają one pierwszy poziom abstrakcji dla szerokiego spektrum ważnych fundamentalnych algorytmów' oraz liczne wskazówki dla ich zrozumienia. Omaw-iane przez nas algorytmy są wynikiem dziesiątek lat badań naukowych i nadal odgrywają istotną rolę w stale rozszerzającym się obszarze informatyki stosowanej.

Część 1 („Podstawy”) zawiera omówuenic podstawowych zasad i metod używanych do implementacji, analizy i porów-nyw-ania algorytmów. Materiał z rozdziału 1 stanowi zachętę do badania technik konstrukcji i analizy' algorytmów. W rozdziale 2 rozważamy podstawowe metody uzyskiwania kwantytatywnych informacji o wydajności algorytmu.

Część 2 (pt. „Struktury danych”) to prezentacja kolejnych algorytmów'. Wypracujemy tu wnikliwe zrozumienie metod reprezentacji danych na potrzeby pozostałej części książki. Zaczniemy od wprowadzenia (w rozdziale 3) w podstawowe konkretne struktury danych, czyli tablice, listy połączone i łańcuchy znaków'. W rozdziale 5 zajmiemy się rekurencyjnymi programami i strukturami danych, a w- szczególności drzewami i algorytmami do ich manipulacji. W rozdziale 4 omówimy podstawowe typy abstrakcyjne, a wńęc stosy i kolejki, oraz implementacje wykorzystujące te elementarne struktury.

Część 3 (pt, „Algorytmy sortowania”) zaw-iera opis metod porządkow-ania plików^r - algorytmów o fundamentalnym znaczeniu dla całej informatyki. Rozpatrujemy dość dokładnie różne typy algorytmów', w tym sortowanie Shella, sortowanie szybkie (ąuicksort), sortowanie przez scalanie (mergesort), sortow-anic kopcowe (heapsort) i sortowanie pozycy jne. Przedstawimy algorytmy dla różnych problemów pokrewnych, między innymi dla problemów kolejek

1

Por. przyp. 2zcs. V.

23%>«