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
- J. Cichoń, Wykłady ze wstępu do matematyki, DWE, 2003
- J. Cichoń, Wykłady ze wstępu do matematyki
Literatura pomocnicza
- J. Kraszewski, Wstęp do matematyki, WNT, 2012
- 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:
Punkty | Ocena |
0-8 | 2.0 |
9-10 | 3.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.)
Punkty | Ocena |
0-15 | 2.0 |
16-19 | 3.0 |
20-23 | 3.5 |
24-27 | 4.0 |
28-31 | 4.5 |
32-35 | 5.0 |
36 | 5.5 |
Zrealizowany materiał
- Rachunek zdań
- Język, spójniki logiczne $\land, \lor, \neg, \rightarrow, \leftrightarrow$
- Waluacja, wartościowanie
- Tautologia
- Mnogości, czyli zbiory
- Symbol $\in$
- Aksjomat ekstensjonalności i jego konsekwencje
- Funkcja zdaniowa
- Aksjomat wycinania, paradoks Russela
- Operacje na zbiorach: przekrój $\cap$, różnica $\setminus$
- Aksjomat sumy w wersji beta, $\cup$
- Relacja $\subseteq$
- Aksjomat zbioru potęgowego
- Aksjomat pary
- Dopełnienie
- Para uporządkowana, definicja Kuratowskiego $(a,b)=\{\{a\},\{a,b\}\}$
- Produkt (iloczyn) kartezjański $A\times B=\{(x,y): x\in A\land y\in B\}$
- Aksjomat zbioru potęgowego oraz Aksjomat Wycinania gwarantują istnienie produktu kartezjańskiego
- Kwantyfikatory
- Kwantyfikator ogólny $\forall$ (dla każdego) i szczegółowy $\exists$ (istnieje)
- Podstawowe własności
- Kwantyfikatory ograniczone
- Relacje
- Dziedzina i obraz relacji
- Własności relacji: zwrotność, przechodniość, symetryczność, słabaantysymetryczność
- Złożenie (superpozycja) relacji, relacja odwrotna
- Funkcje
- Iniekcja, suriekcja, bijekcja
- Zbiór $A^B$
- Obraz, przeciwobraz
- Automaty skończone
- Skończony automat deterministyczny DFA
- Rozszerzenie funkcji przejścia
- Język akceptowany przez DFA
- Niedeterministyczny automat skończony NFA
- Język akceptowany przez NFA
- Równoważność DFA i NFA
- Lemat o pompowaniu
- Dowód lematu o pompowaniu
- Zastosowania lematu o pompowaniu
- Automaty z $\varepsilon$-przejściami
- Zamkniętość języków akceptowanych przez automaty na operacje teoriomnogościowe
- Wyrażenia regularne
- Języki regularne
- Zamknietość języków akceptowanych przez DFA na operacje $L_1L_2$ oraz $L^*$
- Język akceptowany przez DFA jest regularny
- Języki regularne = języki akceptowane przez skończone automaty
- Gramatyki bezkontekstowe
- Przykłady gramatyk
- Formalna definicja
- Wyprowadzenie w gramatyce, drzewo wyprowadzenia
- Równoważność powyższych
- Język bezkontekstowy, czyli język $L(G)$ reprezentowany przez gramatykę $G$
- Budowa gramatyki dla języka $L(G)\setminus\{\epsilon\}$
- Eliminacja $\epsilon$-produkcji
- Gramatyki w postaci Chomsky'ego
- Lemat o pompowaniu dla języków bezkontekstowych
- Przykład języka, który nie jest bezkontekstowy
Powrót