IB113 Radek Pelánek
2019
O C S A R B V
E K T E O A
0AJLBNOCE 0CSBUJTMBWB
2/41
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
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	t	t
10	14	25	0
+ 3 |	1	1	1
13	17	2	3
1	t	1	
n	r	c	d
Substituce podle hesla
hledejpodlipou Ilonslonslonsl zwsqwudbvwwcgf s
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	V W 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	V W 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	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
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	VW 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
■g ► < -š ►
Řetězce a znaky - ukázky operací
"kos" * 3
"petr" + "klič"
text = "velbloud"
len(text)
text [0]
text [2]
text [-1]
"e" in text
ordCb')
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))
Ř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/41
Ř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/41
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="")
print()
13/41
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/41
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/41
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/41
Caesarova šifra - rozlomení
• máme text zašifrovaný Caesarovou šifrou (s neznámým posunem)
• jak text dešifrujeme?
• príklad: MPKTWTDVLVELMZCF
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 S1 ►   < -ž ►   < -E ►
18/41
Caesarova šifra - rozlomení
k	Kandidát	bs		k	Kandidát	bs	
0	MPKTWTDVLVELMZCF	0	21	13	ZCXGJGQIYIRYZMPS	0	-13
1	NQLUXUEWMWFMNADG	13	0	14	ADYHKHRJZJS ZANQT	0	16
2	ORMVYVFXNXGNOBEH	24	9	15	BEZILISKAKTABORU	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 ERUX	17	31
6	SVQZCZJBRBKRSFIL	0	3	19	FIDMPMWOEOXEF SVY	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	WZUDGDNFVF 0VW JMP	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/41
Vigeněrova šifra
9 substituce podle hesla - „sčítáme" zprávu a heslo
• vhodné cvičení
• rozlomení Vigeněrovovy šifry?
•<□►   4 ^ t   <  -ž  ►   <  -š ►
20/41
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í
21 /41
Náhodná čŕsla: xkcd
iní get R<*n dom N vrti ber ()
í
i
return 4,' //chosen by fair dice, roll // guaranteed to be rano/om.
THIS m RANDOM NUMBER
GocmiDR voľ uttmcw/m
TO BE miř> BUTTHEOUlPlřTío BIASED CERffllM MUrIBEľRS.
/  (JOl, ř?#rf$E THOSE I   NUM6ER5 ARE JUST /rm/NStCALLYBETTER/
htts://xkcd.com/221/ htts://xkcd.com/1277/
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 hodnot? (Názorná ukázka centrální limitní věty)
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ů
• tt = 3.14159265359...
• Ale jak se na to přišlo?
• Jak vypočítat tt?
27/41
Příklady naivních metod: • Gregoryho-Leibnizova řada
oo
(_1)* 44444
tt = 4- >   --— =---H----H---
+ l     1    3    5 79
k=0
• Monte Carlo metoda - házení šipek do čtvrtdisku, Buffonova jehla
•<□►   4 ^ t   <  -Ž  ►   4 S ►
Š      vT) Q^O
28/41
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
29/41
Výpočet 7T - Monte Carlo
1
y
0
x 1
• obsah čtvrtdisku: tt/4
• obsah čtverce: 1
30/41
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
32/41
men, nůžky, papír
Zdroj: Wikipedia
33/41
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"
34/41
KNP: vyhodnocení tahu
def evaluate(symbol1, symbol2): if symboll == symbol2:
return 0 if symboll == "R" and symbol2 symboll == "S" and symbol2 symboll == "P" 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)
36/41
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"
37/41
KNP: rozšiřující náměty
• turnaj různých strategií
• strategie pracující s historií
9 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)
38/41
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?
https://www.umimeprogramovat.cz/rozhodovacka https://www.umimeprogramovat.cz/porozumeni https://www.umimeprogramovat.cz/vystup-programu
^> sada „Řetězce"
40/41
• řetězce, znaky
• náhodná čísla
9 ukázky, příklady
příště: seznamy