Zestaw nr 3/7 (przykłady zadań z rozwiązaniami) Elementy teorii liczb: podzielność, operacje mod I div znajdywanie nwd (algorytm Euklidesa) I nww algorytmy mnożenia I potęgowania oraz działania



Pobieranie 264,56 Kb.
Data15.12.2017
Rozmiar264,56 Kb.

 (Aktualizacja z dnia 3 kwietnia 2013)

MATEMATYKA DYSKRETNA - informatyka semestr 2 (lato 2012/2013)

Zadania do omówienia na zajęciach w dniach 21 i 28 kwietnia 2013

ZESTAW NR 3/7 (przykłady zadań z rozwiązaniami)
Elementy teorii liczb:

- podzielność, operacje MOD i DIV

- znajdywanie NWD (algorytm Euklidesa) i NWW

- algorytmy mnożenia i potęgowania oraz działania modulo

Elementy kodowania:

- chińskie twierdzenie o resztach

- funkcje liniowe w pierścieniach skończonych

- zapis dwójkowy - word, byte, integer

Elementy funkcji boolowskich

Zadanie 3.1. W alfabecie 10 znakowym S={0,1,2,3,4,5,6,7,8,9}= Z_10 szyfrem liniowym

y = 2 * x + 5 (w Z_10)

zakodowano wyraz 3.literowy (3,5,8) metodą ,litera po literze'.

1. znaleźć otrzymany nowy wyraz 3.literowy

2. podać kilka innych wyrazów, które mają ten sam wynik kodowania
Rozwiązanie:

Cz.1. Dany szyfr koduje następująco:

x=3 --> y = 2 * 3 + 5 mod 10 = 11 mod 10 = 1

x=5 --> y = 2 * 5 + 5 mod 10 = 15 mod 10 = 5

x=8 --> y = 2 * 8 + 5 mod 10 = 21 mod 10 = 1



Odpowiedź: Wynik kodowania to ciąg (1,5,1)
Cz.2. Zauważam, że 3 i 8 kodują się na ten sam znak 1. Przez wykonanie tabeli wyników kodowania wszystkich znaków od 0 do9 poznam wszystkie możliwe wartości:
0 --> 5, 1 --> 7, 2 --> 9, 3 -->1, 4 --> 3, 5 --> 5, 6 --> 7, 7 --> 9, 8 --> 1, 9 --> 3.
Dochodzę do wniosku, że ten sam wynik kodowania (1,5,1) dadzą wszystkie te wyrazy, które na pierwszym miejscu mają 3 lub 8, na drugim miejscu mają 0 lub 5 i na trzecim miejscu mają znowu 3 lub 8, np.
Odpowiedź: Oto przykłady spełniające wymogi polecenia - (3,5,8), (8,0,8), (3,0,8), (3,5,3).
Zadanie 3.2. Odwrócić szyfr liniowy y = 5 * x + 2 w pierścieniu Z_9 .
Rozwiązanie: Dany wzór na y w zależności od x należy traktować jako równość w pierścieniu Z_9 , którego elementami są reszty z dzielenia przez 9 czyli liczby 0, 1, 2, 3, 4, 5, 6, 7, 8 z dodawaniem i mnożeniem modulo 9. Ponieważ liczba 5 jest pierwsza względem 9, więc ma odwrotność w tym pierścieniu, która można znaleźć przez wypisanie tabelki mnożenia. Spośród wartości iloczynu przez 5, czyli z liczb 0, 5, 10, 15, 20, 25, 30, 35, 40 tylko 10 ma wartość równą 1 modulo 9 czyli, że 2 jest odwrotnością 5 w pierścieniu Z_9. Mnożąc równość definiującą szyfr stronami przez 2 (mod 9) otrzymujemy:
2 * y = 2 * 5 * x + 2 * 2 (mod 9)
2 * y = 1 * x + 4 (mod 9)
x = 2 * y - 4 (mod 9)
i ostatecznie
Odpowiedź: x = 2 * y + 5 (w pierścieniu Z_9).

Zadanie 3.3. Znaleźć wszystkie liczby całkowite a spełniające warunki
a mod 13 = 4, a mod 8 = 5, a mod 3 = 0.

Rozwiązanie: Zastosujemy chińskie twierdzenie o resztach. W naszym przypadku mamy, że dzielniki 13, 8 oraz 3 są względnie pierwsze, tzn. żadne dwa nie mają wspólnego dzielnika. Zatem wśród liczb ze zbioru {0, 1, 2, . . . , M - 1} istnieje dokładnie jedna liczba X posiadająca wymienione reszty 4, 5, oraz 0, odpowiednio, gdzie M = 13 * 8 * 3 = 312. Ponadto, każda inna liczba przy dzieleniu przez 312 daje tę samą resztę. Zatem zbiór poszukiwanych liczb to liczby postaci X + k * 312, gdzie k to dowolna liczba ze zbioru liczb całkowitych Z := { . . ., -1, 0, 1, 2, . . . } .
Obliczanie X . Posłużymy się algorytmem podanym na wykałdzie:
definiujemy

M_1 = 8 * 3 = 24, M_2 = 13 * 3 = 39, M_3 = 13 * 8 = 104.
obliczamy

L_1 = M_1 mod 13 = 11,

L_2 = M_2 mod 8 = 7,

L_3 = M_3 mod 3 = 2
obliczamy odwrotności:

N_1 = ODWR(L_1, mod 13) = . . . = 6 (bo 6 * 11 = 5 * 13 +1 = 1 (mod 13) )

N_2 = ODWR(L_2, mod 8) = . . . = 7 (bo 7 * 7 = 6 * 8 + 1 = 1 (mod 8) )

N_3 = ODWR(L_3, mod 3) = . . . = 2 (bo 2 * 2 = 1 * 3 + 1 = 1 (mod 3) )
obliczamy liczbę:

Y = 4 * N_1* M_1 + 5 * N_2 * M_2 + 0 * N_3 * M_3 = 4 * 6 * 24 + 5* 7 *39 = 24 * 24 + 35 * 39 = 1941.
obliczamy jej resztę z dzielenia przez M = 312:

X = Y mod 312 = 69 (bo 1941 = 6 * 312 + 69).
Sprawdzenie: 69 = 3 * 13 + 4 czyli 69 mod 13 = 4,

69 = 8 * 8 +5 czyli 69 mod 8 = 5

oraz 69 = 13 * 3 czyli 69 mod 3 = 0.
Odpowiedź: Zbiór poszukiwanych liczb to wszystkie liczby postaci X + k * 312, gdzie X = 69 zaś k to dowolna liczba ze zbioru liczb całkowitych Z := { . . ., -1, 0, 1, 2, . . . } .
Zadanie 3.4. Przy pomocy algorytmu rosyjskich chłopów obliczyć iloczyn 245 * 167.
Odpowiedź: Tworzymy dwie kolumny, z których pierwsza w pierwszym wierszu zawiera 245 a druga w pierwszym wierszu zawiera 167. Kolejne wiersze powstają z dzielenia pierwszej kolumny całkowicie liczbowo przez dwa i mnożenie drugiej kolumny przez 2:
245 167

122 334


61 668 835

30 1336


15 2672 3507

7 5344 8851

3 10688 19539

1 21376 40915


Dodajemy te wyrazy z drugiej kolumny, które stoją obok liczb nieparzystych (w pierwszej kolumnie): 245 * 167 = 167 + 668 + 2672 + 5344 + 10688 + 21376 =

40915.
Zadanie 3.5. Zbudować sieć boolowską obliczającą wartości bitów z_1, z_2 (ze zbioru {0, 1} tak, aby dla dowolnych a, b, c spełniona była równość liczb naturalnych


( z_1, z_2 )_2 = a + b + c.
Uwaga: lewa strona oznacza wartość liczby zapisanej w systemie dwójkowym przy pomocy dwóch bitów, tj. liczbę z_1 * 2 + z_2 * 1 .

Odpowiedź:

Ograniczę się do sugestii, aby uzyskać ją z notatek, które prowadzą do konstrukcji tzw. pełnego sumatora FULL ADDER (dla trzech bitów). Jako dane wejściowe wziąć zmienne boolowskie a, b i c, zaś jako wyjściowe z_1 i z_2 . Ubóstwo dostępnej mi grafiki nie pozwala na sporządzenie szkicu tej odpowiedzi.

Zadanie 3.6. Pokazać przykłady takich par wartości bajtów x, y ze zbioru {0,1}^8, które spełniają równości

1. Par ( x or y ) = Par ( x ) or Par( y )

2. Par ( x xor y ) = Par( x ) xor Par( y )
Uwagi nie należące do rozwiązania:

1. Zapis ,a^b' oznacza ,a do potęgi b'. Zapis ,a_b' oznacza, że b jest dolnym indeksem a.

2. Zastosowałem łączniki ,or' i ,xor', które mogą być w zadaniach na egzaminie zastąpione przez ptaszek (taki jak oznaczający w logice ,lub') oraz krzyżyk w kółku, odpowiednio. Na niektórych edytorach brak tych symboli. JoD
Rozwiązanie:

Cz.1. Zgodnie z treścią wykładów przyjmuję, że dla x = (x_1, x_2, . . . , x_8) , y = (y_1, y_2, . . ., y_8) operacje ,or' oraz ,xor' dają w wyniku
x or y = (x_1 or y_1, x_2 or y_2, . . . , x_8 or y_8)
x xor y = (x_1 xor y_1, x_2 xor y_2, . . . , x_8 xor y_8)
przy czym tabela działania na zmiennych (0,1)-owych jest taka jak w logice:
1 or 1 = 1 or 0 = 0 or 1 = 1, 0 or 0 = 0
1 xor 1 = 0 xor 0 = 0, 1 xor 0 = 0 xor 1 = 1
Ponadto przyjmuję, że Par jest funkcją, która ciągowi (0,1)-owemu przyporządkowuje wartość 0, jeśli ilość jedynek jest parzysta, zaś wartość 1, jeśli ilość jedynek jest nieparzysta. Tak więc aby spełniona pierwsza równość zadania,

parzystość połączonych operacją ,or' ciągów x i y musi być równa większej z parzystości przypisywanych tym ciągom oddzielnie. Dam więc przykłady trzech istotnie różnych możliwości:


1.1. . . . gdy lewa strona równa się 0 i oba składniki prawej strony są równe 0, np:

x = (0,1,0,1,0,1,0,1), y = (1,0,1,0,0,0,0,0). Rzeczywiście wtedy mamy x or y = (1,1,1,1,0,1,0,1) a więc L = Par ( x or y ) = 0 (bo liczba jedynek wynosi 6 czyli że jest liczbą parzystą). Ponadto Par ( x ) = Par ( y ) = 0 (bo liczby jedynek w x i y są parzyste - 4 i 2, odpowiednio). Tak więc na prawej stronie mamy ,0 or 0' czyli 0. Zatem lewa strona i prawa są równe.
1.2. . . . . gdy lewa strona równa się 1 i oba składniki prawej strony są równe 1, np:

x = (0,1,0,1,0,1,0,0), y = (1,1,1,0,0,0,0,0). Rzeczywiście wtedy mamy x or y = (1,1,1,1,0,1,0,0) a więc L = Par ( x or y ) = 1 (bo liczba jedynek wynosi 5 czyli że jest liczbą nieparzystą). Ponadto Par ( x ) = Par ( y ) = 1 (bo liczby jedynek w x i y są nieparzyste - 3 i 3, odpowiednio). Tak więc na prawej stronie mamy ,1 or 1' czyli 1. Zatem lewa strona i prawa są równe.
1.3. . . . gdy lewa strona równa się 1 i tylko jeden składnik prawej strony jest równy 1, np: x = (0,1,0,1,0,1,0,0), y = (1,0,1,0,0,0,0,0). Rzeczywiście wtedy mamy x or y = (1,1,1,1,0,1,0,0) a więc L = Par ( x or y ) = 1 (bo liczba jedynek wynosi 5 czyli że jest liczbą nieparzystą). Ponadto Par ( x ) = 1 (bo liczba jedynek w x wynosi 3) zaś Par ( y ) = 0 ( bo liczba jedynek wynosi 2). Tak więc na prawej stronie mamy ,1 or 0' czyli 1. Zatem lewa strona i prawa są równe.
Uwaga: W tym zadaniu można dać przykłady, że równość nie jest spełniona.
Odpowiedź: Przykłady ciągów spełniających równość 1.

x = (0,1,0,1,0,1,0,1), y = (1,0,1,0,0,0,0,0);

x = (0,1,0,1,0,1,0,0), y = (1,1,1,0,0,0,0,0);

x = (0,1,0,1,0,1,0,0), y = (1,0,1,0,0,0,0,0).
Cz.2. Tutaj mamy sytuację inną, gdyż zgodnie z treścią wykładów mamy wzór:
(*) Par( x_1, x_2, . . . , x_8) = x_1 xor x_2 xor . . . xor x_8
Ponadto poznaliśmy prawo łączności i przemienności operacji ,xor'. Zatem możemy przekształcić lewa stronę następująco:
L = Par ( x xor y ) = Par ( x_1 xor y_1, x_2 xor y_2, . . . , x_8 xor y_8) =

= (x_1 xor y_1) xor (x_2 xor y_2) xor . . . xor (x_8 xor y_8) =

= ( x_1 xor x_2 xor . . . xor x_8) xor ( y_1 xor y_2 xor . . . xor y_8 )
co na mocy wzoru (*) pozwala stwierdzić, że L = Par( x ) xor Par( y ) a więc, że
Odpowiedź: Lewa strona równości 2. równa się prawej dla dowolnych x i y ze zbioru {0,1}^8. Zatem jako przykłady par spełniających można wiąć dowolne pary ciągów (0,1)-owych o długości 8.
Uwaga (poza rozwiązaniem): Jest oczywiste, że ten dowód stosuje się do tej samej równości dla ciągów dowolnej długości (niekoniecznie 8).

Zadanie 3.7. Obliczyć wartość liczbową zmiennej typu SHORT INTEGER c, wiedząc że c = a or b, gdzie zmienne typu SHORT INTEGER a i b mają wartość liczbową W( a ) = - 11 oraz W( b ) = 23, odpowiednio.

Rozwiązanie:

Korzystamy ze wzoru, który bajtowi a = ( a_1 , a_2, . . . , a_8) (czyli ciągowi (0,1)-owemu ze zbioru {0,1}^8) przyporządkowuje wartość


(*) W ( a ) := a_2 * 64 + a_3 * 32 + . . . + a_8 * 1 - a_1 * 128
Zatem a_1 = 1 (bo W(a) jest ujemne), zaś a_2 * 64 + a_3 * 32 + . . . + a_8 * 1 = -11 + 128 = 117. Z jednoznaczności rozwinięcia dwójkowego otrzymujemy:
a_2 = 1, a_3 = 1, a_4 = 1, a_5 =0, a_6 = 1, a_7 = 0, a_8 = 1
(sprawdzenie: 64 + 32 + 16 + 0*8 + 4 + 0*2 + 1 = 117). Zatem
a = ( 1, 1, 1, 1, 0, 1, 0, 1).
Podobnie, ze wzoru (*) zasosowanego do b otrzymamy b_1 = 0 (bo W( b ) jest dodatnie) i konsekwentnie
b_2 = 0, b_3 = 0, b_4 = 1, b_5 =0, b_6 = 1, b_7 = 1, b_8 = 1
(sprawdzenie: W( b ) = 0*64 + 0*32 + 16 + 0*8 + 4 + 2 + 1 - 0*128 = 23). Zatem
b = ( 0, 0, 0, 1, 0, 1, 1, 1).
Operacja ,or' zastosowana do a i b daje c = (1, 1, 1, 1, 0, 1, 1, 1). Korzystając jeszcze raz ze wzoru (*) tym razem zastosowanego do c otrzymujemy
W( c ) = 1*64 + 1*32 + 1*16 + 0*8 + 1*4 + 1*2 + 1*1 - 1*128 = -7.
Odpowiedź: W( c ) = -7.


Zadanie 3.8 (wprowadzenie do rekurencji). Udowodnić, że ciągi liczbowe S_n oraz T_n podane poniższymi równościami spełniają ten sam związek rekurencyjny. Korzystając z tego, że S_1 = T_1 wywnioskować stąd rowność S_n = T_n dla wszystkich n ze zbioru {1, 2, 3, . . .}. Oto równości definiujące:
S_n := 1 + 2 + . . . + n, T_n := 0.5 * n * (n+1), dla n = 1, 2, . . . .
Cz.1. Odpowiedź: Dla znalezienia wyrażenia na S_{n+1} przy pomocy S_n zapiszmy
S_{n+1} = 1 + 2 + . . . + n + (n+1)
S_n = 1 + 2 + . . . n,
a więc mamy:
(*) S_{n+1} = S_n + (n+1).
Dla znalezienia wyrażenia na T_{n+1} przy pomocy T_n zapiszmy
T_{n+1} = 0.5 * (n + 1) * ((n+1) + 1) = 0.5 * (n+1) * (n+2)
T_n = 0.5 * n * ( n+1 ) ,
a więc, wyłączając wspólny czynnik przed nawias, otrzymamy:
T_{n+1} - T_n = 0.5 * (n + 1) [ ( n+2) - n] = 0.5 * (n+1) * 2 = n+1,
czyli:
(**) T_{n+1} = T_n + (n+1).
Ponieważ formuły (*) i (**) są takie same, więc rzeczywiście ciągi S_n i T_n spełniają te same związki rekurencyjne.

Cz.2. Odpowiedź: Ponieważ S_1 = 1, T_1 = 0.5 * 1 * 2 =1, więc rzeczywiście S_1 = T_1. Ze wzorów rekurencyjnych udowodnionych w cz. 1 wynika, że dla każdego n ze zbioru {1,2,3 . . .} mamy
S_n = T_n implikuje S_{n+1} = T_{n+1}
Na mocy postulatu o indukcji matematycznej zupełmej wnosimy, że
S_n = T_n dla każdego n ze zbioru liczb naturalnych {1, 2, 3, . . . }
Dalsze zadania, bez rozwiązań:
Zadanie 3.9. Rozłożyć na czynniki pierwsze: 513, 76, 72, 5183, 427.

Zadanie 3.10. Obliczyć: 2^{25) mod 7;  3^{21} mod 8; 7^{40} mod 10 .

Zadanie 3.11. W pierścieniu Z_9 rozwiązać równania dla x z tego pierścienia lub pokazać brak rozwiązania:

    2 + 4*x = 0;   1+ 3*x = 4;   5 + x = 4.



Zadanie 3.12. Przy pomocy rozszerzonego algorytmu Euklidesa znaleźć d = NWD(a=650,b=156) oraz takie liczby całkowite x oraz  y, dla  których d = x*a + y*b.

Zadanie 3.13. Znaleźć wszystkie liczby całkowite  a spełniające warunki:  a mod 13 = 4, a mod 8 = 5,  a mod 3 = 0.

Zadanie 3.14. Znaleźć szyfr odwrotny do liniowego: y = (9* x+ 6) mod 26, dla  x z pierścienia Z_{26}. Przyjmując znaczenie literowe A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z  dla liczb 0,1,2,...,25,  odszyfruj wyraz (litera po literze):   ,,ZDJZL‘‘

Zadanie 3.15. Przy pomocy algorytmu rosyjskich chłopów obliczyć  247 * 163

.
Zapowiedź materiału do zestawu 4/7



PRZYKŁADY ZADAŃ NA FUNKCJE TWORZĄCE





©operacji.org 2017
wyślij wiadomość

    Strona główna