Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2023/2024

Logika a grafy

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
B0B01LGR Z,ZK 5 3P+2S česky
Garant předmětu:
Marie Demlová
Přednášející:
Matěj Dostál, Alena Gollová
Cvičící:
Matěj Dostál, Alena Gollová, Natalie Žukovec
Předmět zajišťuje:
katedra matematiky
Anotace:

Tento předmět se zabývá základy matematické logiky a teorie grafů. Je zavedena syntaxe a sémantika výrokové logiky a predikátové logiky prvního řádu. Důraz je kladen na pochopení pojmu důsledku, na vztah mezi formulí a jejím modelem. Dále jsou zavedeny některé základní pojmy teorie grafů a popsány algoritmy k řešení některých základních úloh z teorie grafů.

Požadavky:

Nejsou.

Osnova přednášek:

Výroková logika (cca 4 týdny):

1. Formální jazyk. Jazyk výrokové logiky.

2. Význam a sémantický důsledek.

3. Resoluční metoda ve výrokové logice.

4. Odvozování důsledků (přirozená dedukce).

Predikátová logika (cca 4 týdny):

1. Jazyk predikátové logiky.

2. Význam a sémantický důsledek v predikátové logice.

3. Resoluční metoda v predikátové logice.

4. Reserva: pokročilá témata.

Teorie grafů: (cca 6 týdnů):

1. Základní pojmy teorie grafů.

2. Stromy. Minimální kostry.

3. Silná souvislost. Acyklické grafy.

4. Kreslení jedním tahem.

5. Barvení. Rovinné grafy.

6. Reserva.

Osnova cvičení:

Řešení teoretických i algoritmických úloh z logiky a teorie grafů.

Upevňování a rozšiřování znalostí a dovedností z přednášek.

Cíle studia:

Cílem předmětu je seznámit studenty se základy matematické logiky a základy teorie grafů.

Studenti by měli rozlišovat syntax a sémantiku, umět pracovat se syntaktickým i sémantickým důsledkem, a dále by měli být schopni formalisovat ve vhodném jazyce jednoduché praktické úlohy.

Dále by studenti měli být schopni řešit teoretické i praktické grafové úlohy, a měli by být schopni popsat a použít základní grafové algoritmy.

Studijní materiály:

[1] M. Huth, M. Ryan: Logic in Computer Science: Modelling and Reasoning about Systems. Cambridge University Press, 2004.

[2] J. A. Bondy, U. S. R. Murty: Graph theory with applications. Elsevier Science Ltd/North-Holland, 1976.

V češtině:

[3] J. Velebil: Velmi jemný úvod do matematické logiky. Online 2007.

[4] M. Demlová, B. Pondělíček: Matematická logika. ČVUT Praha, 1997.

[5] J. Demel: Grafy a jejich aplikace. Academia 2002, druhé vydání 2015.

[6] P. Kovář: Teorie grafů. Online, 2019.

Poznámka:
Další informace:
https://math.fel.cvut.cz/en/people/gollova/lgr.html
Rozvrh na zimní semestr 2023/2024:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
místnost T2:C4-365
Gollová A.
09:15–10:45
(přednášková par. 1
paralelka 101)

Dejvice
Cvičebna
místnost T2:C4-365
Gollová A.
11:00–12:30
(přednášková par. 1
paralelka 102)

Dejvice
Cvičebna
místnost T2:C4-363
Dostál M.
12:45–14:15
(přednášková par. 1
paralelka 107)

Dejvice
Cvicebna
St
místnost T2:C4-365
Gollová A.
09:15–10:45
(přednášková par. 1
paralelka 106)

Dejvice
Cvičebna
místnost T2:C4-365
Gollová A.
11:00–12:30
(přednášková par. 1
paralelka 104)

Dejvice
Cvičebna
Čt
místnost T2:C4-78
Dostál M.
09:15–10:45
(přednášková par. 1
paralelka 103)

Dejvice
T2:C4-78
místnost T2:C4-364
Dostál M.
11:00–12:30
(přednášková par. 1
paralelka 105)

Dejvice
Cvicebna
místnost T2:C4-365
Gollová A.
16:15–17:45
(přednášková par. 1
paralelka 108)

Dejvice
Cvičebna
místnost T2:C3-135
Gollová A.
14:30–16:00
(přednášková par. 1)
Dejvice
T2:C3-135

místnost T2:C3-135
Gollová A.
11:00–12:30
(přednášková par. 1)
Dejvice
T2:C3-135
Rozvrh na letní semestr 2023/2024:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
místnost T2:D3-209
Dostál M.
11:00–12:30
(přednášková par. 1)
Dejvice
T2:D3-209
místnost T2:C3-51
Dostál M.
14:30–16:00
(přednášková par. 1
paralelka 101)

Dejvice
T2:C3-51
místnost T2:C3-51
Dostál M.
12:45–14:15
(přednášková par. 1
paralelka 102)

Dejvice
T2:C3-51
Út
místnost T2:D3-209
Dostál M.
12:45–14:15
SUDÝ TÝDEN

(přednášková par. 1)
Dejvice
T2:D3-209
místnost T2:C4-459
Dostál M.
14:30–16:00
(přednášková par. 1
paralelka 111)

Dejvice
Laborator počítače
St
místnost T2:A4-202b

14:30–16:00
(přednášková par. 1
paralelka 103)

Dejvice
Učebna
místnost T2:A4-202b

16:15–17:45
(přednášková par. 1
paralelka 104)

Dejvice
Učebna
místnost T2:A4-202b

18:00–19:30
(přednášková par. 1
paralelka 105)

Dejvice
Učebna
Čt
místnost T2:C2-84
Žukovec N.
09:15–10:45
(přednášková par. 1
paralelka 112)

Dejvice
Ucebna
místnost T2:C2-84
Žukovec N.
12:45–14:15
(přednášková par. 1
paralelka 106)

Dejvice
Ucebna
místnost T2:C2-84
Žukovec N.
14:30–16:00
(přednášková par. 1
paralelka 107)

Dejvice
Ucebna
místnost T2:A4-202a

16:15–17:45
(přednášková par. 1
paralelka 108)

Dejvice
Ucebna

místnost T2:A4-202a

11:00–12:30
(přednášková par. 1
paralelka 110)

Dejvice
Ucebna
místnost T2:A4-202a

12:45–14:15
(přednášková par. 1
paralelka 109)

Dejvice
Ucebna
Předmět je součástí následujících studijních plánů:
Platnost dat k 30. 11. 2023
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet4680706.html