Języki formalne i automaty 0800-JFA

http://www.fizyka.umk.pl/~milosz/JiA/

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. 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

Zagadnienia realizowane na ćwiczeniach są ilustracją wykładanych treści.

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

W01: ma ogólnoakademicką wiedzę z logicznych podstaw informatyki i matematyki, przydatną do formułowania i rozwiązywania zadań związanych z informatyką. Ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną w zakresie teorii automatów i języków formalnych i jej zastosowań do analizy składni i semantyki języków programowania. Zna podstawowe pojęcia, metody, techniki i narzędzia stosowane przy analizie zadań informatycznych i ich klasyfikacji ze względu na ich złożoność obliczeniową. Przypisanie do kierunkowych efektów kształcenia: K_W01, K_W04

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. Potrafi klasyfikować zadania informatyczne ze względu na ich złożoność obliczeniową, rozumie praktyczne znaczenie takiej klasyfikacji. 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

Rodzaj przedmiotu

przedmiot obligatoryjny

Wymagania wstępne

Elementy logiki matematycznej i algebry zbiorów, elementy matematyki dyskretnej

Koordynatorzy przedmiotu

Miłosz Michalski

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

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

Więcej informacji

Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb:

Strona przedmiotu 0800-JFA w USOSweb