1. SylabUZ
2. Wydział Nauk Inżynieryjno-Technicznych
3. semestr zimowy 2016/2017
4. Informatyka / Sieciowe systemy informatyczne - 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 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

Zapisz zmiany

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.

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%

Obciążenie pracą	Studia stacjonarne (w godz.)	Studia niestacjonarne (w godz.)
Godziny kontaktowe (udział w zajęciach; konsultacjach; egzaminie, itp.)	75	46
Samodzielna praca studenta (przygotowanie do: zajęć, kolokwium, egzaminu; studiowanie literatury przygotowanie: pracy pisemnej, projektu, prezentacji, raportu, wystąpienia; itp.)	75	104
Łącznie	150	150
Punkty ECTS	Studia stacjonarne	Studia niestacjonarne
Zajęcia z udziałem nauczyciela akademickiego	3	2
Zajęcia bez udziału nauczyciela akademickiego	3	4
Łącznie	6	6

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 dr hab. inż. Marek Sawerwain, prof. UZ (ostatnia modyfikacja: 06-09-2016 09:58)