Języki formalne i automaty
Informacje ogólne
Kod przedmiotu: | 0800-16JFA-DZ |
Kod Erasmus / ISCED: |
(brak danych)
/
(0610) Information and Communication Technologies (ICTs)
|
Nazwa przedmiotu: | Języki formalne i automaty |
Jednostka: | Wydział Fizyki, Astronomii i Informatyki Stosowanej |
Grupy: | |
Strona przedmiotu: | http://www.fizyka.umk.pl/~milosz/JiA/ |
Punkty ECTS i inne: |
(brak)
|
Język prowadzenia: | polski |
Wymagania wstępne: | Elementy logiki matematycznej i algebry zbiorów, elementy matematyki dyskretnej |
Rodzaj przedmiotu: | przedmiot fakultatywny |
Całkowity nakład pracy studenta: | Godziny realizowane z udziałem nauczycieli ( 48 godz.): - udział w wykładach 30 h - udział w ćwiczeniach 15 h - konsultacje z nauczycielem akademickim 3 h Czas poświęcony na pracę indywidualną studenta (70 godz.): - przygotowanie do wykładu 15 h - przygotowanie do ćwiczeń 15 h - pisanie prac, projektów 15 h - czytanie literatury 5 h - przygotowanie do egzaminu 10 h - przygotowanie do kolokwium 10 h Łącznie: 118 godz. (4 ECTS) |
Efekty uczenia się - wiedza: | K_W01, K_W03, K_W06: ma ogólnoakademicką wiedzę z matematyki dyskretnej przydatną do formułowania i rozwiązywania prostych zadań związanych z informatyką, ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną w zakresie analizy składni i semantyki języków programowania i inżynierii programowania. Zna podstawowe metody, techniki i narzędzia stosowane przy rozwiązywaniu prostych zadań informatycznych z zakresu analizy składni i senmantyki języków programowania i opisu danych. |
Efekty uczenia się - umiejętności: | U01: potrafi wykorzystać nabytą wiedzę matematyczną do opisu składni i semantyki języków formalnych i wyrażeń symbolicznych oraz do konstrukcji i zapisu algorytmów przetwarzania takich struktur. U02: Potrafi pozyskiwać informacje z literatury, baz danych oraz innych źródeł, potrafi zidentyfikować dyskretne struktury matematyczne w problemach i wykorzystać teoretyczną wiedzę dotyczącą tych struktur do analizy i rozwiązania tych problemów. U03: Potrafi efektywnie tworzyć programy skryptowe dotyczące analizy tekstu, interpretacji symbolicznych wyrażeń i języków formalnych. Przypisanie do kierunkowych efektów kształcenia: K_U02, K_U08, K_U09 |
Efekty uczenia się - kompetencje społeczne: | K01: Rozumie potrzebę ciągłego dokształcania powodowanego pojawianiem się nowych osiągnięć, nowych technologii, etc. rozumie potrzebę wymiany informacji w grupach osób zajmujących się informatyką, rozumie możliwości jakie daje edukacja akademicka. Przypisanie do kierunkowych efektów kształcenia: K_K06, K_K04 |
Metody dydaktyczne: | wykład informacyjny (konwencjonalny) metoda ćwiczeniowa |
Metody dydaktyczne podające: | - wykład informacyjny (konwencjonalny) |
Metody dydaktyczne poszukujące: | - ćwiczeniowa |
Skrócony opis: |
Wykład z ćwiczeniami dotyczy teorii języków formalych, klas języków wg. hierarchii Chomsky'ego, metod ich definiowania i rozpoznawania, a także efektywnych algorytmów analizy składni. |
Pełny opis: |
Program zajęć: 1. Podstawy matematyczne a. Zbiory, relacje, grafy b. Teoria mocy - zbiory przeliczalne i nieprzeliczalne c. Proste struktury algebraiczne d. Indukcja matematyczna e. Rekursja 2. Języki formalne a. Alfabet i język nad nim b. Różne metody definiowania języków c. Operacje na językach 3. Gramatyki - hierarchia Chomsky'ego języków formalnych a. Języki i gramatyki regularne, wyrażenia regularne b. Języki i gramatyki bezkontekstowe c. Języki i gramatyki kontekstowe d. Języki i gramatyki typu "0" e. Języki rekursywne i rekursywnie przeliczalne 4. Automaty i ich relacje z hierarchią Chomsky'ego a. Skończone automaty deterministyczne b. Automaty niedeterministyczne, równoważność z automatami deterministycznymi c. Automaty ze stosem d. Automaty liniowo ograniczone e. Maszyny Turinga 5. Hipoteza Churcha 6. Niedeterministyczne i losowe maszyny Turinga 7. Modele obliczeń a. Funkcje f : N ? N a języki formalne b. Gramatyki, automaty i wyrażenia jako modele obliczeń 8. Teoria złożoności obliczeniowej i jej związki z teorią języków formalnych a. Klasy P i NP b. Redukcja, problemy NP-zupełne i NP-trudne c. Przykłady problemów NP-zupełnych i redukcji między nimi 9. Języki formalne w zastosowaniach 10. Teoria parsingu: gramatyki LL(k) i LR(k) 11. Systemy Lindenmayera Zagadnienia realizowane na ćwiczeniach są ilustracją wykładanych treści. |
Literatura: |
P. Linz, An introduction to formal languages and automata, Jones & Barlett 2006 A. Brooks Weber, Formal language - a practical introduction, Franklin, Beedle & Ass., 2008 M. Michalski, Języki Formalne i Automaty dla słuchaczy kierunku Informatyka Stosowana, Instytut Fizyki UMK |
Metody i kryteria oceniania: |
Metody oceniania: Pisemne kolokwium – W01 Pisemne prace domowe – U01 – U03 Kryteria oceniania: Wykład: na ocenę na podstawie sumarycznej liczby punktów uzyskanych w 2 pisemnych kolokwiów Ndst – 0-50% pkt. Dst – 51-62% pkt. Dst plus – 63-69% pkt. Db – 70-81% pkt. Db plus – 82-87% pkt Bdb – 88-100% pkt. Ćwiczenia: zaliczenie na podstawie sumarycznej liczby punktów zdobytych za pisemne prace domowe (zadania) ndst – 0-59% pkt dst - 60-70% pkt dst plus – 70-75% pkt db – 76-85% pkt db plus – 86-89% pkt bdb - 90-100% pkt |
Praktyki zawodowe: |
nie dotyczy |
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.