Teoria języków formalnych
1000-I1TJF
1. Podstawowe definicje: alfabet, słowa, języki, monoid wolny.
2. Zbiory i wyrażenia regularne
3. Deterministyczne i niedeterministyczne automaty skończone
4. Minimalizacja automatów skończonych
5. Twierdzenie Kleene’go
6. Lemat o pompowaniu dla języków regularnych
7. Analiza leksykalna: problem dopasowywania wzorca, budowanie lekserów
8. Algorytmy decyzyjne dla zbiorów regularnych
9. Gramatyki. Hierarchia Chomsky'ego
10. Lemat o pompowaniu dla języków bezkontekstowych
11. Automaty ze stosem
12. Zastosowania w inżynierii programowania: algorytmy parsingu
13. Rozstrzygalność i nierozstrzygalność
14. Problem odpowiedniości Posta
15. Podstawowe problemy decyzyjne dla języków bezkontekstowych
Całkowity nakład pracy studenta
wykład – 30 godzin
ćwiczenia – 30 godzin
samodzielne rozwiązywanie zadań zadanych przez prowadzącego zajęcia zajęcia – 30 godzin
egzamin – 4 godziny
praca własna (bieżące przygotowanie do zajęć, rozwiązywanie zadań, studiowanie literatury) - 30 godzin
przygotowanie do egzaminu – 26godzin
RAZEM: 150 godzin (6 punktów ECTS)
Efekty uczenia się - wiedza
W1. Student ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną w
zakresie programowania, algorytmów i złożoności, języków formalnych i automatów, języków i paradygmatów programowania (K_W02).
W2. Student zna podstawowe metody projektowania, analizowania i programowania algorytmów (projektowanie strukturalne, rekurencja, złożoność obliczeniowa) (K_W04).
W szczególności zna:
• Wyrażenia i języki regularne,
• Automaty skończone,
• Gramatyki,
• Automaty ze stosem,
• Leksery i parsery,
• Rozstrzygalne i nierozstrzygalne problemy decyzyjne z zakresu teorii języków formalnych.
Efekty uczenia się - umiejętności
Student:
U1. Potrafi zastosować wiedzę matematyczną do formułowania, analizowania i rozwiązywania zadań informatycznych (K_U01).
U2. Potrafi pozyskiwać informacje z literatury, baz wiedzy, Internetu oraz innych wiarygodnych źródeł, integrować je, dokonywać ich interpretacji oraz wyciągać wnioski i formułować opinie (K_U02).
U3. Projektuje, analizuje pod kątem poprawności i złożoności obliczeniowej oraz programuje algorytmy; wykorzystuje podstawowe techniki algorytmiczne i struktur danych (K_U07).
U4. Potrafi ocenić, na podstawowym poziomie, przydatność rutynowych metod i narzędzi informatycznych oraz wybrać i zastosować właściwą metodę i narzędzia do konkretnych zadań informatycznych (K_U23).
Efekty uczenia się - kompetencje społeczne
K1. Myśli twórczo w celu udoskonalenia istniejących bądź stworzenia nowych rozwiązań.
K2. Jest nastawiony na jak najlepsze wykonanie zadania; dba o szczegóły; jest systematyczny.
K3. Skutecznie przekazuje innym swoje myśli w zrozumiały sposób; właściwie posługuje się terminologią fachową; potrafi nawiązać kontakt w obrębie swojej dziedziny i z osobą reprezentującą inną dziedzinę.
K4. Jest nastawiony na nieustanne zdobywanie nowej wiedzy, Umiejętności i doświadczeń; rozumie potrzebę ciągłego doskonalenia się i podnoszenia kompetencji zawodowych.
K5. W pełni samodzielnie realizuje uzgodnione cele, podejmując samodzielne i czasami trudne decyzje; potrafi samodzielnie wyszukiwać informacje w literaturze.
K6. Pracuje systematycznie i posiada umiejętność pozytywnego podejścia do trudności stojących na drodze do realizacji założonego celu; dotrzymuje terminów.
Metody dydaktyczne eksponujące
- pokaz
Metody dydaktyczne podające
- wykład informacyjny (konwencjonalny)
- opis
- opowiadanie
- pogadanka
Rodzaj przedmiotu
kanon (atrybut wycofany)
Wymagania wstępne
Podstawowe wiadomości z zakresu matematyki i informatyki obejmujące teorię zbiorów (1000-I1LTM), matematykę dyskretną (1000-I1MAD), teorię algorytmów (1000-I1ASD) oraz programowanie (1000-I1PPR).
Koordynatorzy przedmiotu
Kryteria oceniania
Kryteria oceniania ćwiczeń:
Zaliczenie na ocenę na podstawie:
• wyników z kolokwiów (co najmniej 1) [W1,W2,U1,U3,U4,K1,K2,K3]
• wyników wejściówek [W1,W2,U1,U3,U4,K1,K2,K3,K4,K5]
• wyników uzyskanych za samodzielne wykonanie zadań domowych rozwiązywanych przez cały semestr [W1,W2,U1,U2,U3,U4,K1,K2,K3,K4,K5]
• projektów na zaliczenie [W1,W2,U1,U2,U3,U4,K1,K2,K3,K4,K5]
• aktywności na zajęciach [W1,W2,U1,U3,U4,K1,K2,K3,K4,K5] .
Dodatkowo na ocenę końcową składają się:
• systematyczność
• rozwiązywanie zadań dla chętnych
• obecność.
Dopuszczalny limit nieobecności na zajęciach – 2 razy.
Uwaga: Zwolnienie lekarskie należy dostarczyć w terminie 2 tygodni od nieobecności.
Zaliczenie wykładu: egzamin pisemny [W1,W2,U1,U2,U3,U4,K1,K2,K3,K4,K5].
Literatura
Literatura podstawowa:
J. E. Hopcroft, J. D. Ullman, Wprowadzenie do teorii automatów, jezyków i obliczeń. PWN, Warszawa 1994.
M. Sipser, Wprowadzenie do teorii obliczeń. WNT 2009.
A. Kościelski, Teoria obliczeń. Wykłady z matematycznych podstaw informatyki. Wyd. Uniw. Wrocławskiego, Wrocław 1997.
Literatura uzupełniająca:
M. Foryś, W. Foryś, Teoria automatów i języków formalnych, Akademicka Oficyna Wydawnicza Exit, 2005.
A. Blikle, Automaty i gramatyki PWN 1971.
S. Eilenberg, Automata, Languages and Machines. Academic Press 1974.
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i
terminach zajęć) mogą być dostępne w serwisie USOSweb: