- Wprowadzenie do algorytmiki -- dziedziny zajmującej się
konstrukcją i analizą algorytmów; zaznajomienie z podstawowymi
algorytmami informatycznymi -- specyfikacja problemu, algorytm
rozwiązujący i jego zgodność ze specyfikacją.
- Opanowanie umiejętności samodzielnego i zespołowego rozwiązywania
typowych problemów za pomocą komputera, poprzez korzystanie z
podstawowych technik algorytmicznych (tj. wybór, iteracja, rekurencja),
struktur danych i metod programowania strukturalnego (w tym podprogramy
i ich parametry, moduły).
- Omówienie na przykładzie analizy algorytmów w zakresie ich
poprawności, skończoności i złożoności. Przedstawienie praktycznej
efektywności algorytmów.
- Przedstawienie sposobów reprezentowania algorytmów i
komputerowych demonstracji ich działania.
- Zapoznanie się z wybranymi metodami programowania (programowanie
funkcjonalne i obiektowe).
- Pascal -- jako forma zapisu algorytmu.
| SEMESTR 4 | TREŚCI NAUCZANIA |
- Sytuacja problemowa (zadanie algorytmiczne), specyfikacja
problemu i algorytm jego rozwiązania.
- Zalgorytmizowana rzeczywistość -- przegląd typowych algorytmów z
różnych dziedzin. Klasyczne algorytmy informatyczne.
- Sposoby zapisywania i reprezentowania algorytmów: listy kroków,
metody graficzne (schematy blokowe), pseudokody.
- Wykorzystanie programów edukacyjnych do demonstracji metod
projektowania i działania algorytmów.
- Podstawowe techniki algorytmiczne, ich realizacje oraz użycie w
rozwiązywaniu problemów klasycznych.
- Podstawowe algorytmy obliczeń matematycznych (algorytmy
numeryczne): działania na wielomianach, znajdowanie zer funkcji.
Kryteria oceny algorytmów numerycznych: błędy zaokrągleń, stabilność.
- Kryteria oceny poprawności i jakości (efektywności) rozwiązań
(algorytmów), porównywanie efektywności różnych rozwiązań tego samego
problemu na przykładzie problemu sortowania.
- Korzystanie z istniejącego oprogramowania (również użytkowego).
- Przykłady analizy algorytmów i programów: proste dowody
poprawności; skończoność algorytmów, złożoność (czasowa, pamięciowa)
algorytmów i problemów.
- Składnia programu w języku Pascal. Konstrukcje sterujące języka
(instrukcje przypisania, złożona, pusta, warunkowa, iteracyjna).
Definicje procedur i funkcji. Rodzaje parametrów i sposoby ich
przekazywania.
- Typy danych w języku Pascal: proste i strukturalne (tablice,
rekordy, zbiory, pliki). Deklaracje zmiennych i definicje stałych.
- Deklaracja użycia modułów w programie, definiowanie modułów
niestandardowych.
- Podstawowe idee programowania strukturalnego, modularnego i
obiektowego.
- Elementy grafiki w języku Turbo Pascal.
Ćwiczenia do wykładu odbywają się w pracowni komputerowej.
- A. V. Aho, J. E. Hopcroft, J. D. Ullman, Projektowanie i
analiza algorytmów komputerowych, PWN, Warszawa 1983.
- L. Banachowski, A. Kreczmar, Elementy analizy
algorytmów, WN-T, Warszawa 1992.
- D. Harel, Rzecz o istocie informatyki. Algorytmika, WN-T,
Warszawa 1992.
- S. Kowalski, A.W. Mostowski, Teoria automatów i
lingwistyka matematyczna, PWN, Warszawa 1979.
- A. Marciniak, Podstawowy system i język Turbo
Pascal, PWN, Warszawa 1989.
- M. M. Sysło, Algorytmy, WSiP, Warszawa 1997.
Instytut Matematyki Akademii
Pedagogicznej w Krakowie,
15.01.2002
