\documentclass[12pt,a4paper]{article}
\usepackage{enumitem}
\usepackage[czech]{babel}
\usepackage[utf8]{inputenc}

\textwidth=170mm
\hoffset=-14mm

%\hoffset -24mm
%\voffset -20mm
%\textwidth 170mm
%\textheight 230mm

\usepackage[all]{xy}
\usepackage{amsfonts}

%\usepackage{czech}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{xcolor}

\newcommand{\mezera}{}%\vskip .3cm}
\newcommand{\hvezda}{${}^\ast$}%\
\def\vect #1{{\overrightarrow{#1}}}
\DeclareMathOperator{\tg}{tg}

\newcounter{prik}[section]
\renewcommand{\theprik}{\thesection.\arabic{prik}}
\newcommand{\priklad}[1]{\refstepcounter{prik} 
                         \paragraph*{Příklad \theprik:} #1}
\newcommand{\prikladhvezda}[1]{\refstepcounter{prik} 
                         \paragraph*{Příklad \theprik${}^\ast$:} #1}

                         \newcommand{\matice}[4]{\begin{pmatrix} #1 & #2 \\ #3 & #4\end{pmatrix} }

\newcommand{\cviceni}[2]{{\section{#1}} Cvičení konané #2 2021. \\ \vskip 0.2cm}   
%\newcommand{\cvicenii}[2]{{\section{#1}} Cvičení konané #2 2021. \\ \vskip 0.2cm}   

\def\N{\mathbb N}
\def\Z{\mathbb Z}
\def\Q{\mathbb Q}
\def\R{\mathbb R} 
\def\C{\mathbb C}      
             
\newcommand{\ondra}[1]{{\color{red} #1}}   
\newcommand{\josef}[1]{{\color{blue} #1}}   
          

                         
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%  PREPINANI VERZI %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\rezervnipriklad}[1]{\refstepcounter{prik} 
                         \paragraph*{Příklad \theprik:} #1}

%\newcommand{\rezervnipriklad}[1]{}

% Priprava
\newcommand{\vysledekbez}[1]{[{\it Řešení: #1}]}
\newcommand{\vysledek}[1]{\\ \noindent [{\it Řešení: #1}]}
\newcommand{\napoveda}[1]{{\it Nápověda: #1}}
\newcommand{\poznamka}[1]{{\it Poznámka: #1}}

% Zadani 
%\newcommand{\vysledekbez}[1]{}\newcommand{\vysledek}[1]{}\newcommand{\napoveda}[1]{{\it Nápověda: #1}}\newcommand{\poznamka}[1]{{\it Poznámka: #1}}

% Reseni
%\newcommand{\vysledekbez}[1]{[Řešení: #1}\newcommand{\vysledek}[1]{[Řešení: #1]}\newcommand{\napoveda}[1]{}\newcommand{\poznamka}[1]{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\hlavicka}{
\newpage
\begin{center}
{\large MIN401 Matematika IV - příklady počítané na cvičení (jarní semestr 2021)}
\end{center} 
%{\small \begin{itemize}
%\item Jde o seznam typových úloh, které se probírají na cvičení a dalších obdobných úloh na procvičení  za domácí úlohu. Na písemkách se objeví výhradně modifikace příkladů z této sbírky a~jim obdobné příklady. 
%\item Příklady označené hvězdičkou jsou určeny pro studenty, kteří by se na cvičení příliš nudili a jsou zde uvedeny pouze jako doplňující příklady, které nebudou obsahem písemek.
%\item Program jednotlivých cvičení si sestavují vyučující sami 
%a~mohou se lišit i v rámci jednotlivých cvičení jednoho vyučujícího.
%\item Velké množství příkladů je převzato ze sbírky \uv{Seminář ze středoškolské matematiky} autorů Herman, Kučera, Šimša (skriptum MU, 2004).
%\end{itemize}} 
}

\begin{document}
\pagestyle{empty}

\hlavicka




\cviceni{1.\ týden -- středoškolská dělitelnost}{14.\ 2.} 

\priklad {Jak poznáme, že je celé číslo dělitelné 2, 3, 4, 5, 6, 8, 9, 10, 11? Svá tvrzení zdůvodněte.
}


\priklad 
{Ukažte, že součin pěti po sobě jdoucích čísel je dělitelný 120.
}

\priklad{ Nejdříve pro $n=2,3$ a potom pro další $n\in\N$ si připomeňte 
\begin{enumerate}
\item[a)]  vzorec pro rozdíl $n$-tých mocnin dvou čísel,
\item[b)]  vzorec pro součet $n$-tých mocnin dvou čísel,
\item[c)] vzorec pro $n$-tou mocninu součtu, tzv. binomický vzorec.
\end{enumerate}
}


\priklad{[10.2] Dokažte, že pro libovolné $a \in \mathbb{Z}$ platí:
\begin{itemize}
\item[(i)] $a^2$ dává po dělení čtyřmi zbytek $0$ nebo $1$,
\item[(ii)] $a^2$ dává po dělení osmi zbytek $0$, $1$ nebo $4$,
\item[(iii)] $a^4$ dává po dělení šestnácti zbytek $0$ nebo $1$.
\end{itemize}
}

\priklad{
\begin{itemize}
\item[(i)] Ukažte, že pro každé $n \in \mathbb{N}$ platí $3|4^n-1$.
\item[(ii)] Ukažte, že pro každé $n \in \mathbb{N}$ platí $5|n^5-n$.
\item[(iii)] Ukažte, že pro každé $n \in \mathbb{N}$ platí $5|3^{3n+1}+2^{n+1}$.
\end{itemize}
}


\priklad{[10.1] Určete, pro která přirozená čísla $n \in \mathbb{N}$ je číslo 
$n^3+1$ dělitelné číslem $n-1$.
}

\priklad{ Dokažte, že pro přirozená čísla $a$, $k$ a $n$ platí: jestliže $k\mid n$, pak $a^k-1\mid a^n-1$. Pomocí toho dokažte: Je-li $2^n-1$ prvočíslo, pak $n$ musí být také prvočíslo. Proto se ``největší'' prvočísla hledají ve tvaru $2^p-1$, kde $p$ je prvočíslo.  
 }
 

\priklad { Dokažte, že $25\mid 4^{2n+1}-10n-4$.
 } 


%\priklad{Nalezněte největší společný dělitel polynomů $f(x), g(x) \in \mathbb{R}[x]$
%a určete příslušné koeficienty v Bezoutově rovnosti:
%$$
%f(x) = x^4-2x^3-2x^2+7x-6 \quad \text{a} \quad g(x) = 2x^3-4x^2-x+2.
%$$}

\priklad{
\begin{itemize}
\item[(i)] Nechť $a,b \in \mathbb{N}$, $a \not=b$. Ukažte, že existuje nekonečně mnoho přirozených čísel $n$ takových,
že čísla $a+n$ a $b+n$ jsou nesoudělná.
\item[(ii)] Nechť má číslo $n \in \mathbb{N}$, $n >1$ následující vlastnost: pro každou dvojici dělitelů $a>1$, $b>1$ čísla $n$ 
platí, že $(a,b)>1$. Co můžeme říci o číslu $n$?
\end{itemize}
}

\priklad{[10.10]
\begin{itemize}
\item[(i)] Dokažte, že jsou-li čísla $m,n \in \mathbb{N}$ nesoudělná, jsou nesoudělná i čísla 
$$
m^2+mn+n^2 \quad \text{a} \quad m^2-mn+n^2.
$$
\item[(ii)] Dokažte, že jsou-li lichá čísla $m,n \in \mathbb{N}$ nesoudělná, jsou nesoudělná i čísla 
$$
m+2n \quad \text{a} \quad m^2+4n^2.
$$ 
\end{itemize}
}


\cviceni{2.\ týden -- kongruence, Eulerova funkce}{10.\ 3.}

\priklad{[10.4 a 10.5] Určete největší společný dělitel čísel $a,b \in \mathbb{Z}$
a určete příslušné koeficienty v Bezoutově rovnosti:
\begin{itemize}
\item[(i)] $a=10175$ a $b=2277$, 
\item[(ii)] $a=2^{49}-1$ a $b=2^{35}-1$.
\end{itemize}
}


\priklad{[10.11])
\begin{enumerate}[label=(\roman*)]
\item Nalezněte zbytek po dělení čísla $7^{30}$ číslem $50$.
\item Určete poslední dvě cifry dekadického zápisu čísla $7^{30}$.
\end{enumerate}
}


\priklad{[10.15 a 10.16] 
\begin{enumerate}[label=(\roman*)]
\item Nechť $m,n \in \mathbb{N}$ a $a,b \in \mathbb{Z}$ splňují $a \equiv b \ (\!\!\!\!\mod m^n)$. Ukažte, že pak
$a^m \equiv b^m \ (\!\!\!\!\mod m^{n+1})$
\item Ukažte, že lichá čísla $a$ splňují $a^4 \equiv 1 \ (\!\!\!\!\mod 16)$.
\item Ukažte, že čísla $a$ nedělitelná třemi splňují $a^3 \equiv \pm 1 \ (\!\!\!\!\mod 9)$.
\end{enumerate}
}


\priklad{[10.17] Pro číslo $n \in \mathbb{N}$ označuje $S(n)$ ciferný součet čísla $n$.
\begin{enumerate}[label=(\roman*)]
\item Zopakujte si pravidla po dělitelnost $2$, $3$, $4$, $5$, $6$, $8$, $9$.
\item Ukažte, že $n \equiv S(n) \ (\!\!\!\!\mod 9)$.
\item Pravidlo pro dělitelnost $11$.
\item Ukažte, že pro $n=1000a+b$ platí $n \equiv -a+b \ (\!\!\!\!\mod m)$, kde $m \in \{7,11,13\}$.
\end{enumerate}
}

\priklad{[10.19, 10.20, 10.21] 
\begin{enumerate}[label=(\roman*)]
\item Určete $\varphi(72)$.
\item Dokažte, že pro každé $n \in \mathbb{N}$ platí $\varphi(4n+2)=\varphi(2n+1)$.
\item Určete všechna $n \in \mathbb{N}$ taková, že $\varphi(n)$ je liché.
\item Určete všechna $n \in \mathbb{N}$ taková, že $\varphi(n)=30$.
\item Určete všechna $n \in \mathbb{N}$ taková, že $\varphi(n)=\frac{n}{3}$.
\end{enumerate}
}

\priklad{[10.24, 10.26, 10.28, 10.29] 
\begin{enumerate}[label=(\roman*)]
\item Určete poslední dvojčíslí čísla $7^{2013}$.
\item Určete zbytek po dělení čísla $2^{50}+3^{50}+4^{50}$ číslem $17$.
\item Určete poslední číslici čísla $7^{9^{7^{5^3}}}$.
\item Určete poslední číslici čísla $14^{14^{14}}$.
\end{enumerate}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\cviceni{3.\ týden -- RSA šifry, primitivní kořeny}{18.\ 3.}

\priklad{Veřejný klíč Honzy pro RSA šifru je $(91,23)$. Zachytili jste jemu určenou zprávu $3$. Dekódujte ji.}

\priklad{[10.32, 10.33, slidy] Najděte primitivní kořeny modulo $8$, $11$, $41$ a $41^2$}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\cviceni{4.\ týden -- řešení kongruencí}{25.\ 3.}



\priklad{Vyřešte následující kongruence:
\begin{enumerate}[label=(\roman*)]
\item $5x \equiv 12 \ (\!\!\!\!\mod 23)$.
\item $33x \equiv 7 \ (\!\!\!\!\mod 143)$.
\item $210x \equiv 40 \ (\!\!\!\!\mod 212)$.
\end{enumerate}
}

\priklad{Vyřešte následující soustavy kongruenci:
\begin{enumerate}[label=(\roman*)]
\item $2x \equiv 3 \ (\!\!\!\!\mod 7)$, \  $x \equiv 8 \ (\!\!\!\!\mod 15)$.
\item $x \equiv 3 \ (\!\!\!\!\mod 10)$, \ $x \equiv 8 \ (\!\!\!\!\mod 15)$, \ $x \equiv 5 \ (\!\!\!\!\mod 84)$.
\end{enumerate}
}

\priklad{[10.48, 10.57, 10.58] Vyřešte následující kongruence:
\begin{enumerate}[label=(\roman*)]
\item $7x^{17} \equiv 11 \ (\!\!\!\!\mod 41)$.
\item $x^3 \equiv 3 \ (\!\!\!\!\mod 18)$,
\item $x^2 \equiv 18 \ (\!\!\!\!\mod 63)$.
\end{enumerate}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\cviceni{5.\ týden -- kongruence, šifrování}{31.\ 3.}



\priklad{Vyřešte následující kongruence:
\begin{enumerate}[label=(\roman*)]
\item $x^2 \equiv 1 \ (\!\!\!\!\mod 30)$,
\item $x^3 + x + 3  \equiv 0 \ (\!\!\!\!\mod 25)$,
\item $5x^2+x+8 \equiv 0 \ (\!\!\!\!\mod 11)$,
%\item $x^3 +4x \equiv 12 \ (\!\!\!\!\mod 7^3)$.
\end{enumerate}
}


\priklad{Spočtěte následující Legendreův nebo Jacobiho symbol
$$
\left( \frac{101}{1987} \right), \qquad 
\left( \frac{-35}{97} \right), \qquad 
\left( \frac{-23}{85} \right).
$$
}

\priklad{[Odjinud, 10.67, 10.68] Rozhodněte, zda následující kongruence mají řešení:
\begin{enumerate}[label=(\roman*)]
\item $x^2 \equiv 5 \ (\!\!\!\!\mod 227)$,
\item $x^2 \equiv 5 \ (\!\!\!\!\mod 229)$,
\item $x^2 \equiv 38 \ (\!\!\!\!\mod 65)$,
\item $x^2-23 \equiv 0 \ (\!\!\!\!\mod 77)$.
\end{enumerate}
}

\priklad{[10.93] Šifrování:
\begin{enumerate}[label=(\roman*)]
\item Ukažte, jak pomocí Rabinova kryptosystému s veřejným klíčem $n=437$ zašifrovat 
a pak dešifrovat zprávu $M = 321$.
\item Martin a Honza chtějí komunikovat šifrou ElGamal. Martin si zvolil
prvočíslo $41$ s primitivním kořenem $11$ a tajný klíč $10$, tj.\ zveřejnil $(41,11,A)$, kde $A \equiv 11^{10} \ (\!\!\!\!\mod 41)$.
Honza mu poslal veřejným kanálem dvojici $(22,6)$. Jakou zprávu Honza poslal?
\item Veřejný klíč Honzy pro RSA šifrování je $(33,3)$. Někdo mu poslal zprávu $7$, kterou jste zachytili. Dekódujte ji.
\end{enumerate}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\cviceni{6.\ týden -- Booleovské algebry, uspořádané množiny}{7.\ 4.}

\priklad{Budeme pracovat s výrazy ve výrokové logice.
\begin{enumerate}[label=(\roman*)] 
\item Zjednodušte výraz $(A \wedge B \wedge C) \vee (A' \wedge B) \vee (A \wedge B \wedge C')$.
\item {[11.116]} Nalezněte úplnou disjunktní formu výrazu $(B' \Rightarrow C) \wedge [(A \vee C) \wedge B]'$.
\end{enumerate}
}

\priklad{[11.124] Určete všechny relací uspořádání na čtyřprvkové množině. Pro
každý z neizomorfních typů určete, zda se jedná o svaz. 
Vyskytuje se mezi uspořádáními Booleova algebra?
}

\priklad{[11.126, 11.127] Nakreslete Hasseho diagram svazu dělitelů čísla $36$. Je tento
svaz distributivní? Jedná se o Booleovu algebru? Pak určete  totéž pro dělitele čísla $30$.
}

\priklad{[11.131] Rozhodněte, zda každý řetězec, který má největší a nejmenší prvek, je úplný svaz.}

\priklad{[11.133] Rozhodněte, zda je množina konvexních podmnožin v $\mathbb{R}^3$ svazem pro vhodné operace 
suprema a infima. Pokud ano, je tento svaz úplný či distributivní?}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\cviceni{7.\ týden -- Polynomy}{14.\ 4.}

\priklad{[11.76] Rozložte nad $\mathbb{R}$ a $\mathbb{C}$ polynom
$$
f(x) = x^4 + 2x^3 + 3x^2 + 2x + 1.
$$
}

\priklad{[11.77.] Rozložte polynom $f(x) = x^5+3x^3+3$ nad $\mathbb{Q}$ and $\mathbb{Z}_7$.
}

\priklad{[11.80] Najděte všechny ireducibilní polynomy stupně $\leq 2$ nad $\mathbb{Z}_3$.
}

\priklad{[11.81] Rozhodněte, zda je polynom $x^4+x^3+x+2$ ireducibilní nad $\mathbb{Z}_3$.}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\cviceni{8.\ týden -- polynomy II.}{22.\ 4.}


\priklad{[11.79] 
\begin{enumerate}[label=(\roman*)] 
\item Eisensteinovo kritérium ireducibility nad $\mathbb{Z}$ (tedy i nad $\mathbb{Q}$).
\item Určete polynom s racionálními koeficienty co nejmenšího stupně, jehož kořenem
je číslo $\sqrt[2007]{2}$.
\end{enumerate}
}

\priklad{[11.82, 11.83]
\begin{enumerate}[label=(\roman*)] 
\item Pro liché prvočíslo $p$ určete všechny kořeny polynomu 
$$
f(x) = x^{p-2} +x^{p-3} + \ldots +x +2.
$$
\item Rozložte polynom $g(x) = x^2+x+1$ v $\mathbb{Z}_5[x]$ and $\mathbb{Z}_7[x]$.
\end{enumerate}
}

\priklad{[11.84, 11.84]
\begin{enumerate}[label=(\roman*)] 
\item Rozložte polynom $f(x) = x^6-x^4-5x^2-3$ v $\mathbb{C}[x]$, $\mathbb{R}[x]$, $\mathbb{Q}[x]$, $\mathbb{Z}[x]$,
$\mathbb{Z}_5[x]$ a $\mathbb{Z}_7[x]$ víte-li o něm, že má vícenásobný kořen.
\item  Rozložte polynom $p(x) = x^6+x^5+4x^4+2x^3+5x^2+x+2$ v $\mathbb{C}[x]$, $\mathbb{R}[x]$, $\mathbb{Z}_2[x]$,
$\mathbb{Z}_5[x]$ a $\mathbb{Z}_7[x]$ víte-li o něm, že má vícenásobný kořen $i$.
\item Řešte soustavu $p(x) = q(x) =0$ nad $\mathbb{C}$, kde $q(x) = x^2y^2+y^2+xy+x^2y+2y+1$.
\end{enumerate}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\cviceni{9.\ týden -- okruhy}{28.\ 4.}

\priklad{[11.65] Rozhodněte, zda množina $R$ s operacemi $\oplus$ a $\odot$ tvoří okruh, komutativní okruh, 
obor integrity nebo těleso.
\begin{enumerate}[label=(\roman*)] 
\item[(i)] $R = \mathbb{Z}$, $a \oplus b = a+b+3$, $a \odot b = -3$. [Není okruh.]
\item[(ii)] $R = \mathbb{Z}$, $a \oplus b = a+b-3$, $a \odot b = a \cdot b -1$. [Není okruh.]
\item[(iii)] $R = \mathbb{Z}$, $a \oplus b = a+b-1$, $a \odot b = a +b - a \cdot b$. [Je obor integrity.]
\item[(iv)] $R = \mathbb{Q}$, $a \oplus b = a+b$, $a \odot b = b$. [Není okruh.]
\item[(v)] $R = \mathbb{Q}$, $a \oplus b = a+b+1$, $a \odot b = a+b+ab$. [Je těleso.]
\item[(vi)] $R = \mathbb{Q}$, $a \oplus b = a+b-1$, $a \odot b = a+b+ab$. [Není okruh.]
\end{enumerate}
}

\priklad{[11.66] Dokažte, že podmožina komplexních čísel
$\mathbb{Z}[i] = \{ a+bi | a,b \in \mathbb{Z} \}$ tvoří obor integrity. Jedná se o těleso?
}

\priklad{[11.67] V okruhu matic $Mat_{2,2}(\mathbb{R})$ uvažme podokruh matic tvaru
$$
\begin{pmatrix} a & -b \\ b & a \end{pmatrix},
$$
$a,b \in \mathbb{R}$. Dokažte, že tento podokruh je izomorfní s tělesem $\mathbb{C}$.
}

\priklad{[11.68] Ukažte, že identita je jediný automorfismu tělesa reálných čísel.
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\cviceni{10.\ týden -- grupy I.}{5.\ 5.}


\priklad{[11.1] Rozhodněte o následujících množinách a operacích, jakou algebraickou strukturu
tvoří (grupoid, monoid, pologrupa, grupa):
\begin{enumerate}[label=(\roman*)] 
\item[(i)] podmnožiny množiny přirozených čísel s operací sjednocení [monoid],
\item[(ii)] množina $\mathbb{N}$ spolu s binární operací největší společný dělitel [polorupa],
\item[(iii)] množina $\mathbb{N}$ spolu s binární operací nejmenší společný násobek [monoid],
\item[(iv)] množina reálných invertibilních matic 2x2 spolu s operací sčítání matic [není ani grupoid],
\item[(v)] množina reálných matic 2x2 spolu s operací násobení matic [monoid],
\item[(vi)] množina reálných matic 2x2 spolu s operací odčítán ímatic [grupoid],
\item[(vii)] množina invertibilních matic 2x2 nad $\mathbb{Z}_2$ spolu s operací násobení matic [grupa],
\item[(viii)] množina $\mathbb{Z}_6$ spolu s operací násobení (modulo $6$) [monoid],
\item[(ix)] množina $\mathbb{Z}_7$ spolu s operací násobení (modulo $7$) [grupa].
\end{enumerate}
}

\priklad{11.8} Na množině $(\mathbb{R} \setminus \{0\}) \times \mathbb{R}$ definujeme operaci
$\odot$ jako 
$$
(x,y) \odot (u,v) = (xu, xv+y).
$$
Popište, o jakou algebraickou strukturu se jedná.

\priklad{[2.19] Rozložte následující permutaci v $\mathbb{S}_9$ na součin transpozic:
$$
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
3 & 1 & 6 & 7 & 8 & 9 & 5 & 4 & 2
\end{pmatrix}.
$$
}

\priklad{[11.10] Určete znaménko následujících permutací v $\mathbb{S}_{3n}$ a $\mathbb{S}_{2n}$:
\begin{align*}
&\sigma_1 = 
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & \ldots & 3n-2 & 3n-1 & 3n \\
2 & 3 & 1 & 5 & 6 & 4 & \ldots & 3n-1 & 3n & 3n-2
\end{pmatrix}, \\
&\sigma_2 = 
\begin{pmatrix}
1 & 2 & 3 & \ldots & n & n+1 & n+2 & \ldots & 2n \\
2 & 4 & 6 & \ldots & 2n & 1 & 3 & \ldots & 2n-1 \\
\end{pmatrix}.
\end{align*}
}

\priklad{[11.13] Mějme permutaci $\sigma \in \mathbb{S}_7$,
$$
\sigma = \begin{pmatrix} 
1 & 2 & 3 & 4 & 5 & 6 & 7 \\
3 & 6 & 5 & 7 & 1 & 2 & 4
\end{pmatrix}.
$$
V grupě $(\mathbb{S}_7,\circ)$ určete řád $\sigma$, inverzi k $\sigma$, $\sigma^{2013}$
a ukažte, že $\sigma$ nekomutuje s transpozicí $\tau = (2,3)$.
}

\priklad{[11.16,11.17] Dokažte, že neexistuje čtyřprvková ani pětiprvková nekomutativní grupa.}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\cviceni{11.\ týden -- grupy II.}{12.\ 5.}

\priklad{[11.19] Určete (až na izomorfismus) vsechny komutativní grupy řádu $8$. Potom určete, ketrým z těchto grup jsou
izomorfní grupy
\begin{enumerate}[label=(\roman*)] 
\item $\mathbb{Z}_{15}^\times$,
\item $\mathbb{Z}_{16}^\times$,
\item $\mathbb{Z}_{17}^\times / \{\pm 1\}$,
\item komplexní kořeny polynomu $z^8-1=0$ s násobením.
\end{enumerate}
}

\priklad{[11.25]} Nechť $G$ je grupa dolních trojúhelníkových matic $3 \times 3$ s jedničkami na diagonále a operací
násobení. 
\begin{enumerate}[label=(\roman*)] 
\item Ukažte, že $G \subseteq GL(3,\mathbb{R})$ je podgrupa a rozhodněte, zda je normální.
\item Určete centrum $Z(G) = \{ z \in G | \forall g \in G: zg=gz \}$.
\end{enumerate}

\priklad{[11.38, 11.41, 11.42] Podgrupy v symetrických grupách.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\cviceni{12.\ týden -- homomosfismy grup, kódy}{19.\ 5.}

\priklad{[11.48] Rozhodněte, zda předpis $\varphi$ zadává zobrazení, případně zda jde o homomorfismus grup
(se sčítáním) -- pak popište jádro/obraz a rozhodněte, zda je to surjekce či injekce:
\begin{enumerate}[label=(\roman*)] 
\item $\varphi: \mathbb{Z}_4 \times \mathbb{Z}_3 \to \mathbb{Z}_{12}$,
$\varphi([[a]_4,[b]_3) = [a-b]_{12}$,
\item $\varphi: \mathbb{Z}_4 \times \mathbb{Z}_3 \to \mathbb{Z}_{12}$,
$\varphi([[a]_4,[b]_3) = [6a+4b]_{12}$,
\item $\varphi: \mathbb{Z}_4 \times \mathbb{Z}_3 \to \mathbb{Z}_{12}$,
$\varphi([[a]_4,[b]_3) = [0]_{12}$.
\end{enumerate}
}

\priklad{[11.49] Rozhodněte, zda předpis $\varphi$ zadává zobrazení, případně zda jde o homomorfismus grup
($\mathbb{Z}_k$ se sčítáním a $\mathbb{C}^\ast$ s násobením) -- pak popište jádro/obraz a rozhodněte, zda je to surjekce či injekce:
\begin{enumerate}[label=(\roman*)] 
\item $\varphi: \mathbb{Z}_4 \to \mathbb{C}^\ast$, $\varphi([[a]_4) = i^a$,
\item $\varphi: \mathbb{Z}_5 \to \mathbb{C}^\ast$, $\varphi([[a]_5) = i^a$,
\item $\varphi: \mathbb{Z}_4 \to \mathbb{C}^\ast$, $\varphi([[a]_4) = (-i)^a$,
\item $\varphi: \mathbb{Z} \to \mathbb{C}^\ast$, $\varphi(a) = i^a$
\end{enumerate}
}


\priklad{[11.136] Uvažme $(5,3)$-kód nad $\mathbb{Z}_2$ generovaný polynomem $x^2+x+1$.
Vypište všechna kódová slova, najděte generující matici a matici kontroly parity.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\cviceni{13.\ týden -- kódování}{26.\ 5.}

\priklad{[11.138] Sedmibitové zprávu $a_0 \ldots a_6$ chápanou jako
$a_0+a_1x+\ldots +a_6x^6$ kódujeme polynomiálním kódem generivaným polynomem $p(x)=x^4+x+1$.
\begin{enumerate}[label=(\roman*)] 
\item Zakódujte zprávu $1100011$.
\item Obdrželi jste kód $10111010001$. Jaká byla posílaná zpráva za předpokladu, že k chybě 
došlo maximálně v jednom bitu?
\item Jaká byla zpráva v (ii) za předpokladu, že k chybě došlo právě na dvou bitech?
\end{enumerate}
}


\priklad{[11.141] Určete generující matici a matici kontroly parity $(7,2)$-kódu 
generovaného polynomem $x^5+x^4+x^2+1$. Dekódujte přijaté slovo $0010111$ 
(tj.\ určete poslanou dvoubitovou zprávu) za předpokladu,
že při přenosu došlo k nejmenšímu možnému počtu chyb.
}

\priklad{V lineárním $(7,4)$-kódu (tj.\ dálka zprávy před zakódováním je $4$) nad $\mathbb{Z}_2$
zadaném maticí 
$$
\begin{pmatrix}
0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1
\end{pmatrix}
$$
byla přijata zpráva $1010001$. Dekódujte ji za předpokladu, že při přenosu došlo
k nejmenšímu možnému počtu chyb.
}





\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%





\end{document}

