Logika a grafy

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 (3-4 týdny):

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

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

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

4. Reserva pro případ zdržení.

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. Odvozování důsledků (přirozená dedukce).

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

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

Uspořádání témat a výběr pokročilých témat se může lišit.

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: pokročilá témata.

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://cw.fel.cvut.cz/wiki/courses/b0b01lgr/

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čebnamístnost T2:C4-365 Gollová A. 11:00–12:30 (přednášková par. 1 paralelka 102) Dejvice Cvičebnamí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čebnamí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-78místnost T2:C4-364 Dostál M. 11:00–12:30 (přednášková par. 1 paralelka 105) Dejvice Cvicebnamí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
Pá	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-209mí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:C4-365 Gollová A. 09:15–10:45 (přednášková par. 1 paralelka 109) Dejvice Cvičebnamístnost T2:C4-459 Gollová A. 11:00–12:30 (přednášková par. 1 paralelka 110) Dejvice Laborator počítačemístnost T2:C4-459 Dostál M. 14:30–16:00 (přednášková par. 1 paralelka 111) Dejvice Laborator počítače místnost T2:D3-209 Dostál M. 12:45–14:15 SUDÝ TÝDEN (přednášková par. 1) Dejvice T2:D3-209
St	místnost T2:C2-85 14:30–16:00 (přednášková par. 1 paralelka 103) Dejvice Cvičebnamístnost T2:C2-85 16:15–17:45 (přednášková par. 1 paralelka 104) Dejvice Cvičebnamístnost T2:C2-85 18:00–19:30 (přednášková par. 1 paralelka 105) Dejvice Cvičebna
Čt	místnost T2:C2-84 Žukovec N. 09:15–10:45 (přednášková par. 1 paralelka 112) Dejvice Ucebnamístnost T2:C2-84 Žukovec N. 12:45–14:15 (přednášková par. 1 paralelka 106) Dejvice Ucebnamístnost T2:C2-84 Žukovec N. 14:30–16:00 (přednášková par. 1 paralelka 107) Dejvice Ucebnamístnost T2:C2-86 16:15–17:45 (přednášková par. 1 paralelka 108) Dejvice Cvičebna
Pá

Předmět je součástí následujících studijních plánů:

• Kybernetika a Robotika 2016 (povinný předmět programu)
• Otevřená informatika - Informatika a počítačové vědy 2016 (povinný předmět programu)
• Otevřená informatika - Internet věcí 2016 (povinný předmět programu)
• Otevřená informatika - Software 2016 (povinný předmět programu)
• Otevřená informatika - Počítačové hry a grafika 2016 (povinný předmět programu)
• Otevřená informatika - před rozřazením do oborů (povinný předmět programu)
• Lékařská elektronika a bioinformatika (povinně volitelný předmět)
• Otevřená informatika - před rozřazením do specializací (povinný předmět programu)
• Otevřená informatika - Základy umělé inteligence a počítačových věd 2018 (povinný předmět programu)
• Otevřená informatika - Internet věcí 2018 (povinný předmět programu)
• Otevřená informatika - Software 2018 (povinný předmět programu)
• Otevřená informatika - Počítačové hry a grafika 2018 (povinný předmět programu)
• Kybernetika a Robotika 2021 (povinný předmět programu)