IB111 Základy programování Radek Pelánek
2018
O C S A R B V
E K T E O A
0AJLBNOCE 0CSBUJTMBWB
2/60
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	vw 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
4 □ ►   < [S ► <
■Š ►   <  -Š ►
Řetězce a znaky - ukázky operací
"kos" * 3
"petr" + "klič"
text = "velbloud"
len(text)
text [0]
text [2]
text [-1]
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 http://www.polylab.dk/utf8-vs-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(;A;)+i))
8/60
Řetězce - pokročilejší indexován
(specifické pro Python)
text = "velbloud"
text[:3]       # první 3 znaky
text [3:]       # od 3 znaku dále
text [1:8:2] # od 2. znaku po 7. krok po 2
text[::3]     # od začátku do konce po 3
v
Ř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" # chyba
text = text[:2] + "n" + text [3:]
10/60
Ř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
• ú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
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/60
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])
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
16/60
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?
17/60
Caesarova šifra - rozlomení
k	Kandidát	bs		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	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
18/60
\
Vigeněrova šifra
9 substituce podle hesla - „sčítáme" zprávu a heslo
• vhodné cvičení
• rozlomení Vigeněrovovy šifry?
19/60
Seznamy (pole) - motivace
• razení studentů podle bodů na písemce
• reprezentace herního plánu (piškvorky, šachy) o frekvence písmen v textu
20/60
Frekvenční analýza nevhodně
def frequency_analysis(text): text = text.upper() freqA = 0 freqB = 0 freqC = 0
for letter in text: if letter == 'A':
freqA += 1 elif letter == 'B':
freqB += 1 elif letter == 'C : freqC += 1 print('A', freqA) print('B', freqB) printCC, freqC)
0 12 3 4
• „více položek za sebou v pevném pořadí"
• indexováno od nuly
• základní koncept dostupný ve všech jazycích, běžně „pole" (array), položky stejného typu, pevně daná délka
• seznamy v Pythonu - obecnější (ale pomalejší)
• Python a pole - knihovna NumPy (nad rámec IB111)
22/60
Seznamy v Pythonu
0 12 3 4 -5 -4 -3 -2 -1
• variabilní délka
• položky mohou být různého typu
• indexování i od konce (pomocí záporných čísel)
23/60
v
Pyth
onu
s = [] # deklarace prázdného seznamu
s = [3, 4, 1, 8]
s [2]
s[-l]
s [2] = 15
# indexace prvku, s [2] = 1
# indexace od konce, s[-l] = 8
# změna prvku s.append(6) # přidání prvku
s[l:4] # indexace intervalu, síl:J^] = [4, 15,
len(s) # délka seznamu,  len(s) = 5
t = [3, "pes",  [2, 7] , -8.3]
# seznam může obsahovat různé typy
8]
list () - pretypovaní na seznam
•<□►   < @i ►   < -š ►   4 -E ►
Š      vT) O
24/60
Seznamy: konvence zápisu (PEP8)
• mezera se dělá: za čárkou
• mezera se nedělá: před čárkou, na „okrajích"
25/60
Python: seznamy a cyklus for
• cyklus for - přes prvky seznamu*
• range - vrací seznam* čísel
• typické použití: for i in range (n)
• ale můžeme třeba:
• for animal in ["dog", "cag", "pig"]: ...
• for letter in "hello world": ...
(*) ne úplně přesně - z důvodu efektivity se používají generátory a speciální „range object", v případě potřeby použijte explicitní pretypovaní na seznam: list (range (10))
26/60
Objekty, hodnoty, aliasy - stručné varování
a = [1,2,3] a = [1,2,3]
b = [1, 2, 3] nebo b = a[:]        b = a
[1,2,3] a—►[1,2,3]
b-M1,2,3] b
• parametry funkcí - pouze volání hodnotou
(na rozdíl např. od Pascalu: volání hodnotou a odkazem)
• měnitelné objekty (např. seznam) však funkce může měnit
• mělká vs hluboká kopie
• více později
27/60
Vi
zuaiizace
běhu
programu
http://www.pythontutor.com/
x = [1. 2. 3] y =  [4.  5. 6]
z = y y = x x = z
6
x = [1.  2.  3]  # a different  [1.  2,  3] list!
y = x
x.append(4) y.append(5)
z = [1.  2.  3. 4.  5]  # a different list!
12 x.append(6)
13 y.append(7)
14 y = "hello"
Frames
Objects
0	i	2	
4	5	6	
ist			
0	L	2	3
1	2	3	4
vhodné např. pokud je nejasný některý z příkladů ve slidech
28/60
• n-tice (tuples)
• neměnitelná varianta seznamů
• kulaté závorky místo hranatých (někdy lze vynechat): t = (1, 2, 3)
• neměnitelné podobně jako řetězce
• typické užití:
• souřadnice: (x, y)
• barva: (r, g, b)
o použití pro přiřazení: a, b = b, a
29/60
výpočet průměrné hodnoty
def average1(num_list): total = 0
for i in range(len(num_list)):
total += num_list[i] return total / len(num_list)
def average2(num_list): total = 0 for x in num_list:
total += x return total / len(num_list)
def average3(num_list):
return sum(num_list) / len(num_list)
30/60
Ilustrace práce se seznamem
def divisors_list(n): divisors = [] for i in ranged, n+1) : if n °/0 i == 0:
divisors.append(i) return divisors
divisors24 = divisors_list(24)
print(divisors24)
print(len(divisors24))
for x in divisors24: print(x**2)
Frekvenční analýza nevhodně
def frequency_analysis(text): text = text.upper() freqA = 0 freqB = 0 freqC = 0
for letter in text: if letter == 'A':
freqA += 1 elif letter == 'B':
freqB += 1 elif letter == 'C : freqC += 1 print('A', freqA) print('B', freqB) printCC, freqC)
Frekvenční analýza lépe
def frequency_analysis(text): text = text upper() frequency = [0 for i in range(26)] for letter in text:
if ord(letter) >= ord(;A;) and\ ord(letter) <= ord(;Z;): frequency[ord(letter) - ord(;A;)] += for i in range(26):
if frequency[i]   != 0:
print(chr(ord(;A;)+i), frequency [i])
Simulace volebního průzkumu - nevhodné řešen
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 += 1 print ("Party 1:11, 100 * count 1 / size) print("Party 2:", 100 * count2 / size) print("Party 3:", 100 * count3 / size)
34/60
Simulace volebního průzkumu - lepší řešení
def survey(size, pref): n = len(pref)
count = [0 for i in range(n)] for _ in range(size):
r = random.randint(1, 100) for i in range(n):
if sum(pref [:i]) < r <= sum(pref [:i+1]) count [i] += 1 for i in range(n):
print("Party", i+1, 100 * count [i] / size)
Toto řešení má stále nedostatky (po stránce funkčnosti) -zkuste dále vylepšit.
35/60
• vstup: řetězec
• výstup: zápis v Morseově abecedě
• příklad: PES —. —. I . I . . .
36/60
Prevod do Morseovy abecedy nevhodně
def to_morse_poor(text): result = ;;
for i in range(len(text)):
if text[i] == ;A;: result += ;.-
elif text[i] == ;B;: result += ;
elif text[i] == ;C;: result += ;
elif text[i] == ;D;: result += ;
# etc return result
37/60
Prevod do Morseovy abecedy: využití seznamu
morse = [;.-;, ;-..;] # etc
def to_morse(text): result = ;;
for i in range(len(text)):
if ord(;A;) <= ord(text[i]) <= ord(;Z;):
c = ord(text[i]) - ord(;A;)
result += morse[c] + ;|; return result
(ještě lepší řešení: využití slovníku - bude později)
Prevod z Morseovy abecedy
def find_letter(sequence):
for i in range(len(morse)): if morse[i] == sequence: return chr(ord(;A;) + return ;?;
def from_morse(message): result = ;; sequence = ;; for symbol in message: if symbol == ;I;:
result += find_letter sequence = ;; else:
sequence += symbol return result
Split - seznam z řetězce
split - rozdělí řetězec podle zadaného oddělovače, vrátí seznam
>» vowels = Ma,e, i,o,u,yn »> vowels, split (11,11)
e
i
o
u
]
»> message = — »> message. split (" I")
_ ii
j   _     ;      ;___;      ; _ ;
<  □  ►    < [fpl ►    < ■£ ►    <  -Š ►
40/60
Príklad - načítání vstupu od uživatele
»> input_string = input () 3 7
»> xstring, ystring = input_string.split( »> x = int(xstring) »> y = int (ystring)
< □  ►   < [f}P ►   4 S
Výškový prof i
475 m n.m.
Stoupání: 367 m
Klesaní: 363 m
mapy.cz
42/60
heights_profile( [3, 4, 5, 3, 4, 3, 2, 4, 5, 6, 5])
###### #### ########### ###########
Ascent 7 Descent 5
#
# #
#
#
# # # # # # #
43/60
def heights_profile(heights):
for v in range(max(heights)):
for i in range(len(heights)):
if heights [i] >= max(heights) - v:
print ("#", end=M 11) else:
print ("    5 end=M 11)
print() print()
44/60
def elevation(heights): ascent = 0 descent = 0
for i in range(len(heights)-1): if heights [i] < heights [i+1]:
ascent += heights[i+1] - heights [i] else:
descent += heights [i] - heights [i+1] print ("Ascent11, ascent) print ("Descent11, descent)
45/60
Explicitní vzorec
(n)
i     t (n\ — n!
(o) (i) ™ ~ (n-fc)!fc!
Rekurzivní vztah
© Q ©
© © © © ffl = (n1) + Cí1)
46/60
Pascalův trojúhelník
def get_next_row(row): next_row = [1] for i in range(len(row)-1):
next_row.append(row [i]+row [i+1]) next_row.append(1) return next_row
def pascal_triangle(n): row = [1]
for i in range(n): print(row)
row = get_next_row(row)
Kompaktní zápis
pro zajímavost:
def get_next_row(row):
return [1] + [sum(p) for p in zip(row, row[1:])] + [1]
< [f? ►  < -E ►  < -ž ►      -š     O Q, O
48/60
• dělitelné jen 1 a sebou samým
• předmět zájmu matematiků od pradávna, cca od 70. důležité aplikace (moderní kryptologie)
• problémy s prvočísly:
• výpis (počet) prvočísel v intervalu
• test prvočíselnosti
• rozklad na prvočísla (hledání dělitelů)
let i
49/60
Výpis prvočísel přímočaré
def print_primes(how_many): n = 1
while how_many > 0:
if len(divisors_list(n)) == 2: print(n, end=M 11) how_many -= 1 n += 1 print()
50/60
Odbočka: test prvočíselnosti, kryptografie
Test prvočíselnosti:
• zkoušíme všechny možné dělitele od 2 do n — 1
• vylepšení:
• dělíme pouze dvojkou a lichými čísly
• dělíme pouze dvojkou a čísly tvaru 6/c ± 1
• dělíme pouze do yfn
51/60
Test prvočíselnosti: chytřejší algoritmy
• náhodnostní algoritmy
9 polynomiální deterministický algoritmus (objeven 2002)
• (vysoce) nad rámec tohoto kurzu
• umí se to dělat rychle
4 ^ >■   4 ± k   <  -Š ►
52/60
Rozklad na prvočísla
• rozklad na prvočísla = faktorizace
• naivní algoritmy:
• průchod všech možných dělitelů
• zlepšení podobně jako u testů prvočíselnosti
• chytřejší algoritmy:
• složitá matematika
• aktivní výzkumná oblast
• neumí se to dělat rychle
• max cca 200 ciferná čísla
53/60
Příklad aplikace: asymetrická kryptologie
	Bob		
Hello Alice!		Encrypt	
	♦		
		6EB69570 08E03CE4	
			
Alice			f
Hello Alice!		■ Decrypt	
Alice's public key
Alice's private key
http://en.wikipedia.org/wiki/Public-key_cryptography
54/60
Asymetrická kryptologie: realizace
• jednosměrné funkce
• jednoduché vypočítat jedním směrem
• obtížné druhým (inverze)
• ilustrace: míchání barev
• RSA (Rivest, Shamir, Adleman) algoritmus
• jednosměrná funkce: násobení prvočísel (inverze = faktorizace)
» veřejný klíč: součin velkých prvočísel
• bezpečnost ~ nikdo neumí provádět efektivně faktorizaci
• využití modulární aritmetiky Eulerovy věty ...
55/60
Eratosthenovo síto
• problém: výpis prvočísel od 2 do n
• algoritmus: opakovaně provádíme
• označ další neškrtnuté číslo na seznamu jako prvočíslo
• všechny násobky tohoto čísla vyškrtni
56/60
57/60
def
def
thenovo síto
reset_multiples(is_candidate, i): k = 0
while k < len(is_candidate): is_candidate[k] = 0 k += i
eratosthenes(n):
is_candidate = [1 for _ in range(n)] for i in range(2, n): if is_candidate [i]:
print (i, end=" 11) reset_multiples(is_candidate, i)
Pozn. Všimněte si, že funkce mění seznam.
58/60
• prvočísla - Ulamova spirála
• Pascalův trojúhelník - obarvení podle sudosti -Sierpiňského trojúhelník
Vi Hart: Doodling in math: Sick number games
https : //www.khanacademy. org/math/recreational-math/vi-hart/doodling-in-math/v/ doodling- in-math-sick-number-games
59/60
Seznamy, řetězce:
• základní operace
• ukázky použití
• kryptografické příklady (historické) a souvislosti (moderní) Příště: Vyhledávání, řadicí algoritmy
4 ^ >■   4 ± k   4  S ►
60/60