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

Teoria języków formalnych

Informacje ogólne

Kod przedmiotu: 1000-I1TJF Kod Erasmus / ISCED: (brak danych) / (0613) Tworzenie i analiza oprogramowania i aplikacji
Nazwa przedmiotu: Teoria języków formalnych
Jednostka: Wydział Matematyki i Informatyki
Grupy: Inf., I st. inż., stacjonarne, 2 rok, przedmioty obowiązkowe
Inf., I st., stacjonarne, 2 rok, przedmioty obowiązkowe
Informatyka, studia inżynierskie 1 stopnia, 2 rok
Mat. I st., stacjonarne, przedmioty do wyboru (podstawowe)
Mat. ogólna, I st., stacjonarne, 3 rok, przedmioty do wyboru (matematyczne)
Przedmioty z polskim językiem wykładowym
Wszystkie przedmioty z WMiI
Punkty ECTS i inne: 6.00
zobacz reguły punktacji
Język prowadzenia: polski
Wymagania wstępne:

Podstawowe wiadomości z zakresu matematyki i informatyki obejmujące teorię zbiorów, matematykę dyskretną, teorię algorytmów oraz programowanie.

Rodzaj przedmiotu:

kanon

Całkowity nakład pracy studenta:

30 godz. – wykład

4 godz. - egzamin

30 godz. - ćwiczenia:

50 godz. - praca własna - bieżące przygotowanie do zajęć, studiowanie literatury,

35 godz. - praca własna - przygotowanie do egzaminu.

RAZEM: 149 godz.

6 pkt. ECTS

Efekty uczenia się - wiedza:

Student ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną w zakresie języków formalnych i automatów (INF1_W02).

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:

1. Potrafi zastosować wiedzę matematyczną do formułowania, analizowania i rozwiązywania prostych zadań związanych z informatyką.

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

3. Potrafi ocenić, na podstawowym poziomie, przydatność rutynowych metod i narzędzi informatycznych oraz wybrać i zastosować właściwą metodę i narzędzia do typowych zadań informatycznych.

4. Definiuje składnię języków programowania i języka naturalnego za pomocą wprowadzonych modeli.

5. Odróżnia problemy rozstrzygalne od nierozstrzygalnych.


Efekty uczenia się - kompetencje społeczne:

1. Kreatywność: Myśli twórczo w celu udoskonalenia istniejących bądź stworzenia nowych rozwiązań.

2. Sumienność i dokładność: Jest nastawiony na jak najlepsze wykonanie zadania; dba o szczegół; jest systematyczny.

3. Komunikatywność: 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ę.

4. Dążenie do rozwoju: Jest nastawiony na nieustanne zdobywanie nowej wiedzy, umiejętności i doświadczeń; rozumie potrzebę ciągłego doskonalenia się i podnoszenia kompetencji zawodowych.

5. Wytrwałość i konsekwencja: 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:

WYKŁAD

Egzamin pisemny - po zakończeniu wykładów.

ĆWICZENIA

Kryteria oceniania:

Zaliczenie na ocenę na podstawie:

• wyników z kolokwiów (co najmniej 1)

• wyników wejściówek

• wyników uzyskanych za samodzielne wykonanie zadań domowych rozwiązywanych przez cały semestr

• aktywności na zajęciach.

Dodatkowo na ocenę końcową składają się:

• systematyczność

• rozwiązywanie zadań dla chętnych

• obecność.

Dopuszczalny limit nieusprawiedliwionych nieobecności na zajęciach – 2 razy.

Uwaga: Zwolnienia lekarskie z zajęć proszę dostarczać w terminie dwóch tygodni od daty wystawienia.

Zajęcia w cyklu "Semestr letni 2017/18" (zakończony)

Okres: 2018-02-26 - 2018-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin, 30 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Kamila Barylska, Łukasz Mikulski
Prowadzący grup: Kamila Barylska, Łukasz Mikulski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Semestr letni 2018/19" (zakończony)

Okres: 2019-02-25 - 2019-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin, 30 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Kamila Barylska, Łukasz Mikulski
Prowadzący grup: Kamila Barylska, Mariusz Kaniecki
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Semestr letni 2019/20" (w trakcie)

Okres: 2020-02-29 - 2020-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin, 30 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Kamila Barylska, Łukasz Mikulski
Prowadzący grup: Anna Gogolińska, Mariusz Kaniecki, Łukasz Mikulski, Marcin Piątkowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Semestr letni 2020/21" (jeszcze nie rozpoczęty)

Okres: 2021-03-01 - 2021-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin, 30 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: (brak danych)
Prowadzący grup: (brak danych)
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.