Przekazywana do rąk czytelników książka jest trzecim wydaniem podręcznika akademickiego opublikowanego nakładem Wydawnictwa Politechniki Gdańskiej pod tym samym tytułem. Od momentu drugiego wydania w roku 2002 wystąpiły nowe fakty w dziedzinie dużych liczb pierwszych i sposobów stymulowania nowych odkryć w zakresie teorii algorytmów i teorii liczb. Stąd zrodziła się potrzeba kolejnego wydania, uzupełnionego o najnowsze informacje z tych dziedzin. Ponadto, pomiędzy drugim i trzecim wydaniem ukazały się dwa inne podręczniki w tej serii na temat algorytmów i struktur danych i fakt ten musiał być odnotowany w niniejszej publikacji.
Oddawany do rąk czytelników podręcznik jest przeznaczony dla osób interesujących się podstawami informatyki, w tym przede wszystkim dla studentów kierunku Informatyka na Wydziale ETI Politechniki Gdańskiej. Formalnie rzecz biorąc, jego treść pokrywa pierwszą część wykładu z przedmiotu "Podstawy teorii obliczeń", tj. algorytmy i problemy wielomianowe, ale stanowi też miejscami rozszerzenie programu tego przedmiotu, który jest prowadzony na II roku kierunku Informatyka. W tym miejscu odnotujmy, że drugą część wykładu doskonale pokrywa książka K. Giary ?Złożoność obliczeniowa algorytmów w zadaniach" [4] oraz poprzedni skrypt autora [6]. W szczególności niniejszy podręcznik może służyć jako wprowadzenie do wykładu ?Struktury danych". Jego fragmenty mogą być także wykorzystane w nauczaniu przedmiotu ?Matematyka dyskretna". Sądzę, że książka może ponadto zainteresować studentów kierunku Informatyka na Wydziale Matematyki, Fizyki i Informatyki Uniwersytetu Gdańskiego, oraz studentów kierunków pokrewnych, np. Matematyka Stosowana.
Spis treści:
Przedmowa
1. WPROWADZENIE
1.1. Problemy algorytmiczne
1.2. Język PseudoPascal
1.3. Podstawy matematyczne
1.3.1. Logarytmy i zaokrąglenia całkowite
1.3.2. Sumy szeregów
1.4. Symbole oszacowań asymptorycznych
1.5. Równania rekurencyjne niejednorodne
1.5.1. Równania typu "dziel i rządź"
1.5.2. Równania typu "jeden krok w tył"
Zadania
2. PODSTAWY ANALIZY ALGORYTMÓW
2.1. Wstęp
2.2. Poprawność algorytmów
2.3. Złożoność czasowa algorytmów
2.3.1. Operacje podstawowe
2.3.2. Rozmiar danych
2.3.3. Pesymistyczna złożoność obliczeniowa
2.3.4. Oczekiwana złożoność obliczeniowa
2.4. Złożoność pamięciowa
2.5. Optymalność
2.6. Dokładność numeryczna algorytmów
2.6.1. Zadania źle uwarunkowane
2.6.2. Stabilność numeryczna
2.7. Prostota algorytmów
2.8. Wrażliwość algorytmów
2.9. Programowanie a złożoność obliczeniowa
2.9.1. Rząd złożoności obliczeniowej
2.9.2. Stała proporcjonalności złożoności obliczeniowej
2.9.3. Imperatyw złożoności obliczeniowej i odstępstwa.
Zadania
3. PODSTAWOWE STRUKTURY DANYCH
3.1. Tablice
3.2. Listy
3.3. Zbiory
3.4. Grafy
3.4.1. Macierz sąsiedztwa wierzchołków
3.4.2. Listy sąsiedztwa wierzchołków
3.4.3. Pęki wyjściowe
Zadania
SŁOWNIK POLSKO-ANGIELSKI
LITERATURA
