Theoretical Foundations of Computer Science - course description

General information

Course name	Theoretical Foundations of Computer Science
Course ID	11.3-WI-INFP-TPI
Faculty	Faculty of Computer Science, Electrical Engineering and Automatics
Field of study	Computer Science / Industrial Information Systems
Education profile	academic
Level of studies	First-cycle studies leading to Engineer's degree
Beginning semester	winter term 2016/2017

Course information

Semester	3
ECTS credits to win	6
Course type	obligatory
Teaching language	polish
Author of syllabus	dr hab. inż. Marek Sawerwain, prof. UZ prof. dr hab. inż. Andrzej Obuchowicz

Classes forms

The class form	Hours per semester (full-time)	Hours per week (full-time)	Hours per semester (part-time)	Hours per week (part-time)	Form of assignment
Class	30	2	18	1,2	Credit with grade
Lecture	30	2	18	1,2	Exam

Aim of the course

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.

Prerequisites

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

Scope

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.

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.

Teaching methods

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

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

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%

Notes

Modified by dr hab. inż. Marek Sawerwain, prof. UZ (last modification: 06-09-2016 10:05)

Generate PDF for this page