SylabUZ
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 |
Semestr | 2 |
Liczba punktów ECTS do zdobycia | 5 |
Typ przedmiotu | obowiązkowy |
Język nauczania | polski |
Sylabus opracował |
|
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 |
Algorytmy i struktury danych, Logika dla informatyków, Podstawy systemów dyskretnych, Analiza matematyczna.
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.
Wykład: wykład konwencjonalny/tradycyjny.
Ćwiczenia: ćwiczenia rachunkowe.
Opis efektu | Symbole efektów | Metody weryfikacji | Forma zajęć |
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%
Zmodyfikowane przez prof. dr hab. inż. Andrzej Obuchowicz (ostatnia modyfikacja: 22-04-2020 14:49)