1. SylabUZ
2. Wydział Informatyki, Elektrotechniki i Automatyki
3. semestr zimowy 2022/2023
4. Informatyka - pierwszego stopnia z tyt. inżyniera
5. Teoretyczne podstawy informatyki

Wygeneruj PDF dla tej strony

Teoretyczne podstawy informatyki - opis przedmiotu

Cel przedmiotu

• zapoznanie studentów z podstawowymi pojęciami informatyki teoretycznej takimi jak algorytm, złożoność obliczeniowa, automat, język formalny oraz gramatyka.   
• nauka podstawowych umiejętności w zakresie weryfikowania własności stopu, dowodzenia poprawności algorytmu i wyznaczania jego złożoności obliczeniowej.
• zapoznanie studentów z hierarchią Chomsky'ego, tezą Churcha-Turinga, klasyfikacją problemów obliczeniowych ze względu na ich rozwiązywalność i złożoność.

Wymagania wstępne

Zapisz zmiany

Algorytmy i struktury danych, Logika dla informatyków, Algebra liniowa, Analiza matematyczna.

Zakres tematyczny

Algorytm i jego własności: poprawność i częściowa poprawność algorytmu, własność określoności obliczeń, własność stopu; dowodzenie poprawności częściowej oraz własności stopu - zastosowanie logiki Hoare'a.

Złożoność obliczeniowa algorytmów (pesymistyczna i średnia). Dolne i górne ograniczenie złożoności problemu algorytmicznego, złożoność naturalna i luka algorytmiczna. Określanie złożoności obliczeniowej algorytmów. Notacja asymptotyczna.

Podstawy teorii automatów, języków i obliczeń: gramatyki i języki, automaty skończone, języki i wyrażenia regularne, gramatyki i języki bezkontekstowe, drzewa wywodu, postacie normalne gramatyk, automaty ze stosem, gramatyki kontekstowe, automaty liniowo-ograniczone, maszyny Turinga i języki rekurencyjnie przeliczalne, hierarchia Chomsky'ego.

Programy licznikowe a maszyny Turinga. Akceptowanie a rozstrzyganie. Złożoność przestrzenna i czasowa. Maszyna o dostępie swobodnym. Klasy problemów algorytmicznych: P, NP i NP-zupełne oraz PSPACE. Dowodzenie NP-zupełności. Otwarte problemy związane z klasyfikacją problemów algorytmicznych. Nierozwiązywalność i nierozstrzygalność. Teza Churcha-Turinga.

Algorytmy współbieżne i probabilistyczne. Stała i rozszerzająca się współbieżność. Złożoność iloczynowa. Sieci - współbieżność o stałych połączeniach. Teza o obliczeniach równoległych. Klasa Nicka. Algorytmy RNC. Współbieżność rozproszona. Bezpieczeństwo i żywotność systemów współbieżnych.

 

Metody kształcenia

wykład: wykład konwencjonalny
ćwiczenia: ćwiczenia rachunkowe, prezentacja, dyskusja

Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się

Opis efektu	Symbole efektów	Metody weryfikacji	Forma zajęć

Warunki zaliczenia

Wykład - warunkiem zaliczenia jest uzyskanie pozytywnej oceny z egzaminu przeprowadzonego w formie pisemnej.

Ćwiczenia - warunkiem zaliczenia jest uzyskanie pozytywnych ocen ze sprawdzianów przeprowadzonych co najmniej raz w semestrze.

Przedmiot - warunkiem zaliczenia przedmiotu jest zaliczenie zarówno ćwiczeń jak i wykładu.

Składowe oceny końcowej = wykład 50% + ćwiczenia 50%

Literatura podstawowa

1. Banachowski L., Kreczmar A.: Elementy analizy algorytmów, WNT, Warszawa, 1982
2. Bilski T., Chmiel K., Stokłosa J.: Zbiór zadań ze złożoności obliczeniowej algorytmów, Wydawnictwo Politechniki Poznańskiej, Poznań, 1992
3. Cormen T. H., Leiserson C. E., Rivest R. L.: Wprowadzenie do algorytmów, WNT, Warszawa, 1997
4. Harel D.: Rzecz o istocie informatyki, WNT, Warszawa, 2000
5. Hopcroft J. E., Ullmann J.D.: Wprowadzenie do teorii automatów, języków i obliczeń, PWN, Warszawa, 2003
6. Aho A.V., Ullmann J.D.: Wykłady z informatyki z przykładami w języku C, Helion, Gliwice, 2003

Literatura uzupełniająca

1. Graham R.L., Knuth D.E., Patashnik O.: Matematyka konkretna, PWN, Warszawa, 2002
2. Papadimitriou C. H.: Złożoność obliczeniowa, Helion, Gliwice, 2012
3. Ross K. A., Wright C. R. B.: Matematyka dyskretna, PWN, Warszawa, 2000

Uwagi

Zmodyfikowane przez dr hab. inż. Piotr Borowiecki, prof. UZ (ostatnia modyfikacja: 21-04-2022 01:13)