Uniwersytet Mikołaja Kopernika w Toruniu - Centralny punkt logowania
Strona główna

Języki formalne i automaty

Informacje ogólne

Kod przedmiotu: 0800-16JFA-DZ
Kod Erasmus / ISCED: (brak danych) / (0610) Information and Communication Technologies (ICTs) Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
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) Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

zobacz reguły punktacji
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

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.
ul. Jurija Gagarina 11, 87-100 Toruń tel: +48 56 611-40-10 https://usosweb.umk.pl/ kontakt deklaracja dostępności USOSweb 7.0.2.0-1 (2024-03-12)