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 2024
• Semestr: zimní
• E-Kredity: 5
• Rozsah, examinace: zimní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• 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.
• Vyučující: 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
• Je neslučitelnost pro: NDMI023, NDMX028
• Je záměnnost pro: NDMX028

Anotace

čeština

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.

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (01.04.2015)

angličtina

Advanced course in Computer Science Applications of linear algebraic methods in graph theory and combinatorics. Linear dependence and independence of vectors, equiangular lines, two-distance sets, almost disjoint set systems. Determinants. Eigenvalues and eigenvectors, Moore graphs, strongly regular graphs. Seidel's switching. Error-correcting codes, namely perfect codes in Hamming metrics. Theory of distance regular graphs and Biggs's proof of Lloyd's theorem. Van Lint-Tietavainen's proof of nonexistence of perfect codes over finite fields.

Poslední úprava: T_KAM (20.04.2007)

Podmínky zakončení předmětu

čeština

Zápočet se uděluje za dostatečný počet vyřešených domácích úkolů. Zkouška může mít kontaktní nebo distanční formu.

Poslední úprava: Kratochvíl Jan, prof. RNDr., CSc. (23.09.2020)

angličtina

Solution of home assignments is required for the credit.

Poslední úprava: Kratochvíl Jan, prof. RNDr., CSc. (16.09.2020)

Literatura

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

Sloane, McWilliams: Coding theory

Poslední úprava: T_KAM (20.04.2007)

Požadavky ke zkoušce

čeština

Zkouška může mít kontaktní nebo distanční formu. 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.

Poslední úprava: Kratochvíl Jan, prof. RNDr., CSc. (23.09.2020)

angličtina

The exam is oral and may be performed remotely. The knowledge and skills examined correspond to the syllabus in extent presented during the lectures. Common understanding to all notions and their relationship, theorems including proofs and ability to apply the acquired skills to simple situations related to the topics of the class are subject of the examination. Credit from the recitations must be obtained prior to enrolling to an exam.

Poslední úprava: Kratochvíl Jan, prof. RNDr., CSc. (23.09.2020)

Sylabus

čeština

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.

Proplétání vlastních čísel a důsledky pro nezávislost a barevnost grafu.

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ů.

Poslední úprava: Kratochvíl Jan, prof. RNDr., CSc. (02.10.2024)

angličtina

Application of linear dependence and independence - cardinality of nearly-disjoint set systems, equiangular line systems, two-distance point sets.

Set systems with prescribed parity of intersections.

Eigenvalue techniques - spectra of graphs, Moore graphs, interlacing of eigenvalues and its consequences for independence number and chromatic number of a graph.

Seidel's switching.

Perfect codes in Hamming metrics and generalization to distance-regular graphs, Biggs's proof of Lloyd theorem, van Lint-Tietavainen proof of nonexistence of perfect codes over finite fields.

Construction of Golay codes.

Poslední úprava: Kratochvíl Jan, prof. RNDr., CSc. (02.10.2024)