Test GR4

{thm}{Twierdzenie} {obs}[thm]{Obserwacja} {con}[thm]{Wniosek} {exrr}{Zadanie}

{

0mm

#1

10mm }{{ $◻$ }

}

{article} {../makraT}

0mm

Uzupelnij tytul

Zagadnienia Mini-Maksowe w grafach

10mm

Które z następujących zdań poprawnie opisują Rysunek Uzupelnic test matching|:

[!ht]

{test_1} { [Rysunek z pliku: test1.eps]}

} <wrongoption>Na Rysunku Uzupelnic test matching|.a oraz Uzupelnic test matching|.b zostały przedstawione minimalne pokrycia krawędziowe.} <rightoption>Na Rysunku Uzupelnic test matching|.a oraz Uzupelnic test matching|.b zostały przedstawione maksymalne skojarzenia.} <rightoption>Na Rysunku Uzupelnic test matching|.a zostało przedstawione minimalne pokrycie krawędziowe, a na Rysunku Uzupelnic test matching|.b maksymalne skojarzenie.} <wrongoption>Na Rysunku Uzupelnic test matching|.a zostało przedstawione maksymalne skojarzenie, a na Rysunku Uzupelnic test matching|.b skojarzenie doskonałe.}

Które z następujących zdań poprawnie opisują Rysunek Uzupelnic test 2|:

[!ht]

{test_2} { [Rysunek z pliku: test2.eps]}

}

<rightoption>Na Rysunku Uzupelnic test 2|.a oraz Uzupelnic test 2|.b zostały przedstawione minimalne pokrycia wierzchołkowe.} <wrongoption>Na Rysunku Uzupelnic test 2|.a oraz Uzupelnic test 2|.b zostały przedstawione zbiory niezależne.} <wrongoption>Na Rysunku Uzupelnic test 2|.a zostało przedstawione minimalne pokrycie wierzchołkowe, a na Rysunku Uzupelnic test 2|.b maksymalny zbiór niezależny.} <rightoption>Na Rysunku Uzupelnic test 2|.a zostało przedstawione pokrycie wierzchołkowe, a na Rysunku Uzupelnic test 2|.b zbiór niezależny.}

W $100$ -wierzchołkowym grafie spójnym $\mathbf{𝐆}$ posiadającym skojarzenie doskonałe:} <rightoption>moc maksymalnego skojarzenia wynosi $\nu \left(\mathbf{𝐆}\right)=50$ } <wrongoption>moc najliczniejszego zbioru niezależnego wynosi $\alpha \left(\mathbf{𝐆}\right)=50$ } <rightoption>moc minimalnego pokrycia krawędziowego wynosi $\rho \left(\mathbf{𝐆}\right)=50$ } <wrongoption>moc minimalnego pokrycia krawędziowego wynosi $\rho \left(\mathbf{𝐆}\right)=49$ }

W $1073$ -wierzchołkowym grafie spójnym $\mathbf{𝐆}$ o liczbie chromatycznej $\chi \left(\mathbf{𝐆}\right)=23$ :} <rightoption>moc najliczniejszego zbioru niezależnego wynosi $\alpha \left(\mathbf{𝐆}\right)\le 1051$ } <wrongoption>moc najliczniejszego zbioru niezależnego wynosi $\alpha \left(\mathbf{𝐆}\right)\le 1050$ } <wrongoption>istnieje pokrycie $23$ wierzchołkami} <rightoption>każde pokrycie wierzchołkowe ma co najmniej $24$ elementy}

Jeśli $M$ jest maksymalnym skojarzeniem w grafie $\mathbf{𝐆}$ , to:} <rightoption> $M$ zawiera się w jakimś minimalnym pokryciu krawędziowym} <wrongoption>istnieje maksymalny zbiór niezależny $A$ , dla którego każda krawędź z $M$ jest incydentna z którymś wierzchołkiem w $A$ } <rightoption>wierzchołki nieincydentne z żądną krawędzią z $M$ tworzą zbiór niezależny} <wrongoption> $M$ jest minimalnym pokryciem krawędziowym}

W $153$ -wierzchołkowym grafie dwudzielnym $\mathbf{𝐆}$ , w którym maksymalne skojarzenie ma $\nu \left(\mathbf{𝐆}\right)=73$ krawędzi:} <wrongoption>minimalne pokrycie wierzchołkowe ma moc $\tau \left(\mathbf{𝐆}\right)=80$ } <rightoption>minimalne pokrycie wierzchołkowe ma moc $\tau \left(\mathbf{𝐆}\right)=73$ } <rightoption>minimalne pokrycie krawędziowe ma moc $\rho \left(\mathbf{𝐆}\right)=80$ } <wrongoption>minimalne pokrycie krawędziowe ma moc $\rho \left(\mathbf{𝐆}\right)=73$ }

W każdym grafie prostym $\mathbf{𝐆}$ zachodzi:} <rightoption> $\nu \left(\mathbf{𝐆}\right)\le \tau \left(\mathbf{𝐆}\right)$ } <wrongoption> $\tau \left(\mathbf{𝐆}\right)\le \nu \left(\mathbf{𝐆}\right)$ } <wrongoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \nu\left( \mathbf{G} \right)+ \tau\left( \mathbf{G} \right)=\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert } } <rightoption> $\tau \left(\mathbf{𝐆}\right)\le 2\nu \left(\mathbf{𝐆}\right)$ }

22222222222222222222222222222222222222222222222222222

{article} {../makraT}

0mm

Uzupelnij tytul

Częściowe porządki

10mm

Relacja podzielności określona jako

$x\mid y$ wtw $\mathrm{\exists }zx\cdot z=y$

jest relacją częściowego porządku w zbiorze:} <wrongoption> liczb rzeczywistych $\mathbb{ℝ}$ <wrongoption> liczb wymiernych $\mathbb{\mathbb{Q}}$ <wrongoption> liczb całkowitych $\mathbb{\mathbb{Z}}$ <rightoption> liczb naturalnych $\mathbb{\mathbb{N}}$ <rightoption> liczb naturalnych nieparzystych

Relacja podzielności jest relacją liniowego porządku w zbiorze:} <rightoption> liczb naturalnych będących potęgami liczby $2$ <rightoption> liczb naturalnych będących potęgami liczby $6$ <rightoption> liczb naturalnych będących potęgami liczby $2$ lub $6$ <wrongoption> liczb naturalnych będących równocześnie potęgami liczby $2$ i $6$ <rightoption> $\{0,1\}$

Relacja inkluzji $\subseteq$ jest relacją częściowego porządku w zbiorze:} <rightoption> w zbiorze wszystkich podzbiorów zbioru liczb rzeczywistych $\mathbb{ℝ}$ <rightoption> w zbiorze wszystkich podzbiorów zbioru liczb wymiernych $\mathbb{\mathbb{Q}}$ <rightoption> w zbiorze wszystkich podzbiorów zbioru liczb całkowitych $\mathbb{\mathbb{Z}}$ postaci $[-k,k]$ <rightoption> w zbiorze wszystkich podzbiorów zbioru liczb całkowitych $\mathbb{\mathbb{Z}}$ postaci $[k,l]$ <rightoption> w zbiorze wszystkich podzbiorów zbioru liczb naturalnych $\mathbb{\mathbb{N}}$

Relacja inkluzji $\subseteq$ jest relacją liniowego porządku w zbiorze:} <rightoption> w zbiorze wszystkich podzbiorów zbioru liczb całkowitych $\mathbb{\mathbb{Z}}$ postaci $[0,k]$ <wrongoption> w zbiorze wszystkich podzbiorów zbioru liczb całkowitych $\mathbb{\mathbb{Z}}$ <rightoption> w zbiorze wszystkich podzbiorów zbioru liczb całkowitych $\mathbb{\mathbb{Z}}$ postaci $[-k,k]$ <wrongoption> w zbiorze wszystkich podzbiorów zbioru liczb całkowitych $\mathbb{\mathbb{Z}}$ postaci $[k,l]$ <wrongoption> w zbiorze wszystkich podzbiorów zbioru $\{0,1\}$

{Wiedząc, że $R,S\subseteq A\times A$ są relacjami częściowego porządku na zbiorze $A$ zaznacz prawdziwe zależności:} <rightoption> $R\cap S$ jest relacją częściowego porządku na zbiorze $A$ <wrongoption> $R\cup S$ jest relacją częściowego porządku na zbiorze $A$ <wrongoption> $R\circ S$ jest relacją częściowego porządku na zbiorze $A$ <rightoption> $R\circ R=R$ <wrongoption> $R=R^{\leftharpoonup }$

Zaznacz zdania prawdziwe:} <rightoption> W skończonym zbiorze częściowo uporządkowanym istnieje co najmniej jeden element minimalny. <rightoption> Jeśli w zbiorze częściowo uporządkowanym jest element najmniejszy, to jest on jedynym elementem minimalnym. <rightoption> W zbiorze liniowo uporządkowanym element minimalny o ile istnieje, jest elementem najmniejszym. <wrongoption> W zbiorze liniowo uporządkowanym nie każdy skończony niepusty podzbiór ma element najmniejszy i największy. <rightoption> W zbiorze częściowo uporządkowanym każdy skończony niepusty podzbiór ma elementy minimalne i maksymalne.

Zaznacz zdania prawdziwe:} <wrongoption> Porządek produktowy porządków liniowych jest zawsze porządkiem liniowym. <wrongoption> Każdy zbiór ograniczony z góry i z dołu ma kresy. <rightoption> Elementów minimalnych może w zbiorze uporządkowanym nie być wcale. <wrongoption> Kres górny w zbiorze uporządkowanym i ograniczenie górne -- to to samo. <rightoption> Porządek leksykograficzny jest zawsze liniowy.

Zaznacz zdania prawdziwe:} <rightoption> Każda relacja równoważności jest relacją symetryczną. <rightoption> Suma dowolnej rodziny relacji zwrotnych jest zwrotna. <wrongoption> Relacja porządku nie musi być relacją zwrotną. <wrongoption> Każda relacja przechodnia i zwrotna jest relacją symetryczną. <wrongoption> Relacja porządku musi być relacją symetryczną.

Zaznacz zdania prawdziwe:} <rightoption> Każdy zbiór jednoelementowy jest łańcuchem. <rightoption> W łańcuchu każde dwa elementy są porównywalne. <rightoption> Łańcuch jest zbiorem liniowo uporządkowanym. <wrongoption> Relacja częściowego porządku jest spójna. <rightoption> Jeśli relacja $R$ porządkuje częściowo zbiór $X$, to relacja $R^{-1}$ też częściowo porządkuje zbiór $X$.

Rozważamy zbiór $T=\{2,3,4,5,...13,14,15\}$ z relacją podzielności ograniczoną do elementów zbioru $T$. Zaznacz zdania prawdziwe:} <wrongoption> W zbiorze tym są dokładnie trzy łańcuchy trzyelementowe. <rightoption> W zbiorze tym są dokładnie cztery łańcuchy trzyelementowe. <wrongoption> W zbiorze tym nie ma łańcuchów trzyelementowych. <rightoption> Między innymi $3$ i $7$ są elementami minimalnymi. <rightoption> Między innymi $9$ i $15$ są elementami maksymalnymi.

Zaznacz zbiory częściowo uporządkowane:} <wrongoption> $({\mathbb{\mathbb{Z}}}_n,{\le }_1)$ , gdzie $x{\le }_{1}y$ w.t.w. $x+1=ymodn$ .} <rightoption> $\mathbf{𝐆}=(V,E)$ , gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathbf{G}={\sf TC}\left( \mathbf{H} \right)\cup\left\lbrace \left( x,x \right):x\in V \right\rbrace } , gdzie $H$ jest prostym acyklicznym grafem skierowanym.} <rightoption> $(\mathbb{\mathbb{N}},\le )$ , gdzie $x{\le }_{1}y$ w.t.w. istnieje $a\in \mathbb{\mathbb{N}}$ takie, że $x+a=y$ .} <wrongoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{G},\leq_2 \right) } , gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{G} } jest rodziną wszystkich skończonych nieizomorficznych grafów, zaś $\mathbf{𝐆}{\le }_2\mathbf{𝐇}$ w.t.w. w grafie $\mathbf{𝐇}$ istnie podgraf homeomorficzny do grafu $\mathbf{𝐆}$ .}

Zaznacz zdania poprawnie opisujące zbiór $X$ będący równocześnie łańcuchem oraz antyłańcuchem w zbiorze częściowo uporządkowanym:} <wrongoption>Nie istnieje taki zbiór $X$ .} <wrongoption>Zbiór $X$ jest pusty.} <rightoption>Zbiór $X$ jest co najwyżej jednoelementowy.} <wrongoption>Zbiór $X$ jest co najwyżej dwuelementowy.}

Jeśli $A$ jest maksymalnym antyłańcuchem w posecie $\mathbf{𝐏}=(P,\le )$ , to:} <rightoption>dowolny element $p\in P$ jest porównywalny z którymś elementem $a\in A$ , czyli $p\le a$ lub $a\le p$ } <wrongoption>jeśli $C\subseteq P$ jest łańcuchem o maksymalnym rozmiarze, to $C\cap A\ne \mathrm{\varnothing }$ } <wrongoption>istnieje łańcuch $C\subseteq P$ o maksymalnym rozmiarze taki, że $C\cap A\ne \mathrm{\varnothing }$ } <wrongoption>poset $\mathbf{𝐏}-A$ jest szerokości co najwyżej Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf width}\!\left( \mathbf{P} \right)-1 } }

Jeśli poset $\mathbf{𝐏}$ ma szerokość Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf width}\!\left( \mathbf{P} \right)=10 } , to:} <wrongoption>najliczniejszy łańcuch w posecie $\mathbf{𝐏}$ ma $10$ elementów} <rightoption>najliczniejszy antyłańcuch w posecie $\mathbf{𝐏}$ ma $10$ elementów} <wrongoption>da się pokryć $10$ antyłańcuchami} <rightoption>da się pokryć $10$ łańcuchami}

Jeśli poset $\mathbf{𝐏}$ ma szerokość Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf width}\!\left( \mathbf{P} \right)=11 } , a każdy jego łańcuch ma co najwyżej $9$ elementów, to:} <rightoption>poset $\mathbf{𝐏}$ ma co najwyżej $99$ elementów} <rightoption>poset $\mathbf{𝐏}$ ma co najwyżej $100$ elementów} <rightoption>poset $\mathbf{𝐏}$ ma co najmniej $19$ elementów} <wrongoption>poset $\mathbf{𝐏}$ ma co najmniej $20$ elementów}

Każdy $100$ -elementowy ciąg liczb rzeczywistych zawiera:} <wrongoption> $11$ -elementowy podciąg niemalejący lub $11$ -elementowy podciąg malejący} <rightoption> $10$ -elementowy podciąg niemalejący lub $12$ -elementowy podciąg malejący} <rightoption> $10$ -elementowy podciąg niemalejący lub $10$ -elementowy podciąg malejący} <wrongoption>żadna z pozostałych odpowiedzi nie jest poprawna}

Jeśli $X$ jest zbiorem $10$ -elementowym, to:} <rightoption>poset Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{P}\!\left( X \right),\subseteq \right) } ma szerokość $252$ } <wrongoption>poset Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{P}\!\left( X \right),\subseteq \right) } ma szerokość $210$ } <rightoption>poset Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{P}\!\left( X \right),\subseteq \right) } ma wysokość $11$ } <wrongoption>poset Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{P}\!\left( X \right),\subseteq \right) } ma wysokość $10$ }

Jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{R} } jest zbiorem wszystkich relacji równoważności na $10$ -elementowym zbiorze $X$ , to:} <rightoption>para Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{R},\subseteq \right) } jest zbiorem częściowo uporządkowanym} <rightoption>para Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{R},\subseteq \right) } jest kratą} <wrongoption>para Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{R},\subseteq \right) } jest zbiorem częściowo uporządkowanym o szerokości mniejszej niż szerokość posetu Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{P}\!\left( X \right),\subseteq \right) } } <wrongoption>Żadna z pozostałych odpowiedzi nie jest prawdziwa.}

33333333333333333333333333333333333333333333333333

{article} {../makraT}

0mm

Uzupelnij tytul

Własności podziałowe i Twierdzenie Ramsey'a

10mm

Komoda ma $10$ szuflad. Pierwsza jest w stanie pomieścić $1$ koszulę, druga $2$ i w ogólności $i$ -ta szuflada jest w stanie pomieścić $i$ koszul. Do przechowania jest $46$ koszul. Wtedy:} <wrongoption>nie da się pomieścić wszystkich koszul w komodzie} <wrongoption>wszystkie szuflady będą w pełni zapełnione} <rightoption>co najmniej jedna z szuflad będzie w pełni zapełniona} <rightoption>któraś szuflada może być pusta}

Graf o $524288$ wierzchołkach zawiera jako podgraf indukowany:} <rightoption>klikę ${{𝒦}}_9$ lub antyklikę ${{𝒜}}_9$ } <rightoption>klikę ${{𝒦}}_{10}$ lub antyklikę ${{𝒜}}_{10}$ } <wrongoption>klikę ${{𝒦}}_{512}$ lub antyklikę ${{𝒜}}_{512}$ } <wrongoption>klikę ${{𝒦}}_{1024}$ lub antyklikę ${{𝒜}}_{1024}$ }

Jeśli graf $\mathbf{𝐆}$ ma nieskończenie wiele wierzchołków, to:} <rightoption>istnieje liczba naturalna $n\in \mathbb{\mathbb{N}}$ taka, że graf $\mathbf{𝐆}$ zawiera jako podgraf indukowany klikę ${{𝒦}}_n$ lub antyklikę ${{𝒜}}_n$ } <rightoption>dla dowolnej liczby naturalnej $n\in \mathbb{\mathbb{N}}$ graf $\mathbf{𝐆}$ zawiera jako podgraf indukowany klikę ${{𝒦}}_n$ lub antyklikę ${{𝒜}}_n$ } <wrongoption>dla dowolnej liczby naturalnej $n\in \mathbb{\mathbb{N}}$ graf $\mathbf{𝐆}$ zawiera jako podgraf indukowany klikę ${{𝒦}}_n$ oraz antyklikę ${{𝒜}}_n$ } <rightoption>graf $\mathbf{𝐆}$ zawiera jako podgraf indukowany przeliczalną klikę ${{𝒦}}_{\mathbb{\mathbb{N}}}$ lub przeliczalną antyklikę ${{𝒜}}_{\mathbb{\mathbb{N}}}$ }

Dla dowolnych $n,m,p\in \mathbb{\mathbb{N}}$ istnieje liczba $q$ taka, że:} <rightoption>dla każdego zbioru $X$ o co najmniej $q$ elementach i dowolnego rozbicia Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_{n}\!\left( X \right)=\mathscr{A}_1\cup\ldots\cup\mathscr{A}_m } , istnieje $p$ -elementowy podzbiór $Y$ zbioru $X$ taki, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_{n}\!\left( Y \right)\subseteq \mathscr{A}_i } przy pewnym $i=1,\dots ,t$ } <rightoption>dla każdego zbioru $X$ o co najmniej $n$ elementach i dowolnego rozbicia Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_{r}\!\left( X \right)=\mathscr{A}_1\cup\ldots\cup\mathscr{A}_t } , istnieje $q$ -elementowy podzbiór $Y$ zbioru $X$ taki, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_{r}\!\left( Y \right)\subseteq \mathscr{A}_i } przy pewnym $i=1,\dots ,t$ } <wrongoption>dla każdego zbioru $X$ o co najmniej $q$ elementach i dowolnego rozbicia Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_{n}\!\left( X \right)=\mathscr{A}_1\cup\ldots\cup\mathscr{A}_m } , istnieje $\lceil q/m\rceil$ -elementowy podzbiór $Y$ zbioru $X$ taki, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_{n}\!\left( Y \right)\subseteq \mathscr{A}_p } } <wrongoption>Żadna z pozostałych własności nie musi zachodzić}

Liczba Ramseya Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}\!\left( 3,4 \right) } to:} <wrongoption> $6$ } <rightoption> $9$ } <wrongoption> $14$ } <rightoption>co najwyżej $10$ }

Liczba Ramseya Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}_{r}\!\left( 4,4 \right) } spełnia:} <rightoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}_{r}\!\left( 4,4 \right)\leq {\sf R}_{{r-1}}\!\left( {\sf R}_{r}\!\left( 3,4 \right),{\sf R}_{r}\!\left( 4,3 \right) \right)+1 } } <wrongoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}_{r}\!\left( 4,4 \right)\leq {\sf R}_{{r-1}}\!\left( {\sf R}_{r}\!\left( 3,4 \right),{\sf R}_{r}\!\left( 4,3 \right) \right) } } <wrongoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}_{r}\!\left( 4,4 \right)\leq {\sf R}_{{r-1}}\!\left( {\sf R}_{r-1}\!\left( 3,4 \right),{\sf R}_{r-1}\!\left( 4,3 \right) \right)+1 } } <wrongoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}_{r}\!\left( 4,4 \right)\leq {\sf R}_{{r-1}}\!\left( {\sf R}_{r-1}\!\left( 3,4 \right),{\sf R}_{r-1}\!\left( 4,3 \right) \right) } }

Liczby Ramseya Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}\!\left( n,n \right) } spełniają:} <rightoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle n2^{n/2}\left( \frac{1}{e\sqrt{2}}-{\sf o}\!\left( 1 \right) \right)\leq{\sf R}\!\left( n,n \right) } } <wrongoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle n2^{2n}\left( \frac{1}{e\sqrt{2}}-{\sf o}\!\left( 1 \right) \right)\leq{\sf R}\!\left( n,n \right) } } <rightoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}\!\left( n,n \right)\geq { 2n-2 \choose n-1 } } } <wrongoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}\!\left( n,n \right)\geq { 2n \choose n } } }

444444444444444444444444444444444444444444444444

{article} {../makraT}

0mm

Uzupelnij tytul

Elementy teorii grup

10mm

Zaznacz struktury będące grupami:} <rightoption> $({\mathbb{\mathbb{Z}}}_4,+,0)$ <wrongoption> $({\mathbb{\mathbb{Z}}}_4^{*},\cdot ,1)$ <rightoption> $({\mathbb{\mathbb{Z}}}_5,+,0)$ <rightoption> $({\mathbb{\mathbb{Z}}}_5^{*},\cdot ,1)$

Dla dowolnych elementów $x,y$ pewnej grupy element $x^{-1}y{y}^{-1}yx{y}^{-1}$ można tez zapisać jako:} <rightoption> $x^{-1}yx{y}^{-1}$ <wrongoption> $1$ <rightoption> $x^{-1}zz{z}^{-1}{z}^{-1}yx{y}^{-1}$, gdzie $z$ jest dowolnym elementem grupy <wrongoption> $x^{-1}{y}^{-1}x{y}^{-1}$

W dowolnej grupie skończonej, jeśli $x^{15}=1$ i $x^{25}=1$, to} <wrongoption> $x$ jest rzędu $5$ <rightoption> $x^5=1$ <rightoption> $x^{30}=1$ <rightoption> $x^{35}=1$

Grupa $({\mathbb{\mathbb{Z}}}_{12},+,0)$} <rightoption> ma podgrupę $1$-elementową <rightoption> ma podgrupę $2$-elementową <rightoption> ma podgrupę $3$-elementową <rightoption> ma podgrupę $4$-elementową

Niech $H_0,H_1$ będą podgrupami grupy $\mathbf{𝐆}$. Wtedy:} <rightoption> $H_0\cap H_1$ jest podgrupą grupy $\mathbf{𝐆}$ <wrongoption> $H_0\cup H_1$ jest podgrupą grupy $\mathbf{𝐆}$ <rightoption> $H_0\cap H_1$ jest podgrupą grupy $\mathbf{𝐆}$, o ile $H_0\subseteq H_1$ <rightoption> $H_0\cup H_1$ jest podgrupą grupy $\mathbf{𝐆}$, o ile $H_0\subseteq H_1$

Wskaż prawdziwe własności grup $({\mathbb{\mathbb{Z}}}_n,+,0)$ dla $n>1$:} <wrongoption> grupa $({\mathbb{\mathbb{Z}}}_n,+,0)$ jest cykliczną wtedy i tylko wtedy, gdy $n$ jest pierwsza <rightoption> każda grupa postaci $({\mathbb{\mathbb{Z}}}_n,+,0)$ jest cykliczna <rightoption> jeśli grupa ${\mathbb{\mathbb{Z}}}_n\times {\mathbb{\mathbb{Z}}}_m$ jest cykliczna, to $m$ i $n$ są względnie pierwsze <rightoption> grupa ${\mathbb{\mathbb{Z}}}_n\times {\mathbb{\mathbb{Z}}}_m$ jest cykliczna o ile $m$ i $n$ są względnie pierwsze

Wskaż pary izomorficznych grup, gdzie ${\mathbb{\mathbb{Z}}}_n$ jest grupą addytywną $({\mathbb{\mathbb{Z}}}_n,+,0)$:} <rightoption> ${\mathbb{\mathbb{Z}}}_2\times {\mathbb{\mathbb{Z}}}_3$ i ${\mathbb{\mathbb{Z}}}_3\times {\mathbb{\mathbb{Z}}}_2$ <rightoption> ${\mathbb{\mathbb{Z}}}_2\times {\mathbb{\mathbb{Z}}}_3$ i ${\mathbb{\mathbb{Z}}}_6$ <wrongoption> ${\mathbb{\mathbb{Z}}}_3\times {\mathbb{\mathbb{Z}}}_{33}$ i ${\mathbb{\mathbb{Z}}}_{99}$ <wrongoption> ${\mathbb{\mathbb{Z}}}_2\times {\mathbb{\mathbb{Z}}}_2$ i ${\mathbb{\mathbb{Z}}}_4$

Czy w dowolnej grupie postaci $({\mathbb{\mathbb{Z}}}_n,+,0)$ elementów rzędu $7$ jest $0$ lub $6$?} <rightoption> tak <rightoption> tak, jeśli dodatkowo $n$ jest wielokrotnkością $7$ <rightoption> tak, jeśli dodatkowo $n\perp 7$ <wrongoption> żadna z pozostałych

Dla podgrupy $\mathbf{𝐇}$ skończonej grupy $\mathbf{𝐆}$ zachodzi:} <rightoption> $\left|gH\right|=\left|Hg\right|$, jeśli $g\in H$ <rightoption> $gH=Hg$, jeśli $g\in H$ <rightoption> $\left|gH\right|=\left|Hg\right|$, dla dowolnego $g\in G$ <wrongoption> $gH=Hg$, dla dowolnego $g\in G$

Jeśli element $x$ grupy $\mathbf{𝐆}$ ma rząd $n$, to $x^{3n}$ ma rząd:} <rightoption> $1$ <wrongoption> $3$ <wrongoption> $n$ <wrongoption> żadne z pozostałych

555555555555555555555555555555555555555555555555

{article} {../makraT}

0mm

Uzupelnij tytul

Twierdzenie Pólya

10mm

Orbita $Gx$ w G-zbiorze $(G,X)$ }

<rightoption>to zbiór elementów zbioru  $X$  postaci  $g\left(x\right)$ , gdzie  $g\in G$ .}
<rightoption>jest równa  $Gy$  jeśli tylko istnieje  $g\in G$  takie, że  $g\left(x\right)=y$ .}
<wrongoption>jest równa  $Gy$  dla dowolnego  $y\in X$ .}
<wrongoption>jest równa  $Gy$  jeśli tylko  $x\circ y=id$ .}

Stabilizator $G_x$ w G-zbiorze $(G,X)$ } <wrongoption>to szczególny przypadek orbity.} <wrongoption>jest równoliczny z orbitą $Gx$ .} <rightoption>spełnia warunek $\left|G_x\right|\cdot \left|Gx\right|=\left|G\right|$ .} <rightoption>to zbiór permutacji $g\in G$ takich, że $g\left(x\right)=x$ .}

W G-zbiorze $(G,X)$ zachodzi:} <rightoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left\vert \left\lbrace Gx :x \in G \right\rbrace \right\vert=\frac{1}{\left\vert G \right\vert}\sum_{g\in G} \left\vert {\sf F}\left( g \right) \right\vert } .} <rightoption> $\bigcup _{x\in X}Gx=X$ .} <rightoption> $\left|G{x}_1\right|=\left|G{x}_2\right|$ dla wszystkich $x_1,x_2\in X$ .} <wrongoption> $G{x}_1=G{x}_2$ dla wszystkich $x_1,x_2\in X$ .}

Dla G-zbioru $(G,X)$ dwa kolorowania ${\omega }_1,{\omega }_2$ są izomorficzne wtedy i tylko wtedy, gdy} <rightoption>istnieje permutacja $g\in G$ taka, że ${\omega }_1\left(g\left(x\right)\right)={\omega }_2\left(x\right)$ dla dowolnych $x\in X$ .} <wrongoption>istnieje permutacja $g$ zbioru $X$ taka, że ${\omega }_1\left(g\left(x\right)\right)={\omega }_2\left(x\right)$ dla dowolnych $x\in X$ } <rightoption>istnieje permutacja $g\in G$ taka, że $\hat{g}\left({\omega }_1\right)={\omega }_2$ .} <wrongoption> ${\omega }_1={\omega }_2$ .}

Indeks grupy permutacji wszystkich możliwych obrotów $3$ -wymiarowej kostki to:} <wrongoption> $\frac{1}{21}(x_1^8+8x_1^2{x}_3^2+6x_2^4+6x_4^2)$ } <wrongoption> $\frac{1}{12}(x_1^8+8x_1^2{x}_3^2+9x_2^4+6x_4^2)$ } <rightoption> $\frac{1}{24}(x_1^8+8x_1^2{x}_3^2+9x_2^4+6x_4^2)$ } <wrongoption>żadna z pozostałych.}

Liczba nieizomorficznych kolorowań trzema barwami ścianek sześcianu foremnego to:}

<wrongoption>54}
<rightoption>57}
<wrongoption>1368}
<wrongoption>żadna z pozostałych.}

Liczba nieizomorficznych kolorowań ścian sześcianu takich, że $4$ ściany są białe, a $2$ czarne to:}

<wrongoption>1}
<rightoption>2}
<wrongoption>24}
<wrongoption>48}

666666666666666666666666666666666666666666666666

{article} {../makraT}

0mm

Uzupelnij tytul

Ciała skończone

10mm

Dla dowolnego $x$ w pierścieniu $\mathbf{𝐑}$

$x\cdot 0=x\cdot (0+0)=x\cdot 0+x\cdot 0$

czyli

$0=x\cdot 0.$

W przedstawionym rozumowaniu: } <wrongoption> pierwsza równość jest błędna <wrongoption> druga równość jest błędna <wrongoption> implikacja dająca trzecią równość jest błędna <rightoption> żadne z powyższych

Zbiór $M_{3\times 3}$ wszystkich macierzy wymiaru $3\times 3$ wypełnionych liczbami całkowitymi wraz z dodawaniem i mnożeniem macierzy jest:} <rightoption> pierścieniem <wrongoption> pierścieniem przemiennym <wrongoption> pierścieniem bez dzielników zera <wrongoption> ciałem

Dla wielomianów $a(x),b(x)$ nad pierścieniem $\mathbf{𝐑}$:} <wrongoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf deg}(a(x)\cdot b(x))={\sf deg}(a(x))+{\sf deg}(b(x))} <rightoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf deg}(a(x)+b(x))\leqslant\max\left( {{\sf deg}(a(x))},{{\sf deg}(b(x))} \right)} <rightoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf deg}(a(x)+b(x))\leqslant{\sf deg}(a(x))+{\sf deg}(b(x))} <wrongoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf deg}(a(x)\cdot b(x))\leq{\sf deg}(a(x))\cdot{\sf deg}(b(x))}

Jeśli $1$ jest największym wspólnym dzielnikiem wielomianów $a(x)$ i $b(x)$ nad ${\mathbb{\mathbb{Z}}}_3$, to ich największym wspólnym dzielnikiem jest także:} <wrongoption> $0$ <rightoption> $2$ <wrongoption> $x+1$ <wrongoption> żaden z pozostałych

W pierścieniu wielomianów nad ${\mathbb{\mathbb{Z}}}_3$ ideał główny generowany przez $x^2+2$ zawiera:} <rightoption> $0$ <wrongoption> $x$ <wrongoption> $2x^2+2$ <rightoption> $2x^3+x$

Dla dowolnego $p(x)$ nierozkładalnego wielomianu nad ciałem $\mathbf{𝐅}$:} <wrongoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf deg}(p(x))\leq \left\vert F \right\vert} <wrongoption> $p(x)$ jest odwracalny, <rightoption> jeśli $p(x)=a(x)b(x)$, to Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf deg}(a(x))=0} lub Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf deg}(b(x))=0} <rightoption> jeśli $p(x)|a(x)b(x)$, to $p(x)|a(x)$ lub $p(x)|b(x)$

Wskaż wielomiany nierozkładalne nad ${\mathbb{\mathbb{Z}}}_3$} <rightoption> $2x+1$ <rightoption> $2x^3+x^2+x+2$ <rightoption> $x^2+2$ <wrongoption> $x^2+1$

Dla $p(x)$ wielomianu nad ciałem $\mathbf{𝐅}$ jeśli $(x-c{)}^2|p(x)$ to:} <rightoption> $p(c)=0$ <wrongoption> $p(x)=(x-c{)}^{2}q(x)$ i $q(c)=0$, dla pewnego wielomianu $q(x)$ <rightoption> $p(x)=(x-c)q(x)$ i $q(c)=0$, dla pewnego wielomianu $q(x)$ <rightoption> $p(x)=(x-c)q(x)$ i $x-c|q(x)$, dla pewnego wielomianu $q(x)$

Stopień dowolnego niezerowego elementu ciała ${\mathbb{\mathbb{Z}}}_p$ to:} <wrongoption> $0$ <rightoption> $1$ <wrongoption> $p-1$ <wrongoption> $p$

Istnieje ciało o liczności:} <rightoption> $8$ <rightoption> $9$ <wrongoption> $10$ <rightoption> $11$

77777777777777777777777777777777777777777777777777777777777

{article} {../makraT}

0mm

Uzupelnij tytul

Zastosowania teorii liczb w kryptografii

10mm

Dla małych wartości użytych liczb pierwszych łatwo można złamać RSA. Jeśli $(35,5)$ jest kluczem publicznym RSA to kluczem dekodującym jest:} <wrongoption> $(35,3)$ <rightoption> $(35,5)$ <wrongoption> $(35,7)$ <wrongoption> żaden z pozostałych

Załóżmy, że $(35,11)$ jest naszym kluczem dekodującym w kryptosystemie RSA. Otrzymaliśmy jednostkę szyfrogramu o wartości $5$. Wartość zdekodowanej jednostki to:} <wrongoption> $3$ <wrongoption> $5$ <rightoption> $10$ <wrongoption> $11$

Niech $n=pq$ dla pewnych liczb pierwszych $p\ne q$ oraz niech $n\perp e$ dla pewnego $e$. Wtedy:} <rightoption> znany jest algorytm wielomianowy, który mając na wejściu $p$ i $q$ liczy $\phi (n)$ <rightoption> znany jest algorytm wielomianowy, który mając na wejściu $n$ i $\phi (n)$ liczy $p$ i $q$ <wrongoption> znany jest algorytm wielomianowy, który mając na wejściu $n$ i $e$ wylicza $d$ takie, że $ed{\equiv }_{\phi (n)}1$ <rightoption> znany jest algorytm wielomianowy, który mając na wejściu $n,\phi (n)$ i $e$ liczy $d$ spełniające $ed{\equiv }_{\phi (n)}1$

Jeśli liczba $n$ przeszła $k$ testów Fermata, to:} <wrongoption> $n$ jest złożona z prawdopodobieństwem $\frac{1}{2^k}$ <wrongoption> $n$ jest pierwsza z prawdopodobieństwem $\frac{1}{2^k}$ <wrongoption> $n$ jest liczbą Carmichaela z prawdopodobieństwem $\frac{1}{2^k}$ <rightoption> żadna z pozostałych

Liczba Carmichaela:} <rightoption> przechodzi test Fermata dla dowolnie wylosowanej podstawy <rightoption> jest iloczynem przynajmniej trzech liczb pierwszych <wrongoption> mogą być parzyste <wrongoption> mogą być podzielne przez $9$

Niech $t$ będzie liczbą nieparzystą oraz $n=2^{s}t$, gdzie $s\ge 1$. Jeśli $n$ jest silnie pseudopierwsza przy podstawie $b$ to:} <rightoption> $b^{n-1}{\equiv }_{n}1$ <wrongoption> istnieje $0⩽r<s$ takie, że $b^{2^{r}t}{\equiv }_n-1$ <rightoption> $n$ jest pseudopierwsza przy podstawie $b$ <wrongoption> jeśli $b^{2^{r}t}{\equiv }_{n}1$ dla pewnego $r>0$ to $b^{2^{r-1}t}{\equiv }_n-1$

Jeśli liczba $n$ przeszła $k$ testów Millera-Rabina to:} <rightoption> $n$ jest złożona z prawdopodobieństwem co najwyżej $\frac{1}{4^k}$ <wrongoption> $n$ jest pierwsza z prawdopodobieństwem co najwyżej $\frac{1}{4^k}$ <wrongoption> $n$ jest pierwsza, o ile prawdziwa jest Uogólniona Hipoteza Riemanna <wrongoption> żadna z pozostałych