Uniwersytet Mikołaja Kopernika w Toruniu - Centralny punkt logowaniaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Języki formalne i automaty

Informacje ogólne

Kod przedmiotu: 0800-JFA Kod Erasmus / ISCED: (brak danych) / (0541) Matematyka
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: 4.00
Język prowadzenia: polski
Wymagania wstępne:

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

Rodzaj przedmiotu:

przedmiot obowiązkowy

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

Skrócony opis:

Wykład z ćwiczeniami dotyczy teorii języków formalnych, klas języków wg. hierarchii Chomsky'ego, metod ich definiowania i rozpoznawania, zagadnień złożoności obliczeniowej, 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. 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.

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

Zajęcia w cyklu "Semestr zimowy 2020/21" (zakończony)

Okres: 2020-10-01 - 2021-02-21
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 15 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Miłosz Michalski
Prowadzący grup: Miłosz Michalski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Wykład - Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.