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

Teoria języków formalnych

Informacje ogólne

Kod przedmiotu: 1000-I1TJF
Kod Erasmus / ISCED: (brak danych) / (0613) Tworzenie i analiza oprogramowania i aplikacji Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu: Teoria języków formalnych
Jednostka: Wydział Matematyki i Informatyki
Grupy: Mat. I st., stacjonarne, przedmioty do wyboru (podstawowe)
Mat. ogólna, I st., stacjonarne, 3 rok, przedmioty do wyboru (matematyczne)
Punkty ECTS i inne: 6.00 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:

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

Rodzaj przedmiotu:

kanon

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:

- opis
- opowiadanie
- pogadanka
- wykład informacyjny (konwencjonalny)

Skrócony opis:

Przedmiot kursowy dla II roku studiów I stopnia (licencjackich i inżynierskich). Jego celem jest przedstawienie podstawowych pojęć i faktów z teorii języków formalnych oraz klasyfikacja i analiza własności tych języków, a także zaprezentowanie metod ich wykorzystania w praktyce programistycznej i inżynierii programowania.

Pełny opis:

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

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.

Metody i 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].

Zajęcia w cyklu "Semestr letni 2021/22" (zakończony)

Okres: 2022-02-21 - 2022-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin, 30 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Kamila Barylska
Prowadzący grup: Kamila Barylska
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Semestr letni 2022/23" (zakończony)

Okres: 2023-02-20 - 2023-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin, 30 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Kamila Barylska
Prowadzący grup: Kamila Barylska
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Semestr letni 2023/24" (w trakcie)

Okres: 2024-02-20 - 2024-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin, 30 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Kamila Barylska
Prowadzący grup: Kamila Barylska, Anna Gogolińska
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.
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)