SylabUZ

Wygeneruj PDF dla tej strony

Teoretyczne podstawy informatyki - opis przedmiotu

Informacje ogólne
Nazwa przedmiotu Teoretyczne podstawy informatyki
Kod przedmiotu 11.3-WI-INFP-TPI
Wydział Wydział Informatyki, Elektrotechniki i Automatyki
Kierunek Informatyka
Profil ogólnoakademicki
Rodzaj studiów pierwszego stopnia z tyt. inżyniera
Semestr rozpoczęcia semestr zimowy 2020/2021
Informacje o przedmiocie
Semestr 2
Liczba punktów ECTS do zdobycia 5
Typ przedmiotu obowiązkowy
Język nauczania polski
Sylabus opracował
  • prof. dr hab. inż. Andrzej Obuchowicz
Formy zajęć
Forma zajęć Liczba godzin w semestrze (stacjonarne) Liczba godzin w tygodniu (stacjonarne) Liczba godzin w semestrze (niestacjonarne) Liczba godzin w tygodniu (niestacjonarne) Forma zaliczenia
Ćwiczenia 30 2 18 1,2 Zaliczenie na ocenę
Wykład 30 2 18 1,2 Egzamin

Cel przedmiotu

  • zapoznanie studentów z informacjami o podstawowych teoretycznych pojęciach dotyczących informatyki, jak algorytm, języki formalne, gramatyka bezkontekstowa, a także pojęciem automatów deterministycznych oraz niedeterministycznych,
  • nauka podstawowych umiejętności w zakresie wyznaczania klasy złożoności algorytmów, sprawdzania własności stopu, dowodzenia częściowej poprawności,
  • zapoznanie studentów z tezą Churcha-Turinga, z definicją problemu łatwo i trudno rozwiązywalnego oraz pojęciem NP-trudności,
  • zapoznanie studentów z pojęciami dotyczącymi teorii algorytmów równoległych.

Wymagania wstępne

Algorytmy i struktury danych, Logika dla informatyków, Podstawy systemów dyskretnych, Analiza matematyczna.

Zakres tematyczny

Wiadomości wstępne: algorytm i jego własności, notacja asymptotyczna. Poprawność algorytmów: algorytm poprawny, poprawność częściowa, własność określoności obliczeń, własność stopu; dowodzenie poprawności częściowej, dowodzenie własności stopu, logika Hoare'a.


Podstawy teorii automatów i języków: automaty skończone i wyrażenia regularne, gramatyki bezkontekstowe, automaty ze stosem i języki bezkontekstowe, własności języków bezkontekstowych.


Prymitywne modele algorytmiczne. Teza Churcha--Turinga. Maszyna Turinga i jej warianty. Maszyna o dostępie swobodnym. Programy licznikowe.

Sprawność algorytmów. Miary efektywności algorytmów. Złożoność przestrzenna i czasowa. Złożoność pesymistyczna i średnia. Dolne i górne ograniczenie złożoności. Złożoność naturalna. Problemy algorytmicznie zamknięte i otwarte, luka algorytmiczna.


Klasyfikacja problemów algorytmicznych. Problemy łatwo-rozwiązywalne i trudno-rozwiązywalne. Klasy problemów algorytmicznych: logarytmiczne, wielomianowe, NP, NP-zupełne i wykładnicze. Otwarte problemy związane z klasyfikacją problemów algorytmicznych. Dowodzenie NP-zupełności. Nierozwiązywalność i nierozstrzygalność.


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.


Algorytmy probabilistyczne niektórych konwencjonalnych problemów algorytmicznych. Probabilistyczne klasy złożoności.

Metody kształcenia

Wykład: wykład konwencjonalny/tradycyjny.
Ćwiczenia: ćwiczenia rachunkowe.

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 z kolokwiów pisemnych lub ustnych przeprowadzonych co najmniej raz w semestrze.

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. Ben Ari M.: Logika matematyczna w informatyce, WNT, Warszawa, 2005
  2. Graham R.L., Knuth D.E., Patashnik O.: Matematyka konkretna, PWN, Warszawa, 2002
  3. Papadimitriou C. H.: Złożoność obliczeniowa, Helion, Gliwice, 2012
  4. Ross K. A., Wright C. R. B.: Matematyka dyskretna, PWN, Warszawa, 2000
  5. Wróblewski P.: Algorytmy, struktury danych i języki programowania, Helion, Gliwice, 1997

Uwagi


Zmodyfikowane przez prof. dr hab. inż. Andrzej Obuchowicz (ostatnia modyfikacja: 22-04-2020 14:49)