Detail předmětu

Algebra, kombinatorika, grafy

QM3 Ak. rok 2011/2012 zimní semestr

Aktuální akademický rok

Univerzální algebry. Variety. Kategorie tříd algeber. Speciální třídy binárních systémů obecnějších než grupy. Kapitoly z teorie grup, okruhů a těles. Konečná tělesa a polynomy nad tělesy. Svazy. Svazy a matematická logika. Svazy a teorie variet. Reprezentativní výběr témat z kombinatorické analýzy a teorie grafů: "Counting", rekurentní vtahy, exkluze-inkluze, transverzály v soustavách množin, cestování v multigrafech, planarita a barvení, posloupnosti stupňů a dvojic polostupňů, problém izomorfizmu, vybrané maticové metody.

Garant předmětu

Havel Václav, prof. RNDr., DrSc.

Jazyk výuky

česky

Zakončení

zkouška

Rozsah

  • 39 hod. přednášky

Zajišťuje ústav

Ústav matematiky (UMAT)

Získané dovednosti, znalosti a kompetence z předmětu

Rozšíření vědomostí z algebry, kombinatorické analýzy i teorie grafů k ulehčení studia speciálních předmětů počítačové vědy.

Cíle předmětu

Zopakovat a prohloubit předgraduální znalosti z algebry a diskrétní matematiky. Aktivně ovládnout pojmové a důkazové prostředky obecné algebry pro použití v informatice.

Požadované prerekvizitní znalosti a dovednosti

Základy teoretické informatiky.

Literatura studijní

  • Učební texty přednášejícího (rozmnožené).
  • Bang-Jensen Gutin, Digraphs, London-Berlin-Heidelberg, 2000, inv.č. 5141.
  • Buchmann, Introduction to Cryptography, New York-Berlin-Heidelberg, 2000, inv.č. 5316.
  • J.Matoušek-J.Nešetřil:Kapitoly z diskrétní matematiky, nakl. Karolinum, Praha, 2003
  • J.A.Bondy-U.S.R.Murty:Graph Theory with Applications,North-Holland,New York-Amsterdam-Oxford, 1986
  • Michal Winczer,Teória grafov,Univerzita Komenského Bratislava, 2003; viz   http://user.edi.fmph.uniba.sk/winczer/diskretna.html
  • Radan Kučera:Základy univerzální algebry,MU Brno, 2003; viz http://www.math.muni.cz/~kucera/

Literatura referenční

  • Skornjakov, Elementy obščej algebry, Moskva, 1983.
  • McKenzie-McNulty-Taylor, Algebras, lattices, varieties I, Monterey, California, 1987.
  • Mitchell, Theory of categories, New York, 1965.
  • Rosen, Discrete mathematics and its applications, New York, 1965.
  • Balakrishnan-Ranganathan, A textbook of graph theory, New York-Berlin-Heidelberg, 2000.

Osnova přednášek

  1. Obecný přístup k algebrám: teorie univerzálních algeber, v ariety, Birkhoffova věta. Vícedruhové algebry.
  2. Teorie kategorií a třídy algeber. Brandtovy grupoidy.
  3. Částečné grupoidy a grupoidy, kancelační grupoidy, kvazigrupy, lupy, pologrupy, monoidy. Porovnání z hlediska kongruenčních relací. Třídruhové kvazigrupy (a automaty).
  4. Vybraná kapitola z obecné teorie grup.
  5. Vybraná kapitola z obecné teorie okruhů.
  6. Vnoření pologupy do grupy a okruhu do tělesa. Rozšiřování těles adjunkcemi. Konečná tělesa: konstrukce, existence, podtělesa, automorfizmy. K algebraické kryptografii.
  7. Ideály ve svazech a faktorizace. Svazy a matematická logika. Jak teorie svazů přispívá ke studiu variet.
  8. Kombinatorika I: Dirichletův princip. Slovníková uspořádání. Rekurentní vztahy (Fibonacciho problém, princip "rozděl a panuj").
  9. Kombinatorika II: Užití exkluze-inkluze a věty P. Halla o vzájemně různých reprezentantech. Proslulý algoritmus M. Halla pořizující posloupnost vzájemně různých reprezentantů.
  10. Grafy I: Cestování v neorientovaných i orientovaných multigrafech. Novější výsledky o eulerovských a hamiltonovských sledech a spojeních, o planaritě a o barvení.
  11. Grafy II: Posloupnosti stupňů vrcholů, respektive dvojic polostupňů. Algoritmy restituce. Soustavy nerovností Erdöse-Gallaie a Galea-Rysera. Problém izomorfizmu.
  12. Grafy III: Vybrané maticové metody. Demoucronův algoritmus pro úrovně dosažitelnosti, Warshallův algoritmus.

Průběžná kontrola studia

Hodnocení studia je založeno na bodovacím systému. Pro úspěšné absolvování předmětu je nutno dosáhnout 50 bodů.

Kontrolovaná výuka

Diskuse k probírané látce.

Nahoru