Logika a grafy

Přednášející:

Marie Demlová (gar.), Veronika Sobotíková

Cvičící:

Marie Demlová (gar.), Vojtěch Bartík, Tomáš Kroupa, Libor Nentvich, Karel Pospíšil, Veronika Sobotíková, Jiří Velebil

Předmět zajišťuje:

katedra matematiky

Anotace:

Požadavky:

Osnova přednášek:

1. Formule výrokové logiky, pravdivostní ohodnocení, tautologie, kontradikce, splnitelné formule.

2. Sémantický důsledek, tautologická ekvivalence, CNF a DNF, Booleovský kalkul.

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

4. Predikátová logika, formalizace vět, syntakticky správné formule.

5. Interpretace predikátové logiky, sémantický důsledek a tautologická ekvivalence.6

6. Rezoluční metoda v predikátové logice.

7. Grafy neorientované a orientované, základní pojmy.

8. Souvislost, stromy, kostry, kořenové stromy.

9. Silná souvislost, acyklické grafy.

10. Eulerovy grafy a jejich aplikace.

11. Hamiltonovy grafy a jejich aplikace.

12. Nezávislé množiny, kliky v grafy.

13. Vrcholové a hranové barvení grafu.

14. Rezerva.

Osnova cvičení:

1. Formule výrokové logiky, pravdivostní ohodnocení, tautologie, kontradikce, splnitelné formule.

2. Sémantický důsledek, tautologická ekvivalence, CNF a DNF, Booleovský kalkul.

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

4. Predikátová logika, formalizace vět, syntakticky správné formule.

5. Interpretace predikátové logiky, sémantický důsledek a tautologická ekvivalence.6

6. Rezoluční metoda v predikátové logice.

7. Grafy neorientované a orientované, základní pojmy.

8. Souvislost, stromy, kostry, kořenové stromy.

9. Silná souvislost, acyklické grafy.

10. Eulerovy grafy a jejich aplikace.

11. Hamiltonovy grafy a jejich aplikace.

12. Nezávislé množiny, kliky v grafy.

13. Vrcholové a hranové barvení grafu.

14. Rezerva.

Cíle studia:

Studijní materiály:

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

[2] Velebil, J.: Úvod do logiky, ke stažení na stránkách J. Velebila

[3] J. Matoušek, J., Nešetřel, J.: Kapitoly z diskrétní matematiky, Nakladatelství Karolinum, 2000.

[4] Demel, J.: Grafy a jejich aplikace, Academia 2002.

Poznámka:

Předmět bude vyučován pouze v prezenční formě bez anglické verze.

Rozvrh na zimní semestr 2011/2012:

Rozvrh není připraven

Rozvrh na letní semestr 2011/2012:

	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:D3-309 Demlová M. 12:45–15:15 (přednášková par. 1) Dejvice Posluchárnamístnost Z4:B3-218 Bartík V. 16:15–17:45 (přednášková par. 2 paralelka 202) Zikova ulice Poslucharnamístnost Z4:B3-218 Bartík V. 18:00–19:30 (přednášková par. 2 paralelka 201) Zikova ulice Poslucharna místnost T2:D3-309 Demlová M. 12:45–15:15 (přednášková par. 2) Dejvice Posluchárna
St	místnost T2:C4-363 Pospíšil K. 09:15–10:45 (přednášková par. 1 paralelka 111) Dejvice Cvicebnamístnost T2:C4-363 Pospíšil K. 11:00–12:30 (přednášková par. 1 paralelka 101) Dejvice Cvicebna
Čt	místnost Z4:B3-215 Sobotíková V. 07:30–09:00 (přednášková par. 2 paralelka 204) Zikova ulice Cvicebnamístnost Z4:B3-215 Sobotíková V. 09:15–10:45 (přednášková par. 2 paralelka 203) Zikova ulice Cvicebnamístnost Z4:B3-214 11:00–12:30 (přednášková par. 2 paralelka 206) Zikova ulice Cvicebnamístnost Z4:B3-214 Velebil J. 12:45–14:15 (přednášková par. 1 paralelka 102) Zikova ulice Cvicebnamístnost Z4:B3-214 14:30–16:00 (přednášková par. 1 paralelka 103) Zikova ulice Cvicebnamístnost Z4:B3-214 16:15–17:45 (přednášková par. 1 paralelka 104) Zikova ulice Cvicebna místnost Z4:B3-214 09:15–10:45 (přednášková par. 2 paralelka 205) Zikova ulice Cvicebnamístnost T2:A4-202a Nentvich L. 12:45–14:15 (přednášková par. 1 paralelka 105) Dejvice Ucebnamístnost T2:A4-202a Nentvich L. 14:30–16:00 (přednášková par. 1 paralelka 110) Dejvice Ucebnamístnost T2:A4-202a Nentvich L. 16:15–17:45 (přednášková par. 1 paralelka 109) Dejvice Ucebna
Pá	místnost Z4:B3-220 07:30–09:00 (přednášková par. 1 paralelka 107) Zikova ulice Cvicebnamístnost Z4:B3-220 09:15–10:45 (přednášková par. 1 paralelka 106) Zikova ulice Cvicebnamístnost Z4:B3-220 11:00–12:30 (přednášková par. 1 paralelka 108) Zikova ulice Cvicebna

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

• Kybernetika a robotika - Robotika (povinný předmět programu)
• Kybernetika a robotika - Senzory a přístrojová technika (povinný předmět programu)
• Kybernetika a robotika - Systémy a řízení (povinný předmět programu)
• Otevřená informatika - Počítačové systémy (povinný předmět programu)
• Otevřená informatika - Informatika a počítačové vědy (povinný předmět programu)
• Otevřená informatika - Softwarové systémy (povinný předmět programu)
• Kybernetika a robotika - před rozřazením do oborů (povinný předmět programu)
• Otevřená informatika - před rozřazením do oborů (povinný předmět programu)