V tomto topicu by som chcel vždy napísať nejaké stručné zhrnutie, čo sme stihli na cviku.
Ak budete mať otázky k niečomu, čo bolo na cviku, otvorte na to nový topic. (Tento topic by som chcel zachovať pre tento jediný účel.)
Tu sa dá pozrieť, čo sme na cvičeniach robili minule: viewtopic.php?t=2046
Cvičenia LS 2024/25 - diskrétna matematika
-
Martin Sleziak
- Posts: 5816
- Joined: Mon Jan 02, 2012 5:25 pm
-
Martin Sleziak
- Posts: 5816
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Cvičenia LS 2024/25 - diskrétna matematika
Na stránke k predmetu sú zverejnené prvé domáce úlohy: https://msleziak.com/vyuka/2024/dm2/du01.pdf
Ak by boli nejaké nejasnosti týkajúce sa d.ú, treba sa ozvať. (Aj v budúcnosti budem domáce úlohy zverejňovať po cviku a termín bude spravidla dva týždne.)
1. týždeň (20.2):
Dokázali sme hokejkovú identitu - matematickou indukciou aj kombinatoricky.
Pozreli sme sa na niekoľko príkladov z 01principy.pdf takého typu, kde bolo treba spočítať počty nejakých objektov: úlohy 6, 7, 8 a 9.
Potom sme ešte ukázali kombinatoricky nejaký vzťah pre $\sum\limits_{k=1}^n k^2$ (úloha 2). Nejaké vyjadrenie pre túto sumu by sme vedeli dostať aj z hokejkovej identity (úlohy 3 a 4).
Keďže na cviku padla otázka ako to je pre vyššie mocniny, tak pridám linku na tento článok na Wikipédii: Faulhaber's formula
A keď už pridávam linky, tu sa dajú nájsť rôzne zdôvodnenia pre $\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}6$: Sum of First $n$ Squares Equals $\frac{n(n+1)(2n+1)}{6}$ (Mathematics Stack Exchange)
Ak by boli nejaké nejasnosti týkajúce sa d.ú, treba sa ozvať. (Aj v budúcnosti budem domáce úlohy zverejňovať po cviku a termín bude spravidla dva týždne.)
1. týždeň (20.2):
Dokázali sme hokejkovú identitu - matematickou indukciou aj kombinatoricky.
Pozreli sme sa na niekoľko príkladov z 01principy.pdf takého typu, kde bolo treba spočítať počty nejakých objektov: úlohy 6, 7, 8 a 9.
Potom sme ešte ukázali kombinatoricky nejaký vzťah pre $\sum\limits_{k=1}^n k^2$ (úloha 2). Nejaké vyjadrenie pre túto sumu by sme vedeli dostať aj z hokejkovej identity (úlohy 3 a 4).
Keďže na cviku padla otázka ako to je pre vyššie mocniny, tak pridám linku na tento článok na Wikipédii: Faulhaber's formula
A keď už pridávam linky, tu sa dajú nájsť rôzne zdôvodnenia pre $\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}6$: Sum of First $n$ Squares Equals $\frac{n(n+1)(2n+1)}{6}$ (Mathematics Stack Exchange)
-
Martin Sleziak
- Posts: 5816
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Cvičenia LS 2024/25 - diskrétna matematika
Na stránke k predmetu sú zverejnené nové domáce úlohy: https://msleziak.com/vyuka/2024/dm2/du02.pdf
3. týždeň (6.3):
Príklady, ktoré sme počítali, sa dajú nájsť v 02binom1.pdf.
3. týždeň (6.3):
Príklady, ktoré sme počítali, sa dajú nájsť v 02binom1.pdf.
- Ešte sme sa vrátili k dôkazu binomickej vety a rozmysleli sme si, ako to je pre matice.
- Rozmysleli sme si, ako sa dá pomocou binomických koeficientov vyjadriť počet najkratších ciest po mriežke.
- Počet $k$-prvkových podmnožín v $\{1,2,\dots,n\}$ takých, že sa tam nevyskytnú susedné čísla. viewtopic.php?t=2053
- S pomocou komplexných čísel sme vyjadrili $\sum\limits_{k\ge0}\binom n{4k}$.
-
Martin Sleziak
- Posts: 5816
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Cvičenia LS 2024/25 - diskrétna matematika
Na stránke k predmetu sú zverejnené vové domáce úlohy: https://msleziak.com/vyuka/2024/dm2/du03.pdf
Dohodli sme sa, že najbližšie termíny cvičení budú 3.4., 10.4. a 24.4. (Pretože 17.4., 1.5. aj 8.5. sú štvrtky, kedy je voľno resp. neučí sa.)
5. týždeň (20.3):
Príklady, ktoré sme počítali, sa zväčša dajú nájsť v 03binom2.pdf.
(A tieto príklady sú aj medzi cvičeniami v texte na stránke.)
Prvá suma (aj s nejakými hintami) je v 02binom1.pdf.
Ešte raz sme sa vrátili k identite $\sum\limits_{k=0}^n k\binom nk = n2^{n-1}$: viewtopic.php?t=1003
Rovnosť $\binom nk\binom kl=\binom nl\binom{n-k}{k-l}$: viewtopic.php?t=987
Pozreli sme sa na sumy
\begin{align*}
\sum_{k=0}^n k^2\binom nk&=n(n+1)2^{n-2}\\
\sum_{k=0}^n k(k-1)\binom nk&=n(n-1)2^{n-2}
\end{align*}
Pozreli sme sa na $\sum_{k=0}^n \binom nk^2=\binom{2n}n$ a pripomenuli Vandermondovu identitu.
Rozmysleli sme si, že platí $\sum\limits_{k=0}^n k\binom nk^2=n\binom{2n-1}{n-1}.$
Dokázali sme, že $\sum_{k=0}^n (-1)^k k\binom nk =0$, resp. to, že takáto suma cez párne aj cez nepárne indexy nám dá tú istú hodnotu $n2^{n-2}$.
Dohodli sme sa, že najbližšie termíny cvičení budú 3.4., 10.4. a 24.4. (Pretože 17.4., 1.5. aj 8.5. sú štvrtky, kedy je voľno resp. neučí sa.)
5. týždeň (20.3):
Príklady, ktoré sme počítali, sa zväčša dajú nájsť v 03binom2.pdf.
(A tieto príklady sú aj medzi cvičeniami v texte na stránke.)
Prvá suma (aj s nejakými hintami) je v 02binom1.pdf.
Ešte raz sme sa vrátili k identite $\sum\limits_{k=0}^n k\binom nk = n2^{n-1}$: viewtopic.php?t=1003
Rovnosť $\binom nk\binom kl=\binom nl\binom{n-k}{k-l}$: viewtopic.php?t=987
Pozreli sme sa na sumy
\begin{align*}
\sum_{k=0}^n k^2\binom nk&=n(n+1)2^{n-2}\\
\sum_{k=0}^n k(k-1)\binom nk&=n(n-1)2^{n-2}
\end{align*}
Pozreli sme sa na $\sum_{k=0}^n \binom nk^2=\binom{2n}n$ a pripomenuli Vandermondovu identitu.
Rozmysleli sme si, že platí $\sum\limits_{k=0}^n k\binom nk^2=n\binom{2n-1}{n-1}.$
Dokázali sme, že $\sum_{k=0}^n (-1)^k k\binom nk =0$, resp. to, že takáto suma cez párne aj cez nepárne indexy nám dá tú istú hodnotu $n2^{n-2}$.
-
Martin Sleziak
- Posts: 5816
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Cvičenia LS 2024/25 - diskrétna matematika
Pripomeniem, že najbližšie cvičenie je o týždeň 10.4. a ďalšie bude 24.4. (Pretože 17.4., 1.5. aj 8.5. sú štvrtky, kedy je voľno resp. neučí sa.)
Na stránke k predmetu sú zverejnené nové domáce úlohy: https://msleziak.com/vyuka/2024/dm2/du04.pdf
Termín som dal o tri týždne - aby ste ich nemuseli odovzdávať na najbližšom cviku budúci štvrtok. (Nech máte na riešenie úloh aspoň dva týždne.)
7. týždeň (2.4):
Počítali sme príklady z 04pie.pdf. (Aj nabudúce by sme sa chceli ešte pozrieť na nejaké príklady z tejto sady - prinajmenšom celkom určite sa chceme pozrieť na veci týkajúce sa $D_n$, t.j. počtu permutácií bez pevného bodu. Okrem toho asi prejdeme ešte aj nejaké ďalšie príklady na princíp zapojenia a vypojenie - k príkladom týkajúcim sa grafov sa dostaneme možno ku koncu budúceho cvika; možno až na tom ďalšom cviku.)
Konkrétne sme sa pozreli na úlohy 11 a 10, týkajúce sa počtu celočíselných riešení lineárnej rovnice s viac premennými, kde nám teraz pribudli aj horné ohraničenia.)
Úloha 14 - počet čísel bez štvorcov.
Úloha 12 - počet čísel, ktoré sú deliteľné $2$ alebo $7$. Túto úlohu sme potom vypočítali aj pomocou Eulerovej funkcie - dalo sa tam nejako použiť to, že $\varphi(14)=6$).
Eulerova funkcia
Úloha 6: Ak $n>2$, tak $\varphi(n)$ je párne.
Toto sme zatiaľ ukázali pomocou prvočíselného rozkladu - nabudúce by sme sa k tejto úlohe chceli vrátiť a rozmyslieť si, či nevieme to isté dokázať tak, že vhodne popárujeme prvky množiny, ktorej počet vyjadruje $\varphi(n)$.
Pridám aj nejakú linku: Why is Euler's Totient function always even?
Úloha 5: Zdôvodnili sme $\sum\limits_{d\mid n}\varphi(d)=n$.
Na stránke k predmetu sú zverejnené nové domáce úlohy: https://msleziak.com/vyuka/2024/dm2/du04.pdf
Termín som dal o tri týždne - aby ste ich nemuseli odovzdávať na najbližšom cviku budúci štvrtok. (Nech máte na riešenie úloh aspoň dva týždne.)
7. týždeň (2.4):
Počítali sme príklady z 04pie.pdf. (Aj nabudúce by sme sa chceli ešte pozrieť na nejaké príklady z tejto sady - prinajmenšom celkom určite sa chceme pozrieť na veci týkajúce sa $D_n$, t.j. počtu permutácií bez pevného bodu. Okrem toho asi prejdeme ešte aj nejaké ďalšie príklady na princíp zapojenia a vypojenie - k príkladom týkajúcim sa grafov sa dostaneme možno ku koncu budúceho cvika; možno až na tom ďalšom cviku.)
Konkrétne sme sa pozreli na úlohy 11 a 10, týkajúce sa počtu celočíselných riešení lineárnej rovnice s viac premennými, kde nám teraz pribudli aj horné ohraničenia.)
Úloha 14 - počet čísel bez štvorcov.
Úloha 12 - počet čísel, ktoré sú deliteľné $2$ alebo $7$. Túto úlohu sme potom vypočítali aj pomocou Eulerovej funkcie - dalo sa tam nejako použiť to, že $\varphi(14)=6$).
Eulerova funkcia
Úloha 6: Ak $n>2$, tak $\varphi(n)$ je párne.
Toto sme zatiaľ ukázali pomocou prvočíselného rozkladu - nabudúce by sme sa k tejto úlohe chceli vrátiť a rozmyslieť si, či nevieme to isté dokázať tak, že vhodne popárujeme prvky množiny, ktorej počet vyjadruje $\varphi(n)$.
Pridám aj nejakú linku: Why is Euler's Totient function always even?
Úloha 5: Zdôvodnili sme $\sum\limits_{d\mid n}\varphi(d)=n$.