Teoretyczne podstawy informatyki

TREŚCI NAUCZANIA

Podstawy teorii informacji: jednostki pomiaru ilości informacji, podstawowe równanie teorii informacji. Kodowanie:własności kodów i metody kodowania. Systemy liczbowe i konwersja liczb. Gramatyki i języki formalne: rodzaje gramatyk generacyjnych a klasyfikacja języków formalnych. Teoria automatów: rodzaje automatów i ich możliwości, automaty a translatory. Odwrotna Notacja Polska. Modele maszyn cyfrowych: maszyna Turinga i Przykładowa Maszyna Cyfrowa von Neumanna.

Elementy algorytmiki: struktura algorytmów, poprawność częściowa i całkowita algorytmów oraz metody ich dowodzenia, złożoność czasowa i pamięciowa algorytmów. Optymalizacja algorytmów. Problemy obliczalności i rozstrzygalności algorytmów. Teza Churcha-Turinga i jej znaczenie.

LITERATURA

1. N. Abramson, Teoria informacji i kodowania, Warszawa 1969.
2. J. E. Hopcroft, J. D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, Warszawa 1994.
3. D. Harel, Rzecz o istocie informatyki - algorytmika, Warszawa 1992.
4. M. Cichy, J. Nomańczuk, S. Szpakowicz, Zbiór zadań z propedeutki informatyki, PWN, Warszawa 1986.
5. W. M. Turski, Propedeutyka informatyki, PWN, Warzsawa 1989.
6. R. Tadeusiewicz, P. Moszner, A. Szydełko, Teoretyczne podstawy informatyki, Wydawnictwo Naukowe AP, Kraków, 1999.