IB113 Radek Pelánek
2021
Rozcvička: šifry
O C S A R B V
E K T E 0 A
0AJLBNOCE
©OUAGADOUGOU 0CSBUJTMBWB
2/42
zicni sitry
pozpátku
E	S	A	R	P	E	J	0	L	S	E	H
trojice pozpátku
S	E	H	J	0	L	R	P	E	E	S	A
ob tři
dopředu dozadu
H	0	R	E	J	A	S	E	S	L	P	E
H	S	0	E	R	S	E	A	P	J	L	E
šnek
L	B	A	K	1	N
1	C	S	E	J	B
Z	H	0	P	D	Y
K	0	K	L	A	R
0	V	A	N	Y	U
U	H	R	A	Z	E
cik-cak
					
				\	
\					
K	'N				
\	-N				
					
N	1	0	U	Z	E
H	B	K	K	H	A
C	0	Y	A	Z	R
L	S	V	R	B	1
K	A	E	A	U	L
P	0	D	J	N	Y
Substituční šifry
Jednoduchá substituce - posun o 3 pozice
k	0	z	a
1	t	I	
10	14	25	0
+ 3 |	t	í	
13	17	2	3
1		1	t
n	r	c	d
Substituce podle hesla
hledejpodlipou Ilonslonslonsl
IwSQWUDBVWWCGF
h
7
18
+
25
	A	B	C	D	E	F	G	H	1	J	K	L	M	N	0	P	Q	R	S	T	u	v W X			Y	Z
A	A	B	C	D	E	F	G	H	1	J	K	L	M	N	0	P	Q	R	S	T	u	V W x			Y	z
B	B	C	D	E	F	G	H	1	J	K	L	M	N	0	P	Q	R	S	T	U	v w x			Y	Z	A
C	C	D	E	F	G	H	1	J	K	L	M	N	0	P	Q R		S	T	U	V	w x		Y	Z	A	B
D	D	E	F	G	H	1	J	K	L	M	N	0	P	Q	R	S	T	U	V W		x	Y	Z	A	B	C
E	E	F	G	H	1	J	K	L	M	N	0	P	Q R		S	T	U	V	w x		Y	Z	A	B	C	D
F	F	G	H	1	J	K	L	M	N	0	P	Q	R	S	T	U	V	W	x	Y	Z	A	B	C	D	E
G	G	H	1	J	K	L	M	N	0	P	Q	R	S	T	U	V W		x	Y	Z	A	B	C	D	E	F
H	H	1	J	K	L	M	N	0	P	Q R		S	T	U	V W X			Y	Z	A	B	C	D	E	F	G
1	1	J	K	L	M	N	0	P	Q	R	S	T	U	V W X			Y	Z	A	B	C	D	E	F	G	H
J	J	K	L	M	N	0	P	Q	R	S	T	U	VW X			Y	Z	A	B	C	D	E	F	G	H	1
K	K	L	M	N	0	P	Q	R	S	T	U	V	w x		Y	Z	A	B	C	D	E	F	G	H	1	J
L	L	M	N	0	P	Q	R	S	T	U	V w		x	Y	Z	A	B	C	D	E	F	G	H	1	J	K
M	M	N	0	P	Q R		S	T	U	VW X			Y	Z	A	B	C	D	E	F	G	H	1	J	K	L
N	N	0	P	Q	R	S	T	U	v w x			Y	Z	A	B	C	D	E	F	G	H	1	J	K	L	M
0	0	P	Q	R	S	T	U	V	w x		Y	Z	A	B	C	D	E	F	G	H	1	J	K	L	M	N
P	P	Q R		S	T	U	V	W	x	Y	Z	A	B	C	D	E	F	G	H	1	J	K	L	M	N	0
Q	Q	R	S	T	U	V	W	x	Y	Z	A	B	C	D	E	F	G	H	1	J	K	L	M	N	0	P
R	R	S	T	U	V W		x	Y	Z	A	B	C	D	E	F	G	H	1	J	K	L	M	N	0	P	Q
S	S	T	U	V	w x		Y	Z	A	B	C	D	E	F	G	H	1	J	K	L	M	N	0	P	Q	R
T	T	U	V W		x	Y	Z	A	B	C	D	E	F	G	H	1	J	K	L	M	N	0	P	Q	R	S
U	U	vw X			Y	Z	A	B	C	D	E	F	G	H	1	J	K	L	M	N	0	P	Q	R	S	T
V	V	w x		Y	Z	A	B	C	D	E	F	G	H	1	J	K	L	M	N	0	P	Q R		S	T	U
w	w	x	Y	Z	A	B	C	D	E	F	G	H	1	J	K	L	M	N	0	P	Q	R	S	T	U	V
x	x	Y	Z	A	B	C	D	E	F	G	H	1	J	K	L	M	N	0	P	Q	R	S	T	U	V W	
Y	Y	Z	A	B	C	D	E	F	G	H	1	J	K	L	M	N	0	P	Q R		S	T	U	V W X		
Z	Z	A	B	C	D	E	F	G	H	1	J	K	L	M	N	0	P	Q	R	S	T	U	V W X			Y
< □ ► 4 gi ► 4
■g ► < -š ►
Řetězce a znaky - ukázky operací
ii
"kos" * 3 "petr" + "klic text = "velbloud" len(text) text [0] text [2] text [-1] "e" in text ord('b') chr(99)
str () - explicitní pretypovaní na řetězec
• jiné jazyky často: uvozovky pro řetězce, apostrofy pro znaky
• Python: lze používat uvozovky i apostrofy
• PEP8: hlavně konzistence
Indexování od nuly
Proč indexujeme od 0?
• částečně „historicky-technické" důvody
• ale i dobré „matematické" důvody
Pro zájemce:
Why numbering should start at zero (Edsger W. Dijkstra)
http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html
http: //programmers . stackexchange. com/questions/110804/why-are-zero-based-arrays-the-norm https : //www. quora. com/Why-do- array- indexes- start-with- 0-zero- in-many-programming- languages
• jak jsou znaky reprezentovány?
ASCII, ISO 8859-2, Windows-1250, Unicode, UTF-8, ..
http://www.joelonsoftware.com/articles/Unicode.html
• Python3 - Unicode řetězce
• pro tento kurz:
• ord, chr - převod znaků na čísla a zpět
• anglická abeceda má přiřazena po sobě jdoucí čísla
for i in range(26):
print(chr(ord(1A1)+i))
v
Řetězce - pokročilejší indexován
(specifické pro Python)
text = "velbloud"
text[:3]       # prvni 3 znaky
text [3:]       # od 3 znaku dale
text [1:8:2] # od 2. znaku po 7. krok po 2
text[::3]     # od začátku do konce po 3
Řetězce - změny
• neměnitelné (immutable) - rozdíl oproti seznamům a oproti řetězcům v některých jiných jazycích
• změna znaku - vytvoříme nový řetězec
text = "kopec"
text [2] = "n" # error
text = text[:2] + "n" + text [3:]
10/42
Řetězce: další operace
text = "i Have a dream."
print(text.upper())
print(text.lower())
print(text.capitalize())
print(text.rjust(30))
print("X", text.center(30), "X")
print(text.replace("dream", "nightmare"))
... a mnoho dalších, více později, příp. viz dokumentace Pozn. objektová notace
Příklad: Transpozice (rozcvička 1)
úkol: přepis textu do N sloupců příklad vstupu a výstupu:
• CESKATREBOVA, 2
• C S A R B V E K T E 0 A
12/42
Transpozice (rozcvicka 1)
def cipher_columns(text, n): for i in range(n):
for j in range(len(text) // n + 1): position = j * n + i if position < len(text):
print (text [position] , end=IMI)
print()
13/42
Transpozice (rozcvička 1), kratší varianta
Za využití notace specifické pro Python
def cipher_columns(text, n): for i in range(n):
print(text[i::n])
14/42
Príklady interaktivně: řetězce, vnorené cykly
Oua
gad
oug
ou
0
u
0 a u     d o a     o u u
0 a u g d u o a     o u
o
u
o
u
15/42
Caesarova šifra (rozcvička 3)
• substituční šifra - posun v abeced
• vstup: text, posun
• výstup: zašifrovaný text
• BRATISLAVA, 1 CSBUJTMBWB
Caesarova šifra - řešení
def caesar_cipher(text, n): result = 1111 text = text upper() for i in range(len(text)): if text [i] == 11 11:
result = result + else:
c = ord(text [i]) + n
if (c > ord(MZM)): c = c - 26
result = result + chr(c)
Pozn. Řešení má nedostatky - zkuste najít a vylepšit.
return result
17/42
Caesarova šifra - rozlomení
• máme text zašifrovaný Caesarovou šifrou (s neznámým posunem)
• jak text dešifrujeme?
• príklad: MPKTWTDVLVELMZCF
< □ ►   4 S1 ►   < -ž ►   < -E ►
18/42
Caesarova šifra - rozlomení
• máme text zašifrovaný Caesarovou šifrou (s neznámým posunem)
• jak text dešifrujeme?
• príklad: MPKTWTDVLVELMZCF
• jak to udělat, aby program vrátil jen jednoho kandidáta?
•<□►   4 ^ >■   <  -ž  ►   <  -š ►
18/42
Caesarova šifra - rozlomení
k	Kandidát	bs	h	k	Kandidát	bs	h
0	MPKTWTDVLVELMZCF	0	21	13	ZCXGJGQIYIRYZMPS	0	-13
1	NQLUXUEWMWFMNADG	13	0	14	ADYHKHRJZJS ZANQT	0	16
2	ORMVYVFXNXGNOBEH	24	9	15	BEZILISKAKTABGRU	67	59
3	PSNWZWGYOYHOPCFI	5	-3	16	CFAJMJTLBLUBCPSV	0	11
4	QTOXAXHZPZIPQDGJ	10	-6	17	D GBKNKUMCMVCD QTW	5	-4
5	RUPYBYIAQAJQREHK	0	9	18	E H C LOLVNDNWD E RUX	17	31
6	SVQZCZJBRBKRSFIL	0	3	19	FIDMPMWOEOXEFSVY	5	22
7	TWRADAKCSCLSTGJM	32	26	20	GJENQNXPFPYFGTWZ	4	-23
8	UXSBEBLDTDMTUHKN	0	24	21	HKFOROYQGQZGHUXA	16	-17
9	VYTCFCMEUENUVILO	11	46	22	ILGPSPZRHRAHIVYB	28	18
10	WZUDGDNFVF0VWJMP	0	-6	23	JMHQTQASISBIJWZC	9	0
11	XAVEHEOGWGPWXKNQ	5	-2	24	KNIRURB T J T C JKX AD	5	24
12	YBWFIFPHXHQXYLOR	0	-28	25	LOJSVSCUKUDKLYBE	4	29
19/42
Vigeněrova šifra
a substituce podle hesla - „sčítáme" zprávu a heslo
• vhodné cvičení
• rozlomení Vigeněrovovy šifry?
20/42
Řetězce a for cyklus
Můžeme iterovat přímo přes jednotlivá písmena.
text = "prase"
for i in range(len(text)):
print(text [i]) for letter in text:
print(letter)
Velmi nevhodný hybrid:
for i in text: print(i)
21 /42
Náhodná čísla
• přesněji: pseudo-náhodná čísla
• opravdová náhodná čísla: https://www.random.org/
• bohaté využití v programování: výpočty, simulace, hry,
• Python
• import random
• random.random() - float od O do 1
• random.randint (a, b) - celé číslo mezi a, b
• mnoho dalších funkcí
22/42
Nahodn
a cisia: x
kcd
ini getR&ndomNumber()
}
return H*, //chosen by fair d/ce roll II guaranteed to be random
THIS ArAf RANDOfl NUMBER GENFMCiR VOL? UfiOTE CUW15
id be fair, Bur the: output i& biased tdu\rt; amihi numbers.
UJEtt* tffltBE THOSE NUMBERSAFEJVST JfflmtSlCftLLYSETTER!
htts://xkcd.com/221/ htts://xkcd.com/1277/
23/42
Náhodná čísla: průměr vzorku
Vygenerujeme náhodná čísla a vypočítáme průměrnou hodnotu:
def random_average(count, maximum=100): total = 0
for i in range(count):
total += random.randint(0, maximum) return total / count
Jakou očekáváme hodnotu na výstupu? Jak velký bude rozptyl hodnot? (Názorná ukázka centrální limitní věty)
24/42
Simulace volebního průzkumu
• volební průzkumy se často liší; jaká je jejich přesnost?
• prístup 1: matematické modely, statistika
• prístup 2: simulace
• program:
• vstup: preference stran, velikost vzorku
• výstup: preference zjištěné v náhodně vybraném vzorku
Simulace volebního průzkumu
def survey(size, prefl, pref2, pref3): count1 = 0 count2 = 0 count3 = 0
for i in range(size):
r = random.randint(1, 100) if r <= prefl: count1 += 1 elif r <= prefl + pref2: count2 += 1 elif r <= prefl + pref2 + pref3: count3 print ("Party 1:11, 100 * count 1 / size) print("Party 2:", 100 * count2 / size) print("Party 3:", 100 * count3 / size)
Poznámky ke zdrojovému kódu
• uvedené řešení není dobré:
• „copy & paste" kód
• funguje jen pro 3 strany
• lepší řešení - využití seznamů (příště)
27/42
• tt = 3.14159265359...
• Ale jak se na to přišlo?
• Jak vypočítat tt?
28/42
Příklady naivních metod: • Gregoryho-Leibnizova řada
oo
(_1)* 44444
tt = 4- >   \   ;   =---+---+ --
+ l     1    3    5    7 9
k=0
• Monte Carlo metoda - házení šipek do čtvrtdisku, Buffonova jehla
29/42
Výpočet TT - Gregory-Leibniz
def gregory_leibniz(n): total = 0 sign = 1
for k in ranged, n+1) :
total += sign / (2*k-l) sign *= -1
return 4*total
30/42
Výpočet 7T - Monte Carlo
1
y
0
x 1
• obsah čtvrtdisku: tt/4
• obsah čtverce: 1
31 /42
Výpočet 7T - Monte Carlo
def monte_carlo_disc(attempts) hits = 0
for k in range(attempts): x = random.random() y = random.random() if x*x + y*y < 1: hits += 1
return 4 * hits / attempts
•<□►   4 ^ t   <  -Ž  ►   4 S ►
33/42
men, nůžky, papír
•<□►   4 ^ t   <  -ž  ►   4 >
34/42
KNP: strategie
def strategy_uniform():
r = random.randint(1, 3) if r == 1:
return "R" elif r == 2:
return "S" else:
return "P"
def strategy_rock(): return "R"
35/42
KNP: vyhodnocení tahu
def evaluate(symbol1, symbol2): if symboll == symbol2:
return 0 if symboll == MRM and symbol2 symboll == MSM and symbol2 symboll == MPM and symbol2 return 1 return -1
KNP: sehrání západu
def rsp_game(rounds): points = 0
for i in ranged, rounds+1) : print ("Round ", i) symbol1 = strategy_uniform() symbol2 = strategy_uniform() print("Symbols:", symboll, symbol2) points += evaluate(symboll, symbol2) print("Player 1 points:", points)
37/42
KNP: obecnější strategie
def strategy(weightR, weights, weightP):
r = random.randint(1, weightR + weights + weightP) if r <= weightR:
return "R" elif r <= weightR + weights:
return "S" else:
return "P"
38/42
KNP: rozšiřující náměty
• turnaj různých strategií
• strategie pracující s historií
• kopírování posledního tahu soupeře
• analýza historie soupeře (hraje vždy kámen? —> hraj papír)
• rozšíření na více symbolů (Kámen, nůžky, papír, ještěr, Spock)
39/42
Kontrolní otázky
• Co znamená „indexování od nuly"?
• Jaký je význam funkcí chr a ord?
• Jak zjistíme délku řetězce?
• Jak zjistíme, zda řetězec obsahuje znak X?
• Jak vypíšeme řetězec pozpátku?
• Jaký je význam sčítání řetězců? Můžeme řetězce násobit?
• Jakým způsobem vygenerujeme náhodné číslo?
• K čemu lze využít náhodná čísla?
•<□►   4 ^ t   <  -ž  ►   <  -š ►
https://www.umimeprogramovat.cz/rozhodovacka https://www.umimeprogramovat.cz/porozumeni https://www.umimeprogramovat.cz/vystup-programu
^> sada „Řetězce"
41 /42
Shrnutí
• řetězce, znaky
• náhodná čísla
• ukázky, příklady
příště: seznamy
42/42