Wykłady:

1. Zarys histori, zasotosowania komputerów, obszary informatyki [ PDF ]
2. Arytmetyka maszyny cyfrowej - systemy pozycyjne, algorytmy konwersji [ PDF ]
3. Reprezentacja znaków i liczb [ PDF ]
4. Kodowanie obrazów, dźwięku [ PDF ]
5. Przetwarzanie danych [ PDF ]
6. Poprawność algorytmów, złożoność obliczeniowa [ PDF ]
7. Maszyna Turinga [ PDF ]
8. Języki formalne, gramatyki, ONP [ PDF ]
9. Translacja i translatory [ PDF ]

Opis przedmiotu :

Pojęcie, istota, zadania informatyki, zarys historii. Teoria informacji: informacja, wiadomość, komunikat, entropia informacyjna źródła, redundancja, kod jednoznaczny, kod zwarty. Arytmetyka maszyny cyfrowej: systemy pozycyjne, algorytmy konwersji, stałoprzecinkowa i zmiennoprzecinkowa reprezentacja liczb, reprezentacja znak - moduł prosty i znak - uzupełnienie. Przetwarzanie danych: algorytm schematy blokowe, iteracja, rekurencja. Modele obliczeń, model deterministyczny i uniwersalny maszyny Turinga. Granice obliczalności, nieobliczalność, problem stopu. Funkcje rekurencyjne i ich obliczalność. Języki formalne, gramatyki i automaty: definicja gramatyki, języka generowanego przez gramatykę, klasyfikacja gramatyk wg N. Chomsky'ego. Złożoność obliczeniowa, klasy złożoności, NP-zupełność. Przegląd języków programowania: języki wysokiego i niskiego poziomu, translatory, interpretery, ONP, algorytm translacji wyrażeń arytmetycznych do ONP i odwrotnie.

Literatura:

1. Harel D., Rzecz o istocie informatyki, WNT, Warszawa 2001
2. Brookshear G., Informatyka w ogólnym zarysie, WNT, Warszawa 2003
3. Sysło M. (red.), Elementy informatyki, PWN, Warszawa 1993
4. Sikorski W., Wykłady z podstaw informatyki, MIKOM, Warszawa 2002
5. Wirth N., Algorytmy + struktury danych = programy, WNT, Warszawa 2002