Powrót

Podstawy logiki, teorii automatów i obliczalności (2023/2024)

Wykład odbywa się w środy w godz. 18:55 - 20:35 w sali 201 C-1.
Wykład przeznaczony jest dla studentów pierwszego roku Automatyki i Robotyki WEFiM PWr.

Materiały

Literatura podstawowa

  1. J. Cichoń, Wykłady ze wstępu do matematyki, DWE, 2003
  2. J. Cichoń, Wykłady ze wstępu do matematyki

Literatura pomocnicza

  1. J. Kraszewski, Wstęp do matematyki, WNT, 2012
  2. W. Guzicki, P. Zakrzewski, Wykłady ze wstępu do matematyki, WN PWN, 2021

Zaliczenie kursu

Ćwiczenia

Na ćwiczeniach odbędą się 3 kartkówki. Za każdą z nich będzie można uzyskać 6 pkt. Kartkówki będą zapowiedziane. Zostaną przeprowadzone pod koniec zajęć.
Dodatkowo można zdobyć punkty za aktywność.

Na kartkówkach trzeba mieć coś do pisania i ewentualnie czystą kartkę na brudnopis. Wszelkie inne pomoce są nielegalne!

Kolokwium zaliczeniowe

Kolokwium zaliczeniowe odbędzie sie na ostatnim wykładzie.

Do zdobycia będzie 36 punktów.

Ocena końcowa

Ocena z ćwiczeń zależy od sumy $K1+K2+K3+A$, gzie $Ki$ to liczba punktów za $i$-tą kartkówkę, $A$ - liczba punktów z aktywności.
Ocena będzie wystawiona na podstawie tabelki:
PunktyOcena
0-82.0
9-103.0
11-12 3.5
13-14 4.0
15-16 4.5
17-18 5.0
19+ 5.5
Ocena z wykładu zależy od wyniku kolokwium zaliczeniowego. (Jeśli ocena z wykładu jest wyższa niż z ćwiczeń, to ocena z ćwiczeń jest taka jak z wykładu.)
PunktyOcena
0-152.0
16-193.0
20-23 3.5
24-27 4.0
28-31 4.5
32-35 5.0
36 5.5

Zrealizowany materiał

  1. Rachunek zdań
    1. Język, spójniki logiczne $\land, \lor, \neg, \rightarrow, \leftrightarrow$
    2. Waluacja, wartościowanie
    3. Tautologia
  2. Mnogości, czyli zbiory
    1. Symbol $\in$
    2. Aksjomat ekstensjonalności i jego konsekwencje
    3. Funkcja zdaniowa
    4. Aksjomat wycinania, paradoks Russela
    5. Operacje na zbiorach: przekrój $\cap$, różnica $\setminus$
    6. Aksjomat sumy w wersji beta, $\cup$
    7. Relacja $\subseteq$
    8. Aksjomat zbioru potęgowego
    9. Aksjomat pary
    10. Dopełnienie
    11. Para uporządkowana, definicja Kuratowskiego $(a,b)=\{\{a\},\{a,b\}\}$
    12. Produkt (iloczyn) kartezjański $A\times B=\{(x,y): x\in A\land y\in B\}$
    13. Aksjomat zbioru potęgowego oraz Aksjomat Wycinania gwarantują istnienie produktu kartezjańskiego
  3. Kwantyfikatory
    1. Kwantyfikator ogólny $\forall$ (dla każdego) i szczegółowy $\exists$ (istnieje)
    2. Podstawowe własności
    3. Kwantyfikatory ograniczone
  4. Relacje
    1. Dziedzina i obraz relacji
    2. Własności relacji: zwrotność, przechodniość, symetryczność, słabaantysymetryczność
    3. Złożenie (superpozycja) relacji, relacja odwrotna
    4. Funkcje
    5. Iniekcja, suriekcja, bijekcja
    6. Zbiór $A^B$
    7. Obraz, przeciwobraz
  5. Automaty skończone
    1. Skończony automat deterministyczny DFA
    2. Rozszerzenie funkcji przejścia
    3. Język akceptowany przez DFA
    4. Niedeterministyczny automat skończony NFA
    5. Język akceptowany przez NFA
    6. Równoważność DFA i NFA
    7. Lemat o pompowaniu
    8. Dowód lematu o pompowaniu
    9. Zastosowania lematu o pompowaniu
    10. Automaty z $\varepsilon$-przejściami
    11. Zamkniętość języków akceptowanych przez automaty na operacje teoriomnogościowe
    12. Wyrażenia regularne
    13. Języki regularne
    14. Zamknietość języków akceptowanych przez DFA na operacje $L_1L_2$ oraz $L^*$
    15. Język akceptowany przez DFA jest regularny
    16. Języki regularne = języki akceptowane przez skończone automaty
  6. Gramatyki bezkontekstowe
    1. Przykłady gramatyk
    2. Formalna definicja
    3. Wyprowadzenie w gramatyce, drzewo wyprowadzenia
    4. Równoważność powyższych
    5. Język bezkontekstowy, czyli język $L(G)$ reprezentowany przez gramatykę $G$
    6. Budowa gramatyki dla języka $L(G)\setminus\{\epsilon\}$
    7. Eliminacja $\epsilon$-produkcji
    8. Gramatyki w postaci Chomsky'ego
    9. Lemat o pompowaniu dla języków bezkontekstowych
    10. Przykład języka, który nie jest bezkontekstowy

Powrót