1DI1107 - Podstawy informatyki

Nazwa w drugim języku: 

Fundamentals of Computer Science

Cel przedmiotu: 

Celem przedmiotu jest zapoznanie studentów z podstawami teoretycznymi niezbędnymi do studiowania informatyki.

Treści kształcenia: 

Wykład
1. Wprowadzenie (Łańcuch, alfabety i języki. Grafy i drzewa. Dowody przez indukcje. Oznaczenia dla zbiorów. Relacje.)
2. Automaty skończone i wyrażenia regularne (Systemy skończone stanowe. Podstawowe definicje. Niedeterministyczne automaty skończone. Wyrażenia regularne. Zastosowanie automatów skończonych: analizatory leksykalne, edytory tekstu).
3. Gramatyki bezkontekstowe (Wprowadzenie. Definicja. Wyprowadzenia i języki. Drzewa wyprowadzenia.)
4. Automaty ze stosem (Wprowadzenie. Definicje – ruchy, języki akceptowane.)
5. Maszyny Turinga (Wprowadzenie. Model maszyny Turinga. Języki i funkcje obliczalne. Techniki konstruowania maszyn Turinga, Modyfikacje maszyny Turinga. Maszyny Turinga jako generatory).
6. Nierozstrzygalność (Problemy rozstrzygalne i nierozstrzygalne. Własności języków rekurencyjnych i rekurencyjnie przeliczalnych. Uniwersalne maszyny Turinga i problem nierozstrzygalny. Kody maszyn Turinga. Język uniwersalny. Nierozstrzygalność problemu odpowiedniości posta)
7. Hierarchia Chomsky’ego Gramatyka regularna. Gramatyki nieograniczone. Języki kontekstowe.
8. Teoria złożoności obliczeniowej (Definicje, Złożoność pamięciowa, Złożoność czasowa, Klasy złożoności. Redukcja złożoności: Przyspieszenie liniowe. Kompresja taśmy. Zmniejszenie liczby taśm.)
9. Problemy niepodatne (Wielomianowy czas i pamięć: Wprowadzenie, Ograniczone redukowalności, Problemy zupełne. Przykład problemu NP-zupełnego: spełnialność).

Laboratorium
1. Wprowadzenie. Zasoby komputerowe.
2. System operacyjny UNIX – wyrażenia regularne.
3. Automaty skończone. Emulacja działania prostego automatu skończonego
4. Gramatyki bezkontekstowe. Generowanie łańcuchów opisanych za pomocą danej gramatyki
5. Maszyna Turinga. Emulacja działania maszyny Turinga.
6. Problem Odpowiedniości POSTa.
7. Rezerwowy termin odrabiania zajęć.

Bibliografia: 

1. J. E. Hopcroft, M. Rajeev, J. D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń. PWN, 2012.
2. M. Sipser, Wprowadzenie do teorii obliczeń. PWN, 2021.
3. A. V. Aho, J. D. Ullman, Wykłady z informatyki z przykładami w języku C. Helion, 2003.
4. T. H. Cormen, Ch. F. Leiserson, R. L. Rivest, Wprowadzenie do algorytmów, PWN, 2022.
5. C. H. Papadimitriou, Złożoność obliczeniowa. Helion, 2012.
6. D. Brylow, J. Glenn Brookshear, Informatyka w ogólnym zarysie. PWN 2022.
7. D. Harel, Rzecz o istocie informatyki, WNT, 2008.

Metody oceny: 

Wykład jest zaliczany na podstawie pisemnego egzaminu. Laboratorium jest zaliczane w oparciu o zadania problemowe.

Uwagi: 

-

Przedmioty na których bazuje dany przedmiot (prerekwizyty):