- Nazwa przedmiotu:
- Podstawy teoretyczne informatyki
- Koordynator przedmiotu:
- Paweł KERNTOPF
- Status przedmiotu:
- Obowiązkowy
- Poziom kształcenia:
- Studia II stopnia
- Program:
- Informatyka
- Grupa przedmiotów:
- Przedmioty podstawowe
- Kod przedmiotu:
- PTIUZ
- Semestr nominalny:
- 2 / rok ak. 2020/2021
- Liczba punktów ECTS:
- 5
- Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
- 110 w tym studiowanie materiałów dydaktycznych - 30, rozwiązywanie zadań 30, przygotowanie do egzaminu i egzamin 30, konsultacje 20
- Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
- 1
- Język prowadzenia zajęć:
- polski
- Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
- 2 (rozwiązywanie zadań i problemów)
- Formy zajęć i ich wymiar w semestrze:
-
- Wykład450h
- Ćwiczenia450h
- Laboratorium0h
- Projekt0h
- Lekcje komputerowe0h
- Wymagania wstępne:
- Matematyka Dyskretna
- Limit liczby studentów:
- 30
- Cel przedmiotu:
- Zapoznanie studentów z podstawowymi pojęciami i wynikami teorii automatów i teorii języków formalnych (zwanej także lingwistyką matematyczną), które są wykorzystywane w wielu działach informatyki
- Treści kształcenia:
- 1. Pojęcia podstawowe (alfabet, słowo, podsłowo, słownik, język)
2. Operacje na słowach i językach: złożenie (konkatenacja), potęga, odbicie zwierciadlane, iloraz prawostronny, domknięcie, iteracja
3. Definicja automatu skończonego Rabina-Scotta i porównanie jej z definicjami automatu skończonego Moore’a i automatu skończonego Mealy’ego
4. Graf przejść i tablica przejść automatu skończonego, przekształcenie automatu skończonego niedeterministycznego na deterministyczny
5. Wyrażenia regularne i języki regularne
6. Równoważność wyrażeń regularnych i ich upraszczanie
7. Prawostronne kongruencje, związki prawostronnych kongruencji z automatami skończonymi Rabina-Scotta
8. Synteza automatów skończonych, minimalizacja liczby stanów
9. Analiza automatów skończonych
10. Gramatyki formalne, generowanie języków przez gramatyki
11. Gramatyki i języki bezkontekstowe, wywody słów, drzewa wywodu, jednoznaczność gramatyk
12. Uproszczanie języków bezkontekstowych, postaci normalne
13. Automat ze stosem
14. Maszyny Turinga i automaty liniowo ograniczone
15. Hierarchia Chomsky’ego
- Metody oceny:
- egzamin
- Egzamin:
- tak
- Literatura:
- 1. S. Kowalski, A.W. Mostowski: Teoria automatów i lingwistyka matematyczna, PWN, Warszawa 1979 (I wyd.), 1992 (II wyd.).
2. W. Homenda: Elementy lingwistyki matematycznej i teorii automatów, Oficyna Wydawnicza PW, Warszawa 2005.
3. M. Foryś, W. Foryś: Teoria automatów i języków formalnych, Akademicka Oficyna Wydawnicza EXIT, Warszawa 2005.
4. J.E. Hopcroft, J.D. Ullman: Wprowadzenie do teorii automatów, języków i obliczeń, PWN,
Warszawa 1994 (I wyd.), 2003 (II wyd.).
- Witryna www przedmiotu:
- www.red.okno.pw.edu.pl
- Uwagi:
Efekty uczenia się
Profil ogólnoakademicki - wiedza
- Charakterystyka PTI_W01
- student zna podstawowe pojęcia i wyniki z podstaw teoretycznych informatyki, potrzebne do opanowania wielu zagadnień z różnych dziedzin
Weryfikacja: sprawdziany, egzamin
Powiązane charakterystyki kierunkowe:
K2_W07
Powiązane charakterystyki obszarowe:
I.P7S_WG, III.P7S_WG.o, P7U_W, I.P7S_WG.o, III.P7S_WG
Profil ogólnoakademicki - umiejętności
- Charakterystyka PTI_U01
- student potrafi formułować i rozwiązywać problemy z różnych dziedzin, które można przedstawić za pomocą takich podstawowych pojęć informatyki, jak model automatu lub język formalny
Weryfikacja: sprawdziany, egzamin
Powiązane charakterystyki kierunkowe:
K2_U06
Powiązane charakterystyki obszarowe:
I.P7S_UW, III.P7S_UW.1.o, P7U_U, I.P7S_UW.o, III.P7S_UW.o
Profil ogólnoakademicki - kompetencje społeczne
- Charakterystyka PTI_K01
- umiejętność rozwiązywania podstawowych problemów teoretycznych informatyki
Weryfikacja: sprawdziany, egzamin
Powiązane charakterystyki kierunkowe:
K2_K01
Powiązane charakterystyki obszarowe:
I.P7S_KO, P7U_K