Prednášky ZS 2016/17

[Martin Sleziak]

V tomto vlákne budem pravidelne dopĺňať, čo sa stihlo prebrať na jednotlivých prednáškach. (Napríklad to môže byť užitočné pre ľudí, ktorí z nejakého dôvodu nemohli prísť na prednášku - aby si mohli pozrieť, čo si treba doštudovať.)

Ak budete mať otázky k niečomu, čo odznelo na prednáškach, otvorte na to nový topic. (Tento topic by som chcel zachovať pre tento jediný účel.)

[Martin Sleziak]

1. prednáška: (20.9.)
Hovoril som nejaký úvod, ktorý mal slúžiť ako ukážka typov problémov, ktorým sa budeme počas semestra venovať.
Konkrétne:

• Prechádzky po $n$-rozmernej kocke. Spomeniem, že táto úloha vlastne súvisí s hľadaním Grayovho kódu. A keby sme podobnú úlohu riešili pre ľubovoľné grafy, nielen pre kocky, tak by vlastne išlo o hľadanie Hamiltonovskej kružnice.
• Ofarbovanie hrán $K_6$ a zovšeobecnenie. Hre, ktorú sme spomenuli, sa niekedy hovorí aj Sim. A výsledky, ktoré sme tam spomenuli, súvisia s Ramseyovými číslami, ktorým sa neskôr budeme na prednáške venovať podrobnejšie.

Zo slajdov k tejto časti som neprešiel poslednú tému. Kto by bol zvedavý, súvisí so s permutáciami bez pevného bodu. Tejto téme sa budeme ešte v priebehu semestra venovať.

Aspoň som skúsil začať hovoriť niečo o holubníkovom princípe. Stihol som ho sformulovať, dokázať a ukázať jednu aplikáciu.
Opäť, na stránke si môžete pozrieť slajdy.

[Martin Sleziak]

2. prednáška: (27.9.)
Dnes sme sa ešte stále venovali holubníkovému princípu. Uviedli sme aj všeobecnejšiu verziu. A ukázali sme si ako aplikácie aj niekoľko príkladov, ktoré sa dajú pozrieť i na slajdoch: šachový turnaj (hráči s rovnakým počtom partií), 10 bodov vo štvorci.
Ako posledné som stihol dokázať Erdős–Szekeresovu vetu. Postup z dôkazu som stihol ilustrovať iba na postupnosti dĺžky 5 - na slajdoch si môžete pozrieť to isté pre postupnosť dĺžky 13. (A môžete si samozrejme vyskúšať vymyslieť aj nejaké vlastné postupnosti.)

Z tejto témy som vlastne už nestihol iba výsledok o jednofarebnom trojuholníku v $K_6$. (Inými slovami, že $R(3,3)=6$.)

[Martin Sleziak]

3. prednáška: (4.10.)
Holubníkový princíp. Ešte sme ukázali ako ukážku sme ukázali, že v $K_6$ ofarbenom dvoma farbami musí byť jednofarebný trojuholník. Pridám aj linku na Wikipédiu: Theorem on friends and strangers.
Neskôr sa budeme učiť viac o Ramseyových číslach, pomocou nich sa tento výsledok dá vyjadriť ako R(3,3)=6.

Matematická indukcia. Trochu sme hovorili o princípe matematickej indukcie a spomenuli sme, ako súvisí s axiómou o dobrom usporiadaní.
Ako jednu ukážku použitia matematickej indukcie sme dokázali vzorec pre súčet $n$ členov geometrickej postupnosti. Potom sme sa zaoberali dôkazom, že $\frac1{1\cdot 2}+\frac1{2\cdot3}+\dots+\frac1{n(n+1)}<1$.
Pri tejto úlohe sme videli príklad teleskopickej sumy. (Pomenovanie "teleskopický" pochádza z niečoho takéhoto.)
Súčasne sme videli, že niekedy dôkaz indukciou ide ľahšie, ako dokazujeme silnejšie tvrdenie.

[Martin Sleziak]

4. prednáška (11.10.):
Matematická indukcia. Ukázali sme si niečo o triangulácii $n$-uholníka. Ako posledný príklad na indukciu sme mali dláždenie šachovnice $2^n\times2^n$ s jedným vynechaným štvorcom triminami tvaru L.
Sčítací princíp. Stihol som ho sformulovať (ale nie dokázať). Ako príklad použitia som ukázal Pascalovu identitu.

[Martin Sleziak]

5. prednáška (18.10.):
Sčítací princíp. Dôkaz (matematickou indukciou).
Násobiaci princíp. Formulácia, dôkaz, niekoľko príkladov.
Karteziánsky súčin. Definícia súčinu pre dve množiny a pre n množín. Abeceda, slová, počet slov dĺžky n.
Zobrazenia. Iba sme veľmi stručne zopakovali pojem zobrazenia, injektívneho (prostého) zobrazenia, surjektívneho zobrazenia (zobrazenia na) - tieto pojmy už poznáte z iných predmetov.

[Martin Sleziak]

6. prednáška (27.10.):
Princíp bijekcie. Sformulovali sme princíp bijekcie, ukázali sme si jeden jednoduchý príklad a potom sme sa pozreli na vzťah medzi podmnožinami $n$-prvkovej množiny a slovami z $\{0,1\}^n$. Pri tejto príležitosti sme si ukázali existenciu Grayovho kódu, čo vlastne zodpovedá existencii prechádzky po kocke.
Počítanie dvomi spôsobmi. Povedali sme si niečo o počítaní dvomi spôsobmi (čo je postup, ktorý budeme často používať na odvodenie rôznych identít.) Ukázali sme si dva jednoduché príklady: jednu slovnú úlohu a vyjadrenie $\binom n2=1+2+\dots+(n-1)$.

[Martin Sleziak]

1.11. bolo voľno.

7. prednáška (8.11.):
Binomické koeficienty. Permutácie a k-permutácie. (Ako zaujímavosť sme spomenuli problém obchodného cestujúceho.) Odvodili sme vzťah pre $\binom nk$.
Výber s opakovaním. Ukázali sme si, ako sa odvodí vzťah pre počet nezáporných celočíselných riešení $x_1+\dots+x_n=k$ a tiež sme ho ilustrovali na niektorých príkladoch. (Posledný, ktorý sme stihli, bol príklad so žrebovaním, kde sa číslo vracia do osudia.)

[Martin Sleziak]

8. prednáška (15.11.):
Výber s opakovaním. Počet podmnožín $\{1,2,\dots,n\}$ bez susedných čísel. Monotónne slová.
Počet slov s danými počtami písmen (permutácie s opakovaním).
Permutácie a bijekcie. Vzťah medzi permutáciami a bijekciami, k-permutáciami a injekciami.
Binomické koeficienty. Zopakovali sme si veci, ktoré už poznáme. (Pascalova identita, Pascalov trojuholník). Pozreli sme sa na súčet párnych a nepárnych čísel v riadku Pascalovho trojuholníka.

[Martin Sleziak]

9. prednáška (22.11.):
Binomické koeficienty. Monotónnosť, súčet po diagonále, súčet druhých mocnín. (Nerobil som identitu $\sum\limits_{k=0}^n \binom nk (2^{n-k}+2^k-1)=2\cdot 3^n-2^n$ - hoci je na slajdoch resp. v texte.)
Binomická veta. Ukázali sme si ju na príkladoch a tiež ako pomocou nej môžeme odvodiť nejaké súčty binomických koeficientov.
Prechádzky po mriežke. Ukázali sme si, ako sa dá vyjadriť počet ciest v mriežke z počiatku do daného bodu.