Drukuj Eksport do pliku (MS Word)
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. 2017/2018
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

Efekt 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 efekty kierunkowe: K2_W07
Powiązane efekty obszarowe: T2A_W07

Profil ogólnoakademicki - umiejętności

Efekt 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 efekty kierunkowe: K2_U06
Powiązane efekty obszarowe: T2A_U09

Profil ogólnoakademicki - kompetencje społeczne

Efekt PTI_K01
umiejętność rozwiązywania podstawowych problemów teoretycznych informatyki
Weryfikacja: sprawdziany, egzamin
Powiązane efekty kierunkowe: K2_K01
Powiązane efekty obszarowe: T2A_K06