Nastepny dokument:	Wstęp do programowania
Nadrzędny dokument:	PRZEDMIOTY SPECJALNOŚCIOWE (DLA SPECJALNOŚCI MATEMATYKA Z INFORMATYKĄ)
Poprzedni dokument:	Systemy operacyjne

Teoretyczne podstawy informatyki

CELE NAUCZANIA

Nauczanie informatyki polega zazwyczaj na ćwiczeniu umiejętności obsługi komputera, programów użytkowych itp. Tymczasem ten przedmiot ma ukazać studentom teoretyczne podstawy informatyki. Teoria informatyki jest obecnie in statu nascendi. Mimo braku jednolitej teorii w rozumieniu dyscyplin ścisłych takich jak matematyka czy poszczególne dziedziny fizyki można się jednak pokusić o przedstawienie elementów teorii informatyki w jej poszczególnych aspektach. Temu ma służyć niniejszy wykład.

SEMESTR 3

TREŚCI NAUCZANIA

Wykłady

Podstawy teorii informacji: jednostki pomiaru ilości informacji, podstawowe równanie teorii informacji. Kodowanie: własności kodów i metody kodowania. Języki i gramatyki formalne: rodzaje gramatyk generacyjnych a klasyfikacja języków formalnych. Teoria automatów: rodzaje automatów i ich możliwości, automaty a translatory. Modele maszyn cyfrowych: maszyna Turinga, 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.

Ćwiczenia konwersatoryjne

Wyrabianie umiejętności praktycznych z zakresu tematyki objętej wykładem.

LITERATURA

1. N. Abramson, Teoria informacji i kodowania, PWN, Warszawa 1969.
2. D. Harel, Rzecz o istocie informatyki -- algorytmika, WN-T, Warszawa 1992.
3. J. E. Hopcroft, J. D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, PWN, Warszawa 1994.

Nastepny dokument:	Wstęp do programowania
Nadrzędny dokument:	PRZEDMIOTY SPECJALNOŚCIOWE (DLA SPECJALNOŚCI MATEMATYKA Z INFORMATYKĄ)
Poprzedni dokument:	Systemy operacyjne