Fakulta informačních technologií VUT v Brně

Detail předmětu

Algebra, kombinatorika, grafy

QM3 Ak. rok 2003/2004 zimní semestr

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

Jazyk výuky

česky

Zakončení

zkouška (ústní)

Rozsah

39 hod. přednášky

Bodové hodnocení

Zajišťuje ústav

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.

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

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

  • Obecný přístup k algebrám: teorie univerzálních algeber, v ariety, Birkhoffova věta. Vícedruhové algebry.
  • Teorie kategorií a třídy algeber. Brandtovy grupoidy.
  • Čá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).
  • Vybraná kapitola z obecné teorie grup.
  • Vybraná kapitola z obecné teorie okruhů.
  • 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.
  • Ideály ve svazech a faktorizace. Svazy a matematická logika. Jak teorie svazů přispívá ke studiu variet.
  • Kombinatorika I: Dirichletův princip. Slovníková uspořádání. Rekurentní vztahy (Fibonacciho problém, princip "rozděl a panuj").
  • 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ů.
  • 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í.
  • Grafy II: Posloupnosti stupňů vrcholů, respektive dvojic polostupňů. Algoritmy restituce. Soustavy nerovností Erdöse-Gallaie a Galea-Rysera. Problém izomorfizmu.
  • Grafy III: Vybrané maticové metody. Demoucronův algoritmus pro úrovně dosažitelnosti, Warshallův algoritmus.

Osnova ostatní - projekty, práce

  • Jedna seminární práce z přiděleného doprovodného tématu.
Nahoru