Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Automaty i Sieci Petriego
Tok studiów:
2017/2018
Kod:
AMA-2-206-MZ-s
Wydział:
Matematyki Stosowanej
Poziom studiów:
Studia II stopnia
Specjalność:
Matematyka w zarządzaniu
Kierunek:
Matematyka
Semestr:
2
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma i tryb studiów:
Stacjonarne
Strona www:
 
Osoba odpowiedzialna:
dr hab. Foryś Wit (foryswit@wms.mat.agh.edu.pl)
Osoby prowadzące:
dr Foryś Magdalena (maforys@agh.edu.pl)
dr hab. Foryś Wit (foryswit@wms.mat.agh.edu.pl)
dr Michalik Marek (michalik@agh.edu.pl)
Krótka charakterystyka modułu
Pojęcia i struktury matematyczne stosowane w teorii języków formalnych i automatów.
Opis efektów kształcenia dla modułu zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Powiązania z EKK Sposób weryfikacji efektów kształcenia (forma zaliczeń)
Wiedza
M_W001 zna podstawowe pojęcia i struktury matematyczne stosowane w teorii języków formalnych i automatów MA2A_W01, MA2A_W02, MA2A_U02 Aktywność na zajęciach,
Egzamin,
Odpowiedź ustna
M_W002 zna klasy języków wystepujace w hierarchii Chomsky’ego i ich wlasnosci MA2A_W10, MA2A_K05, MA2A_W07 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
M_W003 zna klasy automatów i gramatyk odpowiadające klasom języków hierarchii Chomsky’ego oraz ich wlasności MA2A_W10, MA2A_K05, MA2A_W06 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
Umiejętności
M_U001 Potrafi rozwiązać algorytmicznie problemy z zakresu automatów, gramatyk i językow odpowiadajacych hierarchi Chomsky’ego MA2A_U07, MA2A_U03, MA2A_U01 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
M_U002 Potrafi rozpoznać problemy rozstrzygalne i nierozstrzygalne z zakresu automatów, gramatyk i językow odpowiadajacych hierarchi Chomsky’ego MA2A_U03, MA2A_U01, MA2A_U13 Aktywność na zajęciach,
Kolokwium,
Odpowiedź ustna
M_U003 potrafi zaproponować rozwiązanie problemu, także algorytmicznego, z zakresu automatów, gramatyk i językow odpowiadajacych hierarchi Chomsky’ego MA2A_U07, MA2A_U03, MA2A_U01 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
Kompetencje społeczne
M_K001 umie ocenić stopień zrozumienia przez siebie problemu i brakujące elementy rozumowania MA2A_K02, MA2A_K07, MA2A_K01 Aktywność na zajęciach,
Egzamin,
Odpowiedź ustna
Matryca efektów kształcenia w odniesieniu do form zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Forma zajęć
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Inne
E-learning
Wiedza
M_W001 zna podstawowe pojęcia i struktury matematyczne stosowane w teorii języków formalnych i automatów + + - - - - - - - - -
M_W002 zna klasy języków wystepujace w hierarchii Chomsky’ego i ich wlasnosci + + - - - - - - - - -
M_W003 zna klasy automatów i gramatyk odpowiadające klasom języków hierarchii Chomsky’ego oraz ich wlasności + + - - - - - - - - -
Umiejętności
M_U001 Potrafi rozwiązać algorytmicznie problemy z zakresu automatów, gramatyk i językow odpowiadajacych hierarchi Chomsky’ego + + - - - - - - - - -
M_U002 Potrafi rozpoznać problemy rozstrzygalne i nierozstrzygalne z zakresu automatów, gramatyk i językow odpowiadajacych hierarchi Chomsky’ego + + - - - - - - - - -
M_U003 potrafi zaproponować rozwiązanie problemu, także algorytmicznego, z zakresu automatów, gramatyk i językow odpowiadajacych hierarchi Chomsky’ego + + - - - - - - - - -
Kompetencje społeczne
M_K001 umie ocenić stopień zrozumienia przez siebie problemu i brakujące elementy rozumowania + + - - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:
  1. Wiadomości wstępne

    WYKŁADY

    Alfabet, słowo, język – elementy teorii półgrup; półgrupy i monoidy wolne.

  2. Gramatyki – model obliczeń; hierarchia Chomsky'ego.
  3. Języki regularne

    Automat skończenie stanowy; automat minimalny i algorytmy; automaty deterministyczne i niedeterministyczne; algorytm determinizacji; własności języków regularnych; lemat o pompowaniu i języki nieregularne; wyrażenia regularne i algorytmy; twierdzenie Kleenego; problemy rozstrzygalności.

  4. Języki bezkontekstowe

    Własności języków bezkontekstowych, gramatyka – postać Chomsky’ego i Greibach oraz algorytmy upraszczania; automat ze stosem; równoważność gramatyki bezkontekstowej i automatu ze stosem – algorytmy; lemat o pompowaniu i języki, które nie są bezkontekstowe; jednoznaczność, problem przynależności i algorytm CYK; problemy rozstrzygalności.

  5. Sieci Petriego

    Wiadomości wstępne. Miejsca i tranzycje – reguły odpalania; przykłady modelowania przy wykorzystaniu sieci (przetwarzanie równoległe, protokoły komunikacji dla przepływu danych, synchronizacja, układy multiprocesorów).

  6. Systemy produkcji

    Modelowanie, analiza i zarządzanie systemami produkcyjnymi – „case study” – systemy cykliczne (linia produkcyjna, system składająco/rozkładający, hala produkcyjna) – systemy acykliczne (short-term planning, scheduling).

Ćwiczenia audytoryjne:
Program ćwiczeń laboratoriów pokrywa się z programem wykładów

Rozwiązywanie problemów, implementacja algorytmów,realizacja małych projektów ilustrujących treści przekazywanych na kolejnych wykładach.

Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 156 godz
Punkty ECTS za moduł 6 ECTS
Udział w wykładach 30 godz
Samodzielne studiowanie tematyki zajęć 50 godz
Udział w ćwiczeniach audytoryjnych 30 godz
Przygotowanie do zajęć 40 godz
Egzamin lub kolokwium zaliczeniowe 2 godz
Dodatkowe godziny kontaktowe z nauczycielem 4 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:
  1. Warunkiem koniecznym dopuszczenia do egzaminu jest posiadanie oceny pozytywnej z ćwiczeń.
  2. Ocenę końcową OK wyznacza się na podstawie średniej ważonej SW obliczonej według wzoru
    SW = 1/3 OC + 2/3 OE,
    gdzie OC jest oceną uzyskaną z ćwiczeń, a OE jest oceną uzyskaną z egzaminu.
  3. Ocena końcowa OK. jest obliczana według algorytmu:
    Jeżeli SW ≥ 4.75, to OK = 5.0 (bdb),
    jeżeli 4.75 > SW ≥ 4.25, to OK = 4.5 (db),
    jeżeli 4.25 > SW ≥ 3.75, to OK = 4.0 (db),
    jeżeli 3.75 > SW ≥ 3.25, to OK = 3.5 (dst),
    jeżeli 3.25 > SW ≥ 3.00, to OK = 3.0 (dst).
  4. Niewielkie odstępstwa są możliwe w zależności od kompetencji egzaminowanego wykazanej w czasie egzaminu.
Wymagania wstępne i dodatkowe:

Nie podano wymagań wstępnych lub dodatkowych.

Zalecana literatura i pomoce naukowe:
  1. M.Foryś, W.Foryś, Teoria automatów i języków formalnych – AOW EXIT, Warszawa 2005
  2. J.E.Hopcroft, J.D.Ulman, Introduction to automata theory, languages and computing, Addison-Wesley, 1979 – dostępna w języku polskim
  3. J.M.Proth, X.Xie – Petri Nets, A Tool for Design and Management of Manufacturing Systems , J.Wiley&Sons, 1996
Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

1. Foryś, Wit; Matyja, Janusz; On one-sided, topologically mixing cellular automata, having continuum of fixed points and topological entropy log(n) for any integer n>1; J. Cell. Autom. 9, No. 1, 37-58 (2014).

2. Foryś, Wit; Matyja, Janusz; On one-sided, D-chaotic cellular automaton, having continuum of fixed points and topological entropy log(3); J. Cell. Autom. 8, No. 3-4, 131-146 (2013).

3. Foryś, Wit; Matyja, Janusz; On one-sided, D-chaotic cellular automata, having continuum of fixed points and topological entropy log(p) for any prime p>3; J. Cell. Autom. 7, No. 4, 303-319 (2012).

4. Foryś, Wit; Oprocha, Piotr; Infinite traces and symbolic dynamics – the minimal shift case;
Fundam. Inform. 111, No. 2, 147-161 (2011).

Informacje dodatkowe:

Brak