PředmětyPředměty(verze: 845)
Předmět, akademický rok 2018/2019
   Přihlásit přes CAS
Aplikace lineární algebry v kombinatorice - NDMI028
Anglický název: Linear Algebra Applications in Combinatorics
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2018 do 2018
Semestr: zimní
E-Kredity: 6
Rozsah, examinace: zimní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: prof. RNDr. Jan Kratochvíl, CSc.
Třída: Informatika Mgr. - Diskrétní modely a algoritmy
M Mgr. MSTR
M Mgr. MSTR > Povinně volitelné
Kategorizace předmětu: Informatika > Diskrétní matematika
Anotace -
Poslední úprava: doc. Mgr. Milan Hladík, Ph.D. (01.04.2015)
Bude demonstrováno užití lineárně algebraických metod v kombinatorice a v teorii grafů. Vhodné pro studenty 2. až 5. ročníku. Perfektní kódy v Hammingově metrice. Zobecnění- perf.kódy ve vzdálenostně regulárních grafech, v kartézských mocninách grafů a v obecných grafech. Souvislosti s teorií dominance v grafech. Perfektní kódy v Hammingově metrice. Zobecnění- perf. kódy ve vzdálenostně regulárních grafech, v kartézských mocninách grafů a v obecných grafech. Souvislosti s teorií dominance v grafech.
Podmínky zakončení předmětu -
Poslední úprava: prof. RNDr. Jan Kratochvíl, CSc. (18.10.2018)

Účast na cvičeních, povoleny jsou nejvýše tři absence. V odůvodněných

případech lze několik absencí nahradit vypracováním domácích úloh. Povaha kontroly studia neumožňuje opakování této kontroly.

Literatura
Poslední úprava: T_KAM (20.04.2007)

Cvetkovic, Doob, Sachs: Spectra of graphs Biggs: Algebraic graph theory

Sloane, McWilliams: Coding theory

Požadavky ke zkoušce -
Poslední úprava: prof. RNDr. Jan Kratochvíl, CSc. (18.10.2018)

Zkouška je ústní. Zkouší se látka podle sylabu v rozsahu předneseném na přednášce. Zkouší se porozumění pojmům a jejich souvislostem, věty včetně důkazů i schopnost aplikovat nabyté znalosti na jednoduché problémy předneseným tématům blízké. Udělení zápočtu je nutnou podmínkou účasti na zkoušce.

Sylabus -
Poslední úprava: prof. RNDr. Jan Kratochvíl, CSc. (18.10.2018)

Lineární závislost a nezávislost vektorů - mohutnost skorodisjunktních systémů množin, equiangulární systémy přímek v prostoru, dvouvzdálenostní množiny bodů.

Systémy podmnožin s předepsanou paritou mohutností a mohutností průniků.

Vlastní čísla, vektory a ortonormální baze - vlastní čísla grafu, operace s grafy, silně regulární grafy, Moorovy grafy, aplikace.

Seidelův switching.

Biggsův důkaz Lloydovy věty, van Lint-Tietavainenův důkaz neexistence perfektních kódů nad konečnými tělesy.

Konstrukce Golayových kódů.

 
Univerzita Karlova | Informační systém UK