Test GR4: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
 
(Nie pokazano 62 pośrednich wersji utworzonych przez tego samego użytkownika)
Linia 1: Linia 1:
5555555555555555555555555555555555555555 Logika


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


{


0mm


'''#1'''
10101010101010101010101010101010101010101010101010 Logika
10mm }{{ <math>\displaystyle \square </math> }
 
}
 
{article}
{../makraT}
 
0mm
{| border=1
|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
|-
| '''Współczynniki dwumianowe'''
|-
|
 
|}
 
10mm
 
<quiz>Zależność <math>\displaystyle {n\choose0}-{n\choose1}+\ldots+(-1)^n{n\choose n}=0</math>
zachodzi dla:}
<rightoption>  wszystkich liczb naturalnych <math>\displaystyle n</math>
<wrongoption> tylko skończenie wielu liczb naturalnych <math>\displaystyle n</math>
<wrongoption> żadnej liczby naturalnej <math>\displaystyle n</math>
<rightoption>  wszystkich, poza skończenie wieloma liczbami naturalnymi <math>\displaystyle n</math>
</quiz>
 
<quiz>Suma elementów <math>\displaystyle n</math>-tego wiersza Trójkąta Pascala
bez obu wartości brzegowych to:}
 
<wrongoption> <math>\displaystyle 2^n</math>.
<rightoption>  <math>\displaystyle 2^{n}-2</math>.
<rightoption>  <math>\displaystyle \sum_{i=1}^n{n\choose i}-1</math>.
<wrongoption> <math>\displaystyle {2n\choose n}</math>.
</quiz>
 
<quiz>Współczynnik przy wyrazie <math>\displaystyle x^n</math> w rozwinięciu dwumianu <math>\displaystyle (x+2)^{2n}</math> to:}
<wrongoption> <math>\displaystyle {2n\choose n}</math>.
<wrongoption> <math>\displaystyle 2^n{n\choose2}</math>.
<rightoption>  <math>\displaystyle {2n\choose n}2^n</math>.
<wrongoption> <math>\displaystyle {2n\choose n}2^{2n}</math>.
</quiz>
 
<quiz><math>\displaystyle {-1\choose k}</math> dla <math>\displaystyle k\geqslant0</math> jest równe:}
<wrongoption> <math>\displaystyle 0</math>.
<wrongoption> <math>\displaystyle 1</math>.
<wrongoption> <math>\displaystyle (-1)^k</math>.
<rightoption>  <math>\displaystyle (-1)^{k+1}</math>
</quiz>
 
<quiz>Suma <math>\displaystyle \sum_{i=0}^n2^i{n\choose i}</math> wynosi}
<wrongoption> <math>\displaystyle 2^n</math>.
<rightoption>  <math>\displaystyle 3^n</math>.
<wrongoption> <math>\displaystyle (n+2)^n</math>.
<wrongoption> <math>\displaystyle {2n\choose n}</math>.
</quiz>
 
<quiz>Liczba nieporządków na zbiorze <math>\displaystyle 3</math>-elementowym to:}
<wrongoption> <math>\displaystyle 1</math>.
<rightoption>  <math>\displaystyle 2</math>.
<wrongoption> <math>\displaystyle 3</math>.
<wrongoption> <math>\displaystyle 6</math>.
</quiz>
 
<quiz><math>\displaystyle {n\choose a,b,0,\ldots,0}</math> gdzie <math>\displaystyle a+b=n</math> to:}
<rightoption>  <math>\displaystyle {n\choose a}</math>.
<rightoption>  <math>\displaystyle {n\choose b}</math>.
<wrongoption> <math>\displaystyle {n\choose a+b}</math>.
<wrongoption> <math>\displaystyle {n+a+b\choose a+b}</math>.
</quiz>
 
<quiz>Na ile sposobów z grupy <math>\displaystyle 5n</math> osób,
złożonej z <math>\displaystyle 3n</math> mężczyzn i <math>\displaystyle 2n</math> kobiet,
można wybrać <math>\displaystyle n</math>-kobiet i <math>\displaystyle n</math>-mężczyzn,
i dodatkowo z niewybranych mężczyzn wyznaczyć przywódcę?}
<wrongoption> <math>\displaystyle \left( {5n\choose 3n}{3n\choose n}+{5n\choose 2n}{2n\choose n} \right)\cdot 2n</math>.
<rightoption>  <math>\displaystyle {3n\choose n}{2n\choose n}\cdot 2n</math>.
<wrongoption> <math>\displaystyle \left( {3n\choose n}+{2n\choose n} \right)\cdot 2n</math>.
<wrongoption> <math>\displaystyle {3n\choose n}{2n\choose n}\cdot 3n</math>.
</quiz>
 
<quiz>Suma <math>\displaystyle {0\choose7}+{1\choose7}+{2\choose7}+{3\choose7}+{4\choose7}+{5\choose7}+{6\choose7}+{7\choose7}</math> to:}
<wrongoption> <math>\displaystyle 0</math>.
<wrongoption> <math>\displaystyle {8\choose7}</math>.
<wrongoption> <math>\displaystyle {7\choose8}</math>.
<rightoption>  <math>\displaystyle {8\choose8}</math>.
</quiz>
 
<quiz>Współczynnik przy wyrazie <math>\displaystyle x^my^n</math> w rozwinięciu dwumianu <math>\displaystyle (x+y)^{m+n}</math> to:}
<rightoption>  <math>\displaystyle {m+n\choose m}</math>.
<rightoption>  <math>\displaystyle {m+n\choose n}</math>.
<wrongoption> <math>\displaystyle {m\choose n}</math>.
<wrongoption> <math>\displaystyle \sum_{i=0}^m{m+n\choose i}</math>.
</quiz>
 
66666666666666666666666666666
 
{article}
{../makraT}
 
0mm
{| border=1
|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
|-
| '''Permutacje i podziały'''
|-
|
 
|}
 
10mm
 
<quiz>Niech <math>\displaystyle n_{\pi},n_{\sigma},n_{\rho}</math> będą kolejno liczbami permutacji w <math>\displaystyle S_7</math>
tego samego typu co, odpowiednio,
<math>\displaystyle \pi=(14)(26)(357)</math>, <math>\displaystyle \sigma=(1357)(246)</math>, <math>\displaystyle \rho=(12)(34)(56)(7)</math>. Wtedy:}
<rightoption>  <math>\displaystyle n_{\pi}\leqslant n_{\tau}\leqslant n_{\rho}</math>
<rightoption>  <math>\displaystyle n_{\tau}\leqslant n_{\pi}\leqslant n_{\rho}</math>
<wrongoption> <math>\displaystyle n_{\rho}\leqslant n_{\pi}\leqslant n_{\tau}</math>
<wrongoption> <math>\displaystyle n_{\pi}\leqslant n_{\rho}\leqslant n_{\tau}</math>
</quiz>
 
<quiz>Dla sprzężonych permutacji <math>\displaystyle \pi,\sigma\in S_{13}</math> zachodzi:}
<rightoption>  <math>\displaystyle \pi</math> i <math>\displaystyle \sigma</math> mają tyle samo cykli <math>\displaystyle 4</math>-elementowych
<wrongoption> elementy <math>\displaystyle 1</math> i <math>\displaystyle 2</math> albo są w tym samym cyklu w obu permutacjach,
    albo nie są w tym samym cyklu w obu permutacjach
<rightoption>  <math>\displaystyle \pi</math> i <math>\displaystyle \sigma</math> mają ten sam typ
<rightoption>  <math>\displaystyle \pi</math> i <math>\displaystyle \sigma</math> mają ten sam znak
</quiz>
 
<quiz>Dla <math>\displaystyle n\geqslant 2</math>,
    podziałowa liczba Stirlinga  <math>\displaystyle \left\{\begin{array} {c}n\\ 2\end{array} \right\}</math> wynosi:}
<wrongoption> <math>\displaystyle \sum_{k=1}^{n-1}{n\choose k}k!=\sum_{k=1}^{n-1}\frac{n!}{k!}</math>
<wrongoption> <math>\displaystyle n!\sum_{k=1}^{n-1}\frac{1}{k(n-k)}</math>
<wrongoption> <math>\displaystyle n!\sum_{k=1}^{n-1}\frac{1}{k(n-k)}</math>
<rightoption>  <math>\displaystyle \frac{n!}{2}\sum_{k=1}^{n-1}\frac{1}{k(n-k)}</math>
</quiz>
 
<quiz>Średnia liczba cykli permutacji <math>\displaystyle n</math>-elementowej
(czyli stosunek sumarycznej liczby cykli we wszystkich permutacjach <math>\displaystyle n</math>-elementowych
do liczby cykli <math>\displaystyle n</math>-elementowych) to:}
<wrongoption> <math>\displaystyle 2n</math>
<wrongoption> <math>\displaystyle \left\lfloor \frac{n}{\lg{n}} \right\rfloor+1</math>
<rightoption>  <math>\displaystyle \sum_{k=1}^n \frac{1}{k}</math>
<wrongoption> <math>\displaystyle \frac{n}{2}</math>
</quiz>
 
<quiz>Podziałowa liczba Stirlinga<math>\displaystyle \left\{\begin{array} {c}7\\ 4\end{array} \right\}</math> wynosi}
<wrongoption> <math>\displaystyle 90</math>
<wrongoption> <math>\displaystyle 140</math>
<wrongoption> <math>\displaystyle 301</math>
<rightoption>  <math>\displaystyle 350</math>
</quiz>
 
<quiz>Jednomian <math>\displaystyle x^n</math> jest równy:}
<rightoption>  <math>\displaystyle \sum_i\left\{\begin{array} {c}n\\ i\end{array} \right\}x^{\underline{i}}</math>
<wrongoption> <math>\displaystyle B_nx^{\underline{n}}</math>, gdzie <math>\displaystyle B_n</math> jest <math>\displaystyle n</math>-tą liczbą Bella
<wrongoption> <math>\displaystyle \sum_i\left[\begin{array} {c}n\\ i\end{array} \right]x^{\overline{i}}</math>
<rightoption>  <math>\displaystyle \sum_i\left\{\begin{array} {c}n\\ i\end{array} \right\}(-1)^{n-i}x^{\overline{i}}</math>
</quiz>
 
<quiz>Na ile sposobów można rozłożyć <math>\displaystyle a</math> rozróżnialnych obiektów
do dokładnie <math>\displaystyle b</math> rozróżnialnych szuflad, tak by każda szufladka była niepusta?}
<wrongoption> <math>\displaystyle b^a</math>
<wrongoption> <math>\displaystyle \left\{\begin{array} {c}a\\ b\end{array} \right\}</math>
<rightoption>  <math>\displaystyle b!\left\{\begin{array} {c}a\\ b\end{array} \right\}</math>
<wrongoption> <math>\displaystyle {a-1\choose b-1}</math>
</quiz>
 
<quiz>Na ile sposobów można rozłożyć <math>\displaystyle a</math> nierozróżnialnych obiektów
do co najwyżej <math>\displaystyle b</math> rozróżnialnych szuflad?}
<wrongoption> <math>\displaystyle {a-1\choose b-1}</math>
<rightoption>  <math>\displaystyle {b+a-1\choose b-1}</math>
<wrongoption> <math>\displaystyle \left\{\begin{array} {c}a\\ b\end{array} \right\}</math>
<wrongoption> <math>\displaystyle \sum_{i=1}^b\left\{\begin{array} {c}a\\ i\end{array} \right\}</math>
</quiz>
 
<quiz>Gdy <math>\displaystyle P(n,k)</math> jest liczbą rozkładów liczby <math>\displaystyle n</math>
na sumy dokładnie <math>\displaystyle k</math> nieujemnych całkowitych składników,
to <math>\displaystyle \lim_{n\rightarrow\infty}\frac{P(n,k)}{n^k}</math> wynosi:}
<rightoption>  <math>\displaystyle 0</math>
<wrongoption> <math>\displaystyle \frac{1}{k!(k-1)!}</math>
<wrongoption> <math>\displaystyle \frac{1}{k}</math>
<wrongoption> <math>\displaystyle 1</math>
</quiz>
 
<quiz>Na ile sposobów można podzielić zbiór <math>\displaystyle a</math> elementowy na <math>\displaystyle b+c</math> bloków,
przy czym <math>\displaystyle b</math> bloków jest wyróżnionych?}
<rightoption>  <math>\displaystyle \left\{\begin{array} {c}a\\ b+c\end{array} \right\}{b+c\choose b}</math>
<rightoption>  <math>\displaystyle \sum_k{a\choose k}\left\{\begin{array} {c}k\\ b\end{array} \right\}\left\{\begin{array} {c}a-k\\ c\end{array} \right\}</math>
<wrongoption> <math>\displaystyle \left\{\begin{array} {c}a\\ b\end{array} \right\}\left\{\begin{array} {c}a-b\\ c\end{array} \right\}</math>
<wrongoption> <math>\displaystyle \left\{\begin{array} {c}a\\ b+c\end{array} \right\}b!</math>
</quiz>
 
-------------------------------------------------
 
777777777777777777777777777777777777777777777777777777777
 
{article}
{../makraT}
 
0mm
{| border=1
|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
|-
| '''Funkcje tworzące'''
|-
|
 
|}
 
10mm
 
<quiz>Na ile sposobów można rozmienić  <math>\displaystyle 25 </math>  centów za pomocą monet  <math>\displaystyle 1 </math> ,  <math>\displaystyle 5 </math> ,  <math>\displaystyle 10 </math> 
oraz  <math>\displaystyle 25 </math>  centowych?}
<wrongoption> <math>\displaystyle 6 </math> }
<wrongoption> <math>\displaystyle 12 </math> }
<rightoption> <math>\displaystyle 13 </math> }
<wrongoption> <math>\displaystyle 49 </math> }
</quiz>
 
<quiz>Funkcja tworząca postaci  <math>\displaystyle G\!\left( x \right)=g_0+g_1x+g_2x^2+g_3x^3+\ldots </math>
ma odwrotną względem mnożenia (splotu),
tzn. istnieje funkcja tworząca  <math>\displaystyle U\!\left( x \right) </math>  taka,
że  <math>\displaystyle U\!\left( x \right)G\!\left( x \right)=1 </math>  }
<wrongoption>jeśli  <math>\displaystyle g_0\neq 1 </math> }
<rightoption>jeśli  <math>\displaystyle g_0\neq 0 </math> }
<rightoption>jeśli wszystkie  <math>\displaystyle g_i\neq0 </math> }
<rightoption>wtedy i tylko wtedy, gdy  <math>\displaystyle g_0\neq0 </math> }
</quiz>
 
<quiz>Funkcja  <math>\displaystyle G\!\left( x \right) </math>  spełniająca
<math>\displaystyle G\!\left( x \right)=\left( \sum_{n=0}^{\infty}x^n \right)\cdot\left( 1+xG\!\left( x \right) \right) </math>
jest funkcją tworzącą:}
<wrongoption>ciągu  <math>\displaystyle 1,1,2,4,8,16,32,\ldots, 2^{n-1},\dots </math> }
<rightoption>ciągu geometrycznego  <math>\displaystyle g_n=2^n </math> }
<wrongoption>nie ma takiego ciągu}
<wrongoption>nie istnieje taka funkcja tworząca}
</quiz>
 
<quiz>Funkcja  <math>\displaystyle G\!\left( x \right) </math>  spełniająca
<math>\displaystyle G\!\left( x \right)=G'\!\left( x \right) </math>  oraz  <math>\displaystyle G\!\left( 0 \right)=1 </math>
jest funkcją tworzącą ciągu:}
<wrongoption> <math>\displaystyle g_n=\frac{1}{n} </math> }
<rightoption> <math>\displaystyle g_n=\frac{1}{n!} </math> }
<wrongoption> <math>\displaystyle g_n=1 </math> }
<wrongoption> <math>\displaystyle g_0=1 </math>  oraz  <math>\displaystyle g_n=0 </math>  dla  <math>\displaystyle n>1 </math> }
</quiz>
 
<quiz>Niech  <math>\displaystyle G\!\left( x \right)=\left( 1+x \right)^y </math> , gdzie  <math>\displaystyle y </math>  jest liczba rzeczywistą.
Jeśli  <math>\displaystyle G\!\left( x \right)=\sum_{n=0}^{\infty}g_n x^n </math> , to:}
<wrongoption> <math>\displaystyle g_n=\frac{\left( y+n \right)^{\underline{n}}}{n} </math> }
<wrongoption> <math>\displaystyle g_n=\frac{y^n}{n!} </math> }
<wrongoption> <math>\displaystyle g_n={ y+n \choose n }=\frac{\left( y+n \right)^{\underline{n}}}{n!} </math> }
<rightoption> <math>\displaystyle g_n={ y \choose n }=\frac{y^{\underline{n}}}{n!} </math> }
</quiz>
 
<quiz>Suma  <math>\displaystyle \sum_{k=0}^{n}\left( 3k^2-3k+1 \right) </math>  wynosi:}
<wrongoption> <math>\displaystyle 2n^3+3n+n </math> ,}
<rightoption> <math>\displaystyle n^3 </math> ,}
<wrongoption> <math>\displaystyle \left( 2n^3+3n+n \right)/{6} </math> ,}
<wrongoption> <math>\displaystyle 3n^3-3n^2+n </math> }
</quiz>
 
<quiz>Niech  <math>\displaystyle a_0=2 </math> ,  <math>\displaystyle a_1=3 </math> ,  <math>\displaystyle a_2=5 </math> , oraz  <math>\displaystyle a_{n+3}=7a_{n+2}-16a_{n+1}+12a_n </math> .
Wtedy:}
<wrongoption> <math>\displaystyle a_n=\left( 1-n \right)2^n+3^n </math> }
<rightoption> <math>\displaystyle a_n=\frac{1}{\sqrt{5}}\left( \left( \frac{1+\sqrt{5}}{2} \right)^{n+3}-\left( \frac{1-\sqrt{5}}{2} \right)^{n+3} \right) </math> }
<wrongoption> <math>\displaystyle a_n=\frac{1}{\sqrt{5}}\left( \left( \frac{1+\sqrt{5}}{2} \right)^{n}-\left( \frac{1-\sqrt{5}}{2} \right)^{n} \right) </math> }
<wrongoption>żadna z pozostałych odpowiedzi nie jest prawidłowa}
</quiz>
 
--------------------------------
8888888888888888888888888888888888888888888888
 
{article}
{../makraT}
 
0mm
{| border=1
|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
|-
| '''Zliczanie obiektów'''
|-
|
 
|}
 
10mm
 
<quiz>Liczby Catalana  <math>\displaystyle c_n </math>  spełniają zależność rekurencyjną:}
<wrongoption> <math>\displaystyle c_n =\sum_{k=1}^{n-1} c_{k} </math> }
<wrongoption> <math>\displaystyle c_n =\sum_{k=1}^{n} c_{k} </math> }
<wrongoption> <math>\displaystyle c_n =\sum_{k=1}^{n-1} c_{k} c_{n-k} </math> }
<rightoption> <math>\displaystyle c_n =\sum_{k=1}^{n} c_{k-1} c_{n-k} </math> }
</quiz>
 
<quiz> <math>\displaystyle n </math> -ta liczba Catalana to:}
<wrongoption> <math>\displaystyle {2n \choose n} </math> }
<rightoption> <math>\displaystyle \frac{1}{n+1}{2n \choose n} </math> }
<wrongoption> <math>\displaystyle {1/2 \choose n}\left( -4 \right)^n </math> }
<rightoption> <math>\displaystyle 2{1/2 \choose n+1}\left( -4 \right)^n </math> }
</quiz>
 
<quiz>Niech  <math>\displaystyle t_{10} </math>  będzie liczbą drzew  o wysokości  <math>\displaystyle 10 </math> . Wtedy:}
<rightoption> <math>\displaystyle t_{10}\leq 2^{1023} </math> }
<rightoption> <math>\displaystyle t_{10}\geq 2^{512} </math> }
<wrongoption> <math>\displaystyle t_{10}\leq 2^{10} </math> }
<wrongoption> <math>\displaystyle t_{10}\geq 2^{9} </math> }
</quiz>
 
<quiz>Liczba podziałów liczby  <math>\displaystyle 16 </math>  na sumy złożone jedynie ze składników  <math>\displaystyle 1,2,4,8,16 </math> 
wynosi:}
<wrongoption> <math>\displaystyle 25 </math> }
<wrongoption> <math>\displaystyle 26 </math> }
<rightoption> <math>\displaystyle 35 </math> }
<wrongoption> <math>\displaystyle 165 </math> }
</quiz>
 
<quiz>Funkcja tworząca podziału liczby na sumy jest przedstawialna jako:}
<rightoption> <math>\displaystyle \prod_{k=1}^{\infty}\frac{1}{1-x^k} </math> }
<wrongoption> <math>\displaystyle \sum_{k=1}^{\infty}\frac{1}{1-x^k} </math> }
<wrongoption> <math>\displaystyle \sum_{n=0}^{\infty}\prod_{k=1}^{\infty}\frac{1}{1-x^{nk}} </math> }
<rightoption> <math>\displaystyle \prod_{k=1}^{\infty}\sum_{n=0}^{\infty}x^{nk} </math> }
</quiz>
 
<quiz>Funkcja  tworząca
<math>\displaystyle s_n\!\left( x \right)=\left[\begin{array} {c}n\\ 0\end{array} \right]+\left[\begin{array} {c}n\\ 1\end{array} \right]x+\left[\begin{array} {c}n\\ 2\end{array} \right]x^2+\left[\begin{array} {c}n\\ 3\end{array} \right]x^3+\ldots,
</math>
dla cyklowych liczb Stirlinga  <math>\displaystyle \left[\begin{array} {c}n\\ m\end{array} \right] </math> , ma postać zwartą:
}
<rightoption> <math>\displaystyle s_n\!\left( x \right)=x^{\overline{n}} </math> }
<rightoption> <math>\displaystyle s_n\!\left( x \right)=\prod_{k=0}^{n-1}\left( x+k \right) </math> }
<wrongoption> <math>\displaystyle s_n\!\left( x \right)=x^{\underline{n}} </math> }
<wrongoption> <math>\displaystyle s_n\!\left( x \right)=1/\prod_{k=0}^{n-1}\left( 1-kx \right) </math> }
</quiz>
 
<quiz>Podziałowe liczby Stirlinga spełniają zależność rekurencyjną:}
<wrongoption> <math>\displaystyle \left\{\begin{array} {c}n\\ k\end{array} \right\}=\left( n-1 \right)\left\{\begin{array} {c}n-1\\ k\end{array} \right\}+\left\{\begin{array} {c}n-1\\ k-1\end{array} \right\} </math> , dla  <math>\displaystyle 0>k>n </math> }
<wrongoption> <math>\displaystyle \left\{\begin{array} {c}n+k\\ k\end{array} \right\}=\left\{\begin{array} {c}n+k-1\\ k\end{array} \right\}+k\left\{\begin{array} {c}n+k-1\\ k-1\end{array} \right\} </math> , dla  <math>\displaystyle n>1,\ k>0 </math> }
<rightoption> <math>\displaystyle \left\{\begin{array} {c}n+k\\ k\end{array} \right\}=k\left\{\begin{array} {c}n+k-1\\ k\end{array} \right\}+\left\{\begin{array} {c}n+k-1\\ k-1\end{array} \right\} </math> , dla  <math>\displaystyle n>1,\ k>0 </math> }
<wrongoption>żadna z pozostałych odpowiedzi nie jest prawidłowa}
</quiz>
 
<quiz> Niech  <math>\displaystyle a_0=1 </math> ,  <math>\displaystyle a_1=0 </math>  oraz  <math>\displaystyle a_n=\frac{a_{n-2}}{n} </math> .
Funkcja  tworząca  <math>\displaystyle A\!\left( x \right)=\sum_{n=0}^{\infty}a_n x^n </math>  ma postać zwartą:}
<wrongoption> <math>\displaystyle A\!\left( x \right)=\sin x </math> }
<wrongoption> <math>\displaystyle A\!\left( x \right)=e^{x^2} </math> }
<rightoption> <math>\displaystyle A\!\left( x \right)=e^{x^2/2} </math> }
<wrongoption>żadna z pozostałych odpowiedzi nie jest prawidłowa}
</quiz>
 
999999999999999999999999999999999999999
 
{article}
{../makraT}
 
0mm
{| border=1
|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
|-
| '''Asymptotyka'''
|-
|
 
|}
 
10mm
 
<quiz>Funkcja <math>\displaystyle n^2\lg{n}+\frac{n^2\sqrt{n}}{\lg{n}}</math> jest:}
<wrongoption> <math>\displaystyle \Theta(n^2\lg{n})</math>
<wrongoption> <math>\displaystyle O(n^2\lg{n})</math>
<wrongoption> <math>\displaystyle \Theta{n^2\sqrt{n}}</math>
<rightoption>  <math>\displaystyle O(\frac{n^2\sqrt{n}}{\lg{n}})</math>
</quiz>
 
<quiz>Funkcja <math>\displaystyle \frac{n^9}{\lg^{10}n}</math> jest:}
<wrongoption> <math>\displaystyle O(n^{\frac{9}{10}})</math>
<wrongoption> <math>\displaystyle O(n)</math>
<rightoption>  <math>\displaystyle O(n^9)</math>
<rightoption>  <math>\displaystyle \Omega(\lg^{10}n)</math>
</quiz>
 
<quiz>Dla <math>\displaystyle f(n)=2^{\lg{n}+1}</math> oraz <math>\displaystyle g(n)=\lg{2n}-1</math> zachodzi:}
<wrongoption> <math>\displaystyle f(x)=\omega(g(x))</math>
<rightoption>  <math>\displaystyle f(x)=\Omega(g(x))</math>
<rightoption>  <math>\displaystyle f(x)=\Theta(g(x))</math>
<rightoption>  <math>\displaystyle f(x)=O(g(x))</math>
<wrongoption> <math>\displaystyle f(x)=o(g(x))</math>
</quiz>
 
<quiz>Dowolny wielomian <math>\displaystyle k</math>-tego stopnia jest:}
<rightoption>  <math>\displaystyle \Omega(n^k)</math>
<rightoption>  <math>\displaystyle \Theta(n^k)</math>
<rightoption>  <math>\displaystyle O(n^k)</math>
<rightoption>  <math>\displaystyle o(n^{k+\varepsilon})</math> dla dowolnego <math>\displaystyle \varepsilon>0</math>
</quiz>
 
<quiz>Dla <math>\displaystyle f(n)=\frac{\lg n}{n}</math> oraz <math>\displaystyle g(n)=\frac{1}{\sqrt{n}}</math> zachodzi:}
<wrongoption> <math>\displaystyle f(x)=\omega(g(x))</math>
<wrongoption> <math>\displaystyle f(x)=\Omega(g(x))</math>
<wrongoption> <math>\displaystyle f(x)=\Theta(g(x))</math>
<rightoption>  <math>\displaystyle f(x)=O(g(x))</math>
<rightoption>  <math>\displaystyle f(x)=o(g(x))</math>
</quiz>
 
<quiz>Dla <math>\displaystyle f(x)=x^2</math> oraz <math>\displaystyle g(x)=x^2+\sin x</math> zachodzi:}
<rightoption>  <math>\displaystyle f(x)=\Omega(g(x))</math>
<rightoption>  <math>\displaystyle f(x)=\Theta(g(x))</math>
<rightoption>  <math>\displaystyle f(x)=O(g(x))</math>
<wrongoption> żadne z pozostałych
</quiz>
 
<quiz>Dla <math>\displaystyle T(n)=9T(\frac{n}{3})+\frac{n^2}{\lg n}</math>:}
<wrongoption> możemy skorzystać z pierwszego punktu Tw. o rekurencji uniwersalnej i <math>\displaystyle T(n)=\Theta(n^2)</math>
<wrongoption> możemy skorzystać z drugiego punktu Tw. o rekurencji uniwersalnej i <math>\displaystyle T(n)=\Theta(n^2\lg n)</math>
<wrongoption> możemy skorzystać z trzeciego punktu Tw. o rekurencji uniwersalnej i <math>\displaystyle T(n)=\Theta(\frac{n^2}{\lg n})</math>
<rightoption>  żadne z pozostałych
</quiz>
 
<quiz>Dla <math>\displaystyle T(n)=25T(\frac{n}{4})+\frac{n^2}{\lg n}</math>}
<rightoption>  możemy skorzystać z pierwszego punktu Tw. o rekurencji uniwersalnej i <math>\displaystyle T(n)=\Theta(n^{\lg_4{25}})</math>
<wrongoption> możemy skorzystać z drugiego punktu Tw. o rekurencji uniwersalnej i <math>\displaystyle T(n)=\Theta(n^2)</math>
<wrongoption> możemy skorzystać z trzeciego punktu Tw. o rekurencji uniwersalnej i <math>\displaystyle T(n)=\Theta(\frac{n^2}{\lg n})</math>
<wrongoption> żadne z pozostałych
</quiz>
 
<quiz>Funkcja spełniająca zależność <math>\displaystyle T(n)=T(\frac{n}{2})+1</math> jest:}
<rightoption>  <math>\displaystyle \Theta(\lg n)</math>
<rightoption>  <math>\displaystyle \Theta(n)</math>
<rightoption>  <math>\displaystyle O(n)</math>
<wrongoption> żadne z pozostałych
</quiz>
 
101010101010101010101010101010101010
 
{article}
{../makraT}
 
0mm
{| border=1
|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
|-
| '''Teoria liczb I'''
|-
|
 
|}
 
10mm
 
<quiz>Liczb naturalnych <math>\displaystyle n>1</math> w rozkładzie których
występują wszystkie liczby pierwsze niewiększe od <math>\displaystyle n</math> jest:}
<wrongoption> nieskończenie wiele
<rightoption>  co najmniej jedna
<rightoption>  skończenie wiele
<wrongoption> nie ma takich liczb
</quiz>
 
<quiz>Liczb pierwszych postaci <math>\displaystyle 91n+7</math>, dla <math>\displaystyle n\in\mathbb{N}</math> jest:}
<wrongoption> nie ma takich liczb
<rightoption>  dokładnie jedna
<rightoption>  skończenie wiele
<wrongoption> nieskończenie wiele
</quiz>
 
<quiz>Jeśli w ciągu postaci <math>\displaystyle \left\lbrace an+b \right\rbrace_{n\in\mathbb{N}}</math>, gdzie <math>\displaystyle a,b\in\mathbb{N}</math>, 
są przynajmniej dwie liczby pierwsze, to}
<rightoption>  jest ich nieskończenie wiele
<wrongoption> wszystkie liczby tego ciągu są pierwsze
<wrongoption> może ich być tylko skończenie wiele
<rightoption>  <math>\displaystyle a</math> i <math>\displaystyle b</math> są względnie pierwsze
</quiz>
 
<quiz>Jeśli <math>\displaystyle p</math> jest dowolną liczbą pierwszą, to sito Eratostenesa
zastosowane do liczby <math>\displaystyle p^2+2</math> jako ostatnią skreśli:}
<wrongoption> <math>\displaystyle p</math>
<rightoption>  <math>\displaystyle p^2</math>
<wrongoption> <math>\displaystyle p^2+1</math>
<wrongoption> <math>\displaystyle p^2+2</math>
</quiz>
 
<quiz>Jeśli <math>\displaystyle a|bc</math> oraz  NWD <math>\displaystyle  (a,b)=d</math>, to}
<rightoption>  <math>\displaystyle \frac{a}{d}|c</math>
<rightoption>  <math>\displaystyle a|cd</math>
<rightoption>  <math>\displaystyle \frac{a}{d}\perp b</math>
<rightoption>  <math>\displaystyle \frac{a}{d}\perp\frac{b}{d}</math>
</quiz>
 
<quiz>Liczb pierwszych postaci <math>\displaystyle n^2-1</math>, gdzie <math>\displaystyle n\in\mathbb{N}</math>, jest:}
<wrongoption> <math>\displaystyle 0</math>
<rightoption>  <math>\displaystyle 1</math>
<rightoption>  skończenie wiele
<wrongoption> nieskończenie wiele
</quiz>
 
<quiz>Jeśli <math>\displaystyle a</math> i <math>\displaystyle b</math> są liczbami złożonymi to}
<wrongoption>  NWD <math>\displaystyle  (a,b)>1</math>
<rightoption>  <math>\displaystyle \frac{a}{ </math>  NWD <math>\displaystyle  (a,b)}\perp\frac{b}{ </math>  NWD <math>\displaystyle  (a,b)}</math>
<wrongoption> jedna z liczb <math>\displaystyle \frac{a}{ </math>  NWD <math>\displaystyle  (a,b)}</math>, <math>\displaystyle \frac{b}{ </math>  NWD <math>\displaystyle  (a,b)}</math> jest pierwsza
<wrongoption> jeśli <math>\displaystyle a\perp b</math>, to przynajmniej jedna z liczb <math>\displaystyle a-b</math>, <math>\displaystyle a+b</math> jest parzysta
</quiz>
 
<quiz>Jeśli <math>\displaystyle a|c</math> i <math>\displaystyle b|c</math>, to}
<wrongoption>  NWD <math>\displaystyle  (a,b)>1</math>
<wrongoption>  NWD <math>\displaystyle  (a,b)<c</math>
<rightoption>  jeśli  NWD <math>\displaystyle  (a,b)>1</math>, to  NWW <math>\displaystyle  (a,b)<c</math>
<rightoption>    NWW <math>\displaystyle  (a,b)\leqslant c</math>
</quiz>
 
<quiz>Rosnący ciąg arytmetyczny rozpoczynający się od <math>\displaystyle 1</math>:}
<rightoption>  zawsze zawiera nieskończenie wiele liczb pierwszych
<wrongoption> może zawierać tylko skończenie wiele liczb pierwszych
<wrongoption> zawsze zawiera tylko skończenie wiele liczb pierwszych
<wrongoption> może nie zawierać żadnej liczby pierwszej
</quiz>
 
11111111111111111111111111111111
 
{article}
{../makraT}
 
0mm
{| border=1
|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
|-
| '''Teoria liczb II'''
|-
|
 
|}
 
10mm
 
<quiz>Jeśli <math>\displaystyle d\perp n</math> oraz  <math>\displaystyle acd\equiv_{cn}bcd</math>, to}
<rightoption>  <math>\displaystyle a\equiv_nb</math>
<rightoption>  <math>\displaystyle ad\equiv_nbd</math>
<rightoption>  <math>\displaystyle acd\equiv_nbcd</math>
<wrongoption> <math>\displaystyle ac\equiv_{nd}bc</math>
</quiz>
 
<quiz>Równanie <math>\displaystyle 7x\equiv_{91}4</math>}
<wrongoption> nie ma rozwiązania
<wrongoption> ma skończenie wiele rozwiązań
<wrongoption> zbiór wszystkich jego rozwiązań jest postaci <math>\displaystyle \left\lbrace 13n+c:n\in\ N \right\rbrace</math> dla pewnego <math>\displaystyle c\in\mathbb{N}</math>
<rightoption>  zbiór wszystkich rozwiązań jest postaci <math>\displaystyle \left\lbrace 91n+c:n\in\mathbb{N} \right\rbrace</math> dla pewnego <math>\displaystyle c\in\mathbb{N}</math>
</quiz>
 
<quiz>Układ równań
 
<center><math>\displaystyle \aligned x&\equiv_9&8,\\
x&\equiv_{223}&222.
\endaligned</math></center>
 
}
<rightoption>  ma całkowite rozwiązanie mniejsze od 2006
<wrongoption> <math>\displaystyle 2006</math> jest jego jedynym rozwiązaniem
<wrongoption> wszystkie jego rozwiązania są postaci <math>\displaystyle 2006\cdot n</math>, gdzie <math>\displaystyle n\in\mathbb{Z}</math>
<rightoption>  wszystkie jego rozwiązania są postaci <math>\displaystyle 2007n+2006</math>
</quiz>
 
<quiz>Dla <math>\displaystyle a<b</math> warunek <math>\displaystyle \varphi(a)\leqslant\varphi(b)</math> zachodzi jeśli}
<wrongoption> <math>\displaystyle a\leqslant b</math>
<rightoption>  <math>\displaystyle a|b</math>
<wrongoption> <math>\displaystyle a\perp b</math>
<rightoption>  <math>\displaystyle a\leqslant b</math> i <math>\displaystyle b</math> jest pierwsza
</quiz>
 
<quiz><math>\displaystyle 16^{49}  </math>  { mod}  <math>\displaystyle  25</math> wynosi:}
<wrongoption> <math>\displaystyle 1</math>
<wrongoption> <math>\displaystyle 7</math>
<wrongoption> <math>\displaystyle 14</math>
<rightoption>  <math>\displaystyle 21</math>
</quiz>
 
<quiz><math>\displaystyle 14^{111}  </math>  { mod}  <math>\displaystyle  15</math> wynosi:}
<wrongoption> <math>\displaystyle 1</math>
<wrongoption> <math>\displaystyle 3</math>
<wrongoption> <math>\displaystyle 12</math>
<rightoption>  <math>\displaystyle 14</math>
</quiz>
 
<quiz>Wiedząc, że <math>\displaystyle 2006=2\cdot17\cdot59</math> oblicz <math>\displaystyle \mu(2006)</math>: }
<rightoption>  <math>\displaystyle -1</math>
<wrongoption> <math>\displaystyle 0</math>
<wrongoption> <math>\displaystyle 1</math>
<wrongoption> <math>\displaystyle 3</math>
</quiz>
 
<quiz><math>\displaystyle (n-1)!</math> modulo <math>\displaystyle n</math> to:}
<rightoption>  <math>\displaystyle 0</math>, jeśli <math>\displaystyle n</math> jest złożona a <math>\displaystyle -1</math>, jeśli <math>\displaystyle n</math> jest pierwsza
<rightoption>  <math>\displaystyle 0</math>, jeśli <math>\displaystyle n</math> jest złożona a <math>\displaystyle n-1</math>, jeśli <math>\displaystyle n</math> jest pierwsza
<wrongoption> <math>\displaystyle 0</math>, jeśli <math>\displaystyle n</math> jest złożona a <math>\displaystyle 1</math>, jeśli <math>\displaystyle n</math> jest pierwsza
<wrongoption> zawsze wynosi <math>\displaystyle 1</math>
</quiz>
 
12121212121212121212121212121212
 
{article}
{../makraT}
 
0mm
{| border=1
|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
|-
| '''Grafy I'''
|-
|
 
|}
 
10mm
 
<quiz>Różnych grafów skierowanych bez cykli jednoelementowych w zbiorze <math>\displaystyle n</math>-elementowym jest:}
<wrongoption>  <math>\displaystyle 2^{n^2}</math>
<rightoption>  <math>\displaystyle 2^{n^2-n}</math>
<wrongoption>  <math>\displaystyle 2^{2^n}</math>
<wrongoption>  <math>\displaystyle 2^{2^n-n}</math>
<wrongoption>    <math>\displaystyle 2^{n \choose 2}</math>
</quiz>
 
<quiz>Różnych grafów nieskierowanych bez cykli jednoelementowych  w zbiorze <math>\displaystyle n</math>-elementowym jest:}
<wrongoption>  <math>\displaystyle 2^{n^2}</math>
<wrongoption>  <math>\displaystyle 2^{n^2-n}</math>
<wrongoption>  <math>\displaystyle 2^{2^n}</math>
<wrongoption>  <math>\displaystyle 2^{2^n-n}</math>
<rightoption>    <math>\displaystyle 2^{n \choose 2}</math>
</quiz>
 
<quiz>Zaznacz zdania prawdziwe:}
<wrongoption>    W każdym grafie prostym <math>\displaystyle G= \left( V;E \right)</math> relacja <math>\displaystyle E</math> musi być zwrotna.
<rightoption>    W grafie nieskierowanym  <math>\displaystyle G= \left( V,E \right)</math> relacja <math>\displaystyle E</math> jest symetryczna.
<wrongoption>    Graf nieskierowany to rodzina wszystkich dwuelementowych podzbiorów zbioru wierzchołków.
<rightoption>    W grafie pełnym każde dwa różne wierzchołki połączone są krawędzią.
</quiz>
 
<quiz>Zaznacz zdania prawdziwe dla grafów nieskierowanych:}
<rightoption> podgraf indukowany grafu pełnego jest grafem pełnym
<rightoption> każdy graf jest podgrafem jakiegoś grafu pełnego
<wrongoption> każdy graf jest podgrafem indukowanym jakiegoś grafu pełnego
<wrongoption> graf pełny ma zawsze parzystą liczbę krawędzi
<rightoption> w grafie pełnym wszystkie wierzchołki mają ten sam stopień
</quiz>
 
<quiz>Jaka jest najmniejsza liczba krawędzi w grafie
nieskierowanym o 100 wierzchołkach i trzech składowych spójnych:}
<wrongoption> <math>\displaystyle 99</math>
<rightoption> <math>\displaystyle 97</math>
<wrongoption> <math>\displaystyle 98</math>
<wrongoption> <math>\displaystyle 100</math>
<wrongoption> <math>\displaystyle \frac{100 \cdot 99}{3}</math>
</quiz>
 
<quiz>Ile jest krawędzi w pełnym grafie dwudzielnym <math>\displaystyle K_{1000,1000}</math>:}
<rightoption> <math>\displaystyle 1000 \cdot 1000</math>
<wrongoption> <math>\displaystyle 1000!</math>
<wrongoption> <math>\displaystyle 1000 \choose 2</math>
<wrongoption> <math>\displaystyle 1000 \choose 50</math>
<wrongoption> <math>\displaystyle 2000 \choose 1000</math>
</quiz>
 
<quiz>W pełnym grafie <math>\displaystyle 100</math>-elementowym:}
<wrongoption> każde drzewo rozpinające ma <math>\displaystyle 100</math> krawędzi
<wrongoption> dokładnie jedno drzewo rozpinające ma <math>\displaystyle 100</math> krawędzi
<rightoption>  każde drzewo rozpinające ma <math>\displaystyle 99</math> krawędzi
<wrongoption> dokładnie jedno drzewo rozpinające ma <math>\displaystyle 99</math> krawędzi
<wrongoption> nie ma drzew rozpinających
</quiz>
 
<quiz>W pełnym grafie dwudzielnym <math>\displaystyle K_{50,50}</math>:}
<wrongoption> każde drzewo rozpinające ma <math>\displaystyle 50</math> krawędzi
<wrongoption> każde drzewo rozpinające ma <math>\displaystyle 100</math> krawędzi
<rightoption>  każde drzewo rozpinające ma <math>\displaystyle 99</math> krawędzi
<wrongoption> dokładnie jedno drzewo rozpinające ma <math>\displaystyle 99</math> krawędzi
<wrongoption> nie ma drzew rozpinających
</quiz>
 
<quiz>W <math>\displaystyle 100</math> elementowym grafie o trzech składowych spójnych:}
<wrongoption> jakiś las rozpinający ma <math>\displaystyle 100</math> krawędzi
<wrongoption> jakiś las rozpinający ma <math>\displaystyle 99</math> krawędzi
<wrongoption> jakiś las rozpinający ma <math>\displaystyle 98</math> krawędzi
<rightoption>  jakiś las rozpinający ma <math>\displaystyle 97</math> krawędzi
<wrongoption> może nie być lasu rozpinającego
</quiz>
 
<quiz>Pełny graf <math>\displaystyle 100</math>-elementowy:}
<rightoption> jest grafem Hamiltonowskim
<wrongoption> jest grafem Eulerowskim
<wrongoption> jest spójny
<wrongoption> jest dwudzielny
<rightoption> jest stukolorowalny
</quiz>
 
<quiz>Pełny graf dwudzielny <math>\displaystyle K_{25,25}</math>:}
<rightoption> jest grafem Hamiltonowskim
<wrongoption> jest grafem Eulerowskim
<rightoption> zawiera cykl <math>\displaystyle 4</math> wierzchołkach jako podgraf indukowany
<wrongoption> zawiera cykl <math>\displaystyle 6</math> wierzchołkach jako podgraf indukowany
<rightoption> jest trójkolorowalny
</quiz>
 
<quiz>Graf o  <math>\displaystyle 2005 </math>  wierzchołkach, z których każdy ma stopień  <math>\displaystyle 101 </math> :}
<wrongoption>ma  <math>\displaystyle 202505 </math>  krawędzi}
<wrongoption>ma  <math>\displaystyle 2106 </math>  krawędzi}
<wrongoption>ma  <math>\displaystyle 405010 </math>  krawędzi}
<rightoption>nie istnieje}
</quiz>
 
<quiz>Jeśli  <math>\displaystyle \mathbf{G}_1=\left( V,E_1 \right) </math>  i  <math>\displaystyle \mathbf{G}_2=\left( V,E_2 \right) </math> 
są grafami niespójnymi o tym samym zbiorze wierzchołków  <math>\displaystyle V </math> , to:}
<rightoption>graf  <math>\displaystyle \mathbf{G}_1\cup\mathbf{G}_1 </math>  może być spójny}
<wrongoption>graf  <math>\displaystyle \mathbf{G}_1\cup\mathbf{G}_1 </math>  jest spójny}
<rightoption>graf  <math>\displaystyle \mathbf{G}_1\cap\mathbf{G}_1 </math>  może nie być spójny}
<rightoption>graf  <math>\displaystyle \mathbf{G}_1\cap\mathbf{G}_1 </math>  nie jest spójny}
</quiz>
 
<quiz>Graf  <math>\displaystyle \mathbf{P}_4 </math>  to graf, który składa się jedynie ze ścieżki
odwiedzającej  <math>\displaystyle 4 </math>  wierzchołki,
czyli  <math>\displaystyle {\sf V}\!\left(\mathbf{P}_4\right)=\left\lbrace a,b,c,d \right\rbrace </math> 
oraz  <math>\displaystyle {\sf E}\!\left(\mathbf{P}_4\right)=\left\lbrace \left\lbrace a,b \right\rbrace,\left\lbrace b,c \right\rbrace,\left\lbrace c,d \right\rbrace \right\rbrace </math> .
W grafie spójnym, w którym nie ma
podgrafu indukowanego izomorficznego do  <math>\displaystyle \mathbf{P}_4 </math> :}
<rightoption>dowolne dwa punkty leżą w odległości co najwyżej trzy}
<rightoption>dowolne dwa punkty leżą w odległości co najwyżej dwa}
<wrongoption>dowolne dwa punkty leżą w odległości co najwyżej jeden}
<wrongoption>każde trzy wierzchołki tworzą klikę  <math>\displaystyle \mathcal{K}_{3} </math> }
</quiz>
 
<quiz>Zaznacz zdania prawdziwe:}
<rightoption>Każdy graf pusty jest grafem dwudzielnym.}
<wrongoption>Każdy graf pełny jest grafem dwudzielnym.}
<wrongoption>Graf  <math>\displaystyle \mathcal{K}_{3} </math>  jest grafem dwudzielnym.}
<rightoption>Graf  <math>\displaystyle \mathcal{K}_{2} </math>  jest grafem dwudzielnym.}
</quiz>
 
<quiz>Zaznacz zdania prawdziwe:}
<rightoption>Każdy graf dwudzielny, który jest zarazem grafem pełnym jest planarny.}
<rightoption>Graf  <math>\displaystyle \mathcal{K}_{4} </math>  jest grafem planarnym.}
<wrongoption>Graf  <math>\displaystyle \mathcal{K}_{5} </math>  jest grafem planarnym.}
<wrongoption>Każdy graf dwudzielny jest grafem planarnym.}
</quiz>
 
<quiz>Graf o  <math>\displaystyle 100 </math>  wierzchołkach:}
<wrongoption>jeśli ma  <math>\displaystyle 99 </math>  krawędzi, to jest drzewem.}
<wrongoption>jeśli ma  <math>\displaystyle 100 </math>  krawędzi, to jest drzewem.}
<wrongoption>jeśli ma  <math>\displaystyle 4850 </math>  krawędzi, to jest spójny.}
<rightoption>jeśli ma  <math>\displaystyle 4851 </math>  krawędzi, to jest spójny.}
</quiz>
 
<quiz>Na to by graf  <math>\displaystyle \mathbf{T} </math>  był drzewem potrzeba i wystarcza, by:}
<wrongoption> <math>\displaystyle \mathbf{T} </math>  nie zawierał cykli}
<rightoption> <math>\displaystyle \mathbf{T} </math>  był spójny i miał  <math>\displaystyle \left\vert V \right\vert-1 </math>  krawędzi}
<rightoption>dowolne dwa wierzchołki grafu  <math>\displaystyle \mathbf{T} </math>  były połączone dokładnie jedną drogą}
<wrongoption>dowolne dwa wierzchołki grafu  <math>\displaystyle \mathbf{T} </math>  leżały na dokładnie jednym cyklu}
</quiz>
 
131313131313131313131313131313
 
{article}
{../makraT}
 
0mm
{| border=1
|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
|-
| '''Grafy II'''
|-
|
 
|}
 
10mm
 
<quiz>Pełny graf dwudzielny  <math>\displaystyle \mathcal{K}_{3,3} </math> :}
<wrongoption>jest eulerowski}
<rightoption>jest hamiltonowski}
<wrongoption>jest planarny}
<wrongoption>nie jest ani eulerowski ani planarny}
</quiz>
 
<quiz>Pełny graf <math>\displaystyle 100</math>-elementowy:}
<rightoption> jest grafem Hamiltonowskim
<wrongoption> jest grafem Eulerowskim
<wrongoption> jest spójny
<wrongoption> jest dwudzielny
<rightoption> jest stukolorowalny
</quiz>
 
<quiz>Graf, w którym cykl Hamiltona jest zarazem cyklem Eulera}
<wrongoption>sam jest cyklem o parzystej liczbie krawędzi}
<rightoption>jest cyklem}
<rightoption>ma wierzchołki wyłącznie o stopniu  <math>\displaystyle 2 </math> }
<wrongoption>jest sumą dwu grafów o tych samych wierzchołkach ale rozłącznych zbiorach krawędzi,
przy czym każdy z nich jest cyklem}
</quiz>
 
<quiz>Jeśli graf  <math>\displaystyle \mathbf{G} </math>  jest eulerowski, to:}
<wrongoption>graf  <math>\displaystyle \mathbf{G} </math>  jest hamiltonowski}
<rightoption>każdy wierzchołek w grafie  <math>\displaystyle \mathbf{G} </math>  ma parzysty stopień}
<rightoption>graf  <math>\displaystyle \mathbf{G} </math>  jest sumą grafów o tych samych wierzchołkach
ale rozłącznych zbiorach krawędzi, przy czym każdy z nich jest cyklem}
<wrongoption>jeśli dodatkowo  <math>\displaystyle \mathbf{G} </math>  jest hamiltonowski,
to po usunięciu cyklu Hamiltona graf  <math>\displaystyle \mathbf{G} </math>  dalej jest eulerowski}
</quiz>
 
<quiz>Graf o  <math>\displaystyle 101 </math>  wierzchołkach:}
<wrongoption>w którym wszystkie wierzchołki są stopnia  <math>\displaystyle 50 </math> , jest hamiltonowski}
<rightoption>w którym wszystkie wierzchołki są stopnia  <math>\displaystyle 51 </math> , jest hamiltonowski}
<wrongoption>w którym dowolne dwa niesąsiednie wierzchołki  <math>\displaystyle v </math>  i  <math>\displaystyle w </math> 
spełniają  <math>\displaystyle \deg{v}+\deg{w}\geq 100 </math>  jest hamiltonowski}
<wrongoption>w którym dowolne dwa sąsiednie wierzchołki  <math>\displaystyle v </math>  i  <math>\displaystyle w </math> 
spełniają  <math>\displaystyle \deg{v}+\deg{w}\geq 100 </math>  jest hamiltonowski}
</quiz>
 
<quiz>Który z warunków wystarcza na to,
by w grafie dwudzielnym  <math>\displaystyle \mathbf{G}=\left( V_1\cup V_2, E \right) </math>
istniało pełne skojarzenie  <math>\displaystyle V_1 </math>  z  <math>\displaystyle V_2 </math> ?}
<rightoption>graf  <math>\displaystyle \mathbf{G} </math>  jest hamiltonowski}
<wrongoption>graf  <math>\displaystyle \mathbf{G} </math>  jest eulerowski}
<wrongoption>w grafie  <math>\displaystyle \mathbf{G} </math>  każdy wierzchołek z  <math>\displaystyle V_1 </math> 
ma co najmniej dwu sąsiadów}
<rightoption>dowolny zbiór niezależny w  ma co najwyżej  <math>\displaystyle \left\vert V_2 \right\vert </math>  wierzchołków}
</quiz>
 
<quiz>Grafem  <math>\displaystyle 100 </math> -spójnym jest:}
<rightoption>graf w którym pomiędzy dowolnymi wierzchołkami istnieje  <math>\displaystyle 100 </math> 
dróg wierzchołkowo rozłącznych}
<wrongoption>graf, którego każdy zbiór rozdzielający ma co najmniej  <math>\displaystyle 99 </math>  wierzchołków}
<rightoption>klika  <math>\displaystyle \mathcal{K}_{101} </math> }
<wrongoption>pełny graf dwudzielny  <math>\displaystyle \mathcal{K}_{100,100} </math> }
</quiz>
 
<quiz>W  <math>\displaystyle 2 </math> -spójnym krawędziowo grafie o  <math>\displaystyle 20 </math>  wierzchołkach
i minimalnej liczbie krawędzi:}
<wrongoption>jest dokładnie  <math>\displaystyle 38 </math>  krawędzi}
<rightoption>jest dokładnie  <math>\displaystyle 20 </math>  krawędzi}
<rightoption>dowolny wierzchołek ma stopień co najmniej  <math>\displaystyle 2 </math> }
<wrongoption>istnieje wierzchołek o stopniu co najmniej  <math>\displaystyle 3 </math> }
</quiz>
 
141414141414141414141414141414141414141414
 
{article}
{../makraT}
 
0mm
{| border=1
|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
|-
| '''Grafy III'''
|-
|
 
|}
 
10mm
 
<quiz>Który z grafów przedstawionych na Rysunku [[##test petersen4|Uzupelnic test petersen4|]] jest planarny?
 
[!ht]
{test_petersen4}
{ '''[Rysunek z pliku:''' <tt>testpetersen4.eps</tt>''']'''}
}
 
<wrongoption>graf przedstawiony na rysunku [[##test petersen4|Uzupelnic test petersen4|]].a.}
<wrongoption>graf przedstawiony na rysunku [[##test petersen4|Uzupelnic test petersen4|]].b.}
<wrongoption>graf przedstawiony na rysunku [[##test petersen4|Uzupelnic test petersen4|]].c.}
<rightoption>graf przedstawiony na rysunku [[##test petersen4|Uzupelnic test petersen4|]].d.}
</quiz>
 
<quiz>Który z grafów przedstawionych na Rysunku [[##test klika5|Uzupelnic test klika5|]] jest homeomorficzny z kliką  <math>\displaystyle \mathcal{K}_{5} </math> ?
 
[!ht]
{test_klika5}
{ '''[Rysunek z pliku:''' <tt>testklika5.eps</tt>''']'''}
}
 
<wrongoption>graf przedstawiony na rysunku [[##test klika5|Uzupelnic test klika5|]].a.}
<wrongoption>graf przedstawiony na rysunku [[##test klika5|Uzupelnic test klika5|]].b.}
<rightoption>graf przedstawiony na rysunku [[##test klika5|Uzupelnic test klika5|]].c.}
<wrongoption>graf przedstawiony na rysunku [[##test klika5|Uzupelnic test klika5|]].d.}
</quiz>
 
<quiz>Spójny graf planarny o  <math>\displaystyle 20 </math>  wierzchołkach, z których każdy jest stopnia  <math>\displaystyle 3 </math>  ma:}
<wrongoption> <math>\displaystyle 11 </math>  ścian}
<rightoption> <math>\displaystyle 12 </math>  ścian}
<wrongoption> <math>\displaystyle 22 </math>  ścian}
<wrongoption> <math>\displaystyle 24 </math>  ścian}
</quiz>
 
<quiz>Ile spójnych składowych ma graf planarny o  <math>\displaystyle 121 </math>  wierzchołkach,
<math>\displaystyle 53 </math>  krawędziach, oraz  <math>\displaystyle 30 </math>  ścianach?}
<rightoption> <math>\displaystyle 98 </math> }
<wrongoption> <math>\displaystyle 99 </math> }
<wrongoption> <math>\displaystyle 100 </math> }
<wrongoption> <math>\displaystyle 143 </math> }
</quiz>
 
<quiz>Niech  <math>\displaystyle \mathbf{G}^* </math>  będzie grafem geometrycznie dualnym do
grafu płaskiego  <math>\displaystyle \mathbf{G} </math> .
Podzbiór  <math>\displaystyle C </math>  zbioru krawędzi grafu  <math>\displaystyle \mathbf{G} </math>  jest cyklem w grafie  <math>\displaystyle \mathbf{G} </math> 
wtedy i tylko wtedy, gdy zbiór krawędzi dualnych do krawędzi zbioru  <math>\displaystyle C </math> }
<wrongoption>posiada parzystą liczbę elementów}
<wrongoption>posiada nieparzystą liczbę elementów}
<wrongoption>jest cyklem grafu  <math>\displaystyle \mathbf{G}^* </math> }
<rightoption>jest rozcięciem grafu  <math>\displaystyle \mathbf{G}^* </math> }
</quiz>
 
<quiz>Spójny graf prosty, który nie jest pełny,
i w którym wszystkie wierzchołki  mają stopień nie większy niż  <math>\displaystyle k </math> jest:}
<wrongoption> <math>\displaystyle \left( k-1 \right) </math> -kolorowalny}
<rightoption> <math>\displaystyle k </math> -kolorowalny}
<rightoption> <math>\displaystyle \left( k+1 \right) </math> -kolorowalny}
<rightoption> <math>\displaystyle 2k </math> -kolorowalny}
</quiz>
 
<quiz>Iloma kolorami można pokolorować polityczną mapę Europy?}
<wrongoption> <math>\displaystyle 3 </math> }
<rightoption> <math>\displaystyle 4 </math> }
<rightoption> <math>\displaystyle 5 </math> }
<rightoption> <math>\displaystyle 6 </math> }
</quiz>
 
<quiz>W grafie prostym zachodzi:}
<rightoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)\leq\chi_s\!\left( \mathbf{G} \right)+1 </math> }
<wrongoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)\leq\chi_s\!\left( \mathbf{G} \right) </math> }
<wrongoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)\geq\chi_s\!\left( \mathbf{G} \right)+1 </math> }
<wrongoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)=\chi_s\!\left( \mathbf{G} \right) </math> }
</quiz>
 
<quiz>Pełny graf dwudzielny <math>\displaystyle K_{50,50}</math>:}
<rightoption> jest grafem Hamiltonowskim
<rightoption> jest grafem Eulerowskim
<wrongoption> jest lasem
<rightoption> jest dwukolorowalny
<rightoption> jest 49-kolorowalny
</quiz>
 
151515151515151515151515151515151515
 
{article}
{../makraT}
 
0mm
{| border=1
|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
|-
| '''Metody algebraiczne w teorii grafów'''
|-
|
 
|}
 
10mm
 
<quiz>Niech  <math>\displaystyle m_{ij} </math>  oznacza liczbę skierowanych marszrut,
nie dłuższych niż  <math>\displaystyle n-1 </math> , z wierzchołka  <math>\displaystyle v_i </math>  do  <math>\displaystyle v_j </math> 
w grafie skierowanym  <math>\displaystyle \mathbf{G}=\left( \left\lbrace v_1,\ldots,v_n \right\rbrace,E \right) </math> ,
a  <math>\displaystyle M </math>  niech będzie macierzą  <math>\displaystyle \langle m_{ij}\rangle  </math> .
Wtedy:}
<rightoption> <math>\displaystyle M={\sf A}\left( \mathbf{G} \right)^1+{\sf A}\left( \mathbf{G} \right)^2+\ldots+{\sf A}\left( \mathbf{G} \right)^{\left( n-1 \right)} </math> }
<wrongoption> <math>\displaystyle M={\sf A}\left( \mathbf{G} \right)^{\left( n-1 \right)} </math> }
<wrongoption> <math>\displaystyle M=n\cdot{\sf A}\left( \mathbf{G} \right) </math> }
<rightoption> <math>\displaystyle m_{ij}>0 </math>  wtedy i tylko wtedy, gdy  <math>\displaystyle \left( v_i,v_j \right)\in{\sf E}\!\left({\sf TC}\left( \mathbf{G} \right)\right) </math> }
</quiz>
 
<quiz>Zaznacz prawdziwe zależności dla grafu prostego  <math>\displaystyle \mathbf{G} </math> 
o macierzy sąsiedztwa  <math>\displaystyle {\sf A}\left( \mathbf{G} \right) </math> ,
macierzy incydencji  <math>\displaystyle {\sf B}\left( \mathbf{G} \right) </math> ,
zorientowanej macierzy incydencji  <math>\displaystyle {\sf C}\left( \mathbf{G} \right) </math> 
oraz  macierzy stopni  <math>\displaystyle {\sf D}\left( \mathbf{G} \right) </math> :}
<wrongoption> <math>\displaystyle {\sf B}\left( \mathbf{G} \right)\cdot {\sf B}\left( \mathbf{G} \right)^T= {\sf A}\left( \mathbf{G} \right)- {\sf D}\left( \mathbf{G} \right) </math> }
<rightoption> <math>\displaystyle {\sf B}\left( \mathbf{G} \right)\cdot {\sf B}\left( \mathbf{G} \right)^T= {\sf D}\left( \mathbf{G} \right)+ {\sf A}\left( \mathbf{G} \right) </math> }
<wrongoption> <math>\displaystyle {\sf B}\left( \mathbf{G} \right) \cdot{\sf A}\left( \mathbf{G} \right) = {\sf C}\left( \mathbf{G} \right) </math> }
<wrongoption> <math>\displaystyle {\sf C}\left( \mathbf{G} \right)\cdot {\sf C}\left( \mathbf{G} \right)^T= {\sf A}\left( \mathbf{G} \right)- {\sf D}\left( \mathbf{G} \right) </math> }
</quiz>
 
<quiz>Niech  <math>\displaystyle \mathbf{G} </math>  będzie grafem o  <math>\displaystyle 10 </math>  wierzchołkach
przedstawionym na Rysunku [[##test alg|Uzupelnic test alg|]],
a macierz  <math>\displaystyle M </math> , o rozmiarach  <math>\displaystyle 9\times9 </math> ,
będzie minorem (podmacierzą) zorientowanej macierzy incydencji  <math>\displaystyle {\sf C}\left( \mathbf{G} \right) </math> ,
w którym kolumny odpowiadają krawędziom
<math>\displaystyle e_0, e_2, e_3, e_6, e_9, e_{12}, e_{13}, e_{14}, e_{15} </math> .
 
[!ht]
{test_alg}
{Graf  <math>\displaystyle \mathbf{G} </math> . '''[Rysunek z pliku:''' <tt>testalg.eps</tt>''']'''}
Wtedy:}
<rightoption>macierz  <math>\displaystyle M </math>  jest nieosobliwa}
<wrongoption>macierz  <math>\displaystyle M </math>  jest osobliwa}
<wrongoption>suma elementów w każdej kolumnie macierzy  <math>\displaystyle M </math>  wynosi  <math>\displaystyle 0 </math> }
<wrongoption>macierz  <math>\displaystyle M </math>  jest antysymetryczna}
</quiz>
 
<quiz>Na to by permanent grafu  <math>\displaystyle \mathbf{G} </math>  był niezerowy, wystarcza by:}
<rightoption>graf  <math>\displaystyle \mathbf{G} </math>  posiadał cykl Hamiltona}
<wrongoption>graf  <math>\displaystyle \mathbf{G} </math>  posiadał cykl Eulera}
<wrongoption>graf  <math>\displaystyle \mathbf{G} </math>  był spójny}
<rightoption>graf  <math>\displaystyle \mathbf{G} </math>  był grafem dwudzielnym posiadającym skojarzenie doskonałe}
</quiz>
 
<quiz>Zaznacz zdania prawdziwe o wartościach własnych grafów:}
<wrongoption>Co najmniej jedna z wartości własnych jest liczbą zespoloną.}
<wrongoption>Jeśli wszystkie wartości własne są wymierne, to graf jest eulerowski.}
<rightoption>Wszystkie wartości własne grafu hamiltonowskiego są rzeczywiste.}
<rightoption>Wszystkie wartości własne dowolnego grafu są rzeczywiste.}
</quiz>
 
<quiz>Zaznacz prawdziwe związki wartości własnych z maksymalnym stopniem wierzchołka
w grafie prostym:}
<wrongoption> <math>\displaystyle \lambda_{max}\!\left( \mathbf{G} \right)=\Delta\left( \mathbf{G} \right) </math> }
<rightoption> <math>\displaystyle \left\vert \lambda_{max}\!\left( \mathbf{G} \right) \right\vert\leq\Delta\left( \mathbf{G} \right) </math> }
<rightoption> <math>\displaystyle \lambda_{max}\!\left( \mathbf{G} \right)=\Delta\left( \mathbf{G} \right) </math> 
wtedy i tylko wtedy, gdy któraś spójna składowa grafu  <math>\displaystyle \mathbf{G} </math>
jest grafem regularnym stopnia  <math>\displaystyle \Delta\left( \mathbf{G} \right) </math> }
<rightoption> <math>\displaystyle -\Delta\left( \mathbf{G} \right) </math> 
jest wartością własną macierzy  <math>\displaystyle {\sf A}\left( \mathbf{G} \right) </math> 
wtedy i tylko wtedy, gdy  <math>\displaystyle \mathbf{G} </math>  jest regularnym grafem dwudzielnym
stopnia  <math>\displaystyle \Delta\left( \mathbf{G} \right) </math> }
</quiz>
 
<quiz>W grafie regularnym  <math>\displaystyle \mathbf{G} </math>  o  <math>\displaystyle 10 </math>  wierzchołkach stopnia  <math>\displaystyle 4 </math>
oraz wartościach własnych  <math>\displaystyle \lambda_{min}\!\left( \mathbf{G} \right)\approx-2,73205 </math>  i  <math>\displaystyle \lambda_{max}\!\left( \mathbf{G} \right)=4 </math>
moc niezależnego podzbioru jest ograniczona z góry przez:}
<wrongoption> <math>\displaystyle 2 </math> }
<wrongoption> <math>\displaystyle 3 </math> }
<rightoption> <math>\displaystyle 4 </math> }<rightoption> <math>\displaystyle 10 </math> }
</quiz>
 
<quiz>Zaznacz zdania prawdziwe wiążące liczbę chromatyczną  <math>\displaystyle \chi\!\left( \mathbf{G} \right) </math>
z wartościami własnymi grafu regularnego  <math>\displaystyle \mathbf{G} </math> :}
<rightoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)\geq 1-\frac{\lambda_{max}\!\left( \mathbf{G} \right)}{\lambda_{min}\!\left( \mathbf{G} \right)} </math> }
<wrongoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)= 1-\frac{\lambda_{max}\!\left( \mathbf{G} \right)}{\lambda_{min}\!\left( \mathbf{G} \right)} </math> }
<rightoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)\leq\lambda_{max}\!\left( \mathbf{G} \right)+1 </math> }
<wrongoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)\geq\lambda_{max}\!\left( \mathbf{G} \right) </math> }
</quiz>

Aktualna wersja na dzień 20:09, 29 wrz 2006

5555555555555555555555555555555555555555 Logika



10101010101010101010101010101010101010101010101010 Logika

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Test_GR4&oldid=60021”