Řetězce a seznamy
(a kryptografické odbočky)
IB111 Úvod do programování skrze Python
2013
1 / 50
Rozcvička: šifry
1 C S A R B V
E K T E O A
2 C S B U J T M B W B
3 A J L B N O C E
2 / 50
Transpoziční šifry
HESLOJEPRASE
H E S LO J E PR A S E
HES LOJ EPR ASE
H ES LO JE PR AS E
pozpátku trojice pozpátku
ob tři dopředu dozadu
šnek cik-cak
PO
K L A
D
JESC
H
O
V A N Y U
R
Y
B
NIABL
I
Z
K
O
U H R A Z E P O
K
L
A
D J
E
S
C
H
O
V
A
N Y
U
R
Y
B
N I
A
B
L
I
Z
K
O U
H
R
A
Z EK
K
3 / 50
Substituční šifry
K O Z A
10 14 25 0
13 17 2 3
N R C D
+3
ZWSQWUDBVWWCGF
SLONSLONSLONSL
HLEDEJPODLIPOU
Jednoduchá substituce - posun o 3 pozice
Substituce podle hesla
H
S 18
7
25 Z+
4 / 50
Řetězce a znaky – ukázky operací
"kos" * 3
"petr" + "klic"
text = "velbloud"
len(text)
text[0]
text[2]
text[-1]
ord(’b’)
chr(99)
str() – explicitní přetypování na řetězec
5 / 50
ASCII tabulka, ord, chr
6 / 50
Řetězce – pokročilejší indexování
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
7 / 50
Řetězce – změny
neměnitelné (immutable) – rozdíl oproti seznamům a
ř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:]
8 / 50
Řetězce: další operace
text = "bezi liska k Taboru"
print text.upper()
print text.lower()
print text.capitalize()
print text.rjust(30)
print "X",text.center(30),"X"
print text.replace("liska","jezek")
... a mnoho dalších, více viz dokumentace, později.
9 / 50
Příklad: Transpozice (rozcvička I)
přepis textu po sloupcích:
příklad vstupu a výstupu:
CESKATREBOVA
C S A R B V
E K T E O A
10 / 50
Transpozice (rozcvička I)
def sifra_po_sloupcich(text,n):
for i in range(n):
for j in range(len(text) / n + 1):
pozice = j * n + i
if pozice < len(text):
print text[pozice],
print
11 / 50
Transpozice (rozcvička I), kratší varianta
def sifra_po_sloupcich(text,n):
for i in range(n):
print text[i::n]
12 / 50
Caesarova šifra (rozcvička II)
substituční šifra – posun v abecedě
vstup: text, posun
výstup: zašifrovaných text
BRATISLAVA, 1 → CSBUJTMBWB
13 / 50
Caesarova šifra – řešení
def caesarova_sifra(text, n):
vystup = ""
text = text.upper()
for i in range(len(text)):
if text[i] == ’ ’: vystup = vystup + ’ ’
else:
c = ord(text[i]) + n
if (c > ord(’Z’)): c = c - 26
vystup = vystup + chr(c)
return vystup
14 / 50
Caesarova šifra – rozlomení
máme text zašifrovaný Caesarovou šifrou (s neznámým
posunem)
jak text dešifrujeme?
příklad: MPKTWTDVLVELMZCF
15 / 50
Caesarova šifra – rozlomení
máme text zašifrovaný Caesarovou šifrou (s neznámým
posunem)
jak text dešifrujeme?
příklad: MPKTWTDVLVELMZCF
jak to udělat, aby program vrátil jen jednoho kandidáta?
15 / 50
Caesarova šifra – rozlomení
16 / 50
Vigen`erova šifra
substituce podle hesla – „sčítáme zprávu a heslo
vhodné cvičení
rozlomení Vigen`erovovy šifry?
17 / 50
Seznamy (pole) – motivace
řazení studentů podle bodů na písemce
reprezentace herního plánu (piškvorky, šachy)
frekvence písmen v textu
18 / 50
Frekvenční analýza nevhodně
def frekvencni_analyza(text):
frekA = 0
frekB = 0
frekC = 0
for pismeno in text:
if pismeno == ’A’:
frekA += 1
elif pismeno == ’B’:
frekB += 1
elif pismeno == ’C’:
frekC += 1
print ’A’, frekA
print ’B’, frekB
print ’C’, frekC
19 / 50
Seznamy (pole)
0 1 2 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ší
Python a pole – knihovna NumPy (nad rámec IB111)
20 / 50
Seznamy v Pythonu
0 1 2 3 4
-1-2-3-4-5
seznam (list), n-tice (tuple)
položky mohou být různého typu
variabilní délka
indexování i od konce (pomocí záporných čísel)
21 / 50
Seznamy: použití v Pythonu
s = [] # deklarace prázdného seznamu
s = [3, 4, 1, 8 ]
s[2] # indexace prvku, s[2] = 1
s[-1] # indexace od konce, s[-1] = 8
s[2] = 15 # změna prvku
s.append(6) # přidání prvku
s[1:4] # indexace intervalu, s[1:4] = [4, 15, 8]
len(s) # délka seznamu, len(s) = 5
t = [ 3, "pes", [2, 7], -8.3 ]
# seznam může obsahovat různé typy
list() – přetypování na seznam
22 / 50
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 i:
for zvire in ["pes", "kocka", "prase"]: ...
for pismeno in "velbloud": ...
23 / 50
Objekty, hodnoty, aliasy
a = [1, 2, 3]
b = [1, 2, 3] nebo b = a[:]
a = [1, 2, 3]
b = a
[1, 2, 3]
[1, 2, 3]
[1, 2, 3]a
b
a
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
n-tice (tupples) – neměnitelná varianta seznamů
více na cvičeních, později
24 / 50
Vizualizace běhu programu
http://www.pythontutor.com/
vhodné např. pokud je nejasný některý z příkladů ve slidech
25 / 50
Příklad: výpočet průměrné hodnoty
def prumer1(seznam):
soucet = 0.0
for i in range(len(seznam)):
soucet += seznam[i]
return soucet / len(seznam)
def prumer2(seznam):
soucet = 0.0
for x in seznam:
soucet += x
return soucet / len(seznam)
def prumer3(seznam):
return float(sum(seznam)) / len(seznam)
26 / 50
Ilustrace práce se seznamem
def seznam_delitelu(n):
delitele = []
for i in range(1, n+1):
if n % i == 0:
delitele.append(i)
return delitele
delitele24 = seznam_delitelu(24)
print delitele24
print len(delitele24)
for x in delitele24: print x**2,
27 / 50
Frekvenční analýza nevhodně
def frekvencni_analyza(text):
frekA = 0
frekB = 0
frekC = 0
for pismeno in text:
if pismeno == ’A’:
frekA += 1
elif pismeno == ’B’:
frekB += 1
elif pismeno == ’C’:
frekC += 1
print ’A’, frekA
print ’B’, frekB
print ’C’, frekC
28 / 50
Frekvenční analýza lépe
def frekvencni_analyza(text):
frekvence = [ 0 for i in range(26) ]
for pismeno in text:
if ord(pismeno) >= ord(’A’) and\
ord(pismeno) <= ord(’Z’):
frekvence[ord(pismeno) - ord(’A’)] += 1
for i in range(26):
if frekvence[i] != 0:
print chr(ord(’A’)+i), frekvence[i]
29 / 50
Simulace volebního průzkumu – nevhodné řešení
def pruzkum(vzorek, pref1, pref2, pref3):
pocet1 = 0
pocet2 = 0
pocet3 = 0
for i in range(vzorek):
r = random.randint(1,100)
if r <= pref1: pocet1 += 1
elif r <= pref1 + pref2: pocet2 += 1
elif r <= pref1 + pref2 + pref3: pocet3 += 1
print "Strana 1:", 100.0 * pocet1 / vzorek
print "Strana 2:", 100.0 * pocet2 / vzorek
print "Strana 3:", 100.0 * pocet3 / vzorek
30 / 50
Simulace volebního průzkumu – lepší řešení
def pruzkum(vzorek, pref):
n = len(pref)
pocet = [ 0 for i in range(n) ]
for _ in range(vzorek):
r = random.randint(1,100)
for i in range(n):
if sum(pref[:i]) < r <= sum(pref[:i+1]):
pocet[i] += 1
for i in range(n):
print "Strana", i+1, 100.0 * pocet[i] / vzorek
Toto řešení má stále nedostatky (po stránce funkčnosti) –
zkuste dále vylepšit.
31 / 50
Převod do Morseovy abecedy
vstup: řetězec
výstup: zápis v Morseově abecedě
příklad: PES → .--.|.|...
32 / 50
Převod do Morseovy abecedy nevhodně
def prevod_morse(text):
vystup = ’’
for i in range(len(text)):
if text[i] == ’A’: vystup += ’.-|’
elif text[i] == ’B’: vystup += ’-...|’
elif text[i] == ’C’: vystup += ’-.-.|’
elif text[i] == ’D’: vystup += ’-..|’
# atd
return vystup
33 / 50
Převod do Morseovy abecedy: využití seznamu
morse = [’.-’, ’-...’, ’-.-.’, ’-..’ ] # atd
def prevod_morse(text):
vystup = ’’
for i in range(len(text)):
if ord(’A’) <= ord(text[i]) <= ord(’Z’):
c = ord(text[i]) - ord(’A’)
vystup += morse[c] + ’|’
return vystup
(ještě lepší řešení: využití slovníku)
34 / 50
Převod z Morseovy abecedy
def najdi_pismeno(sekvence):
for i in range(len(morse)):
if morse[i] == sekvence:
return chr(ord(’A’) + i)
return ’?’
def prevod_z_morse(zprava):
vystup = ’’
sekvence = ’’
for znak in zprava:
if znak == ’|’:
vystup += najdi_pismeno(sekvence)
sekvence = ’’
else:
sekvence += znak
return vystup 35 / 50
Pascalův trojúhelník
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Explicitní vzorec
Rekurzivní vztah
36 / 50
Pascalův trojúhelník
def pascaluv_trojuhelnik(n):
aktualni_radek = [ 1 ]
for i in range(n):
for x in aktualni_radek:
print x,
print
dalsi_radek = [ 1 ]
for i in range(len(aktualni_radek)-1):
dalsi_radek.append(aktualni_radek[i] +\
aktualni_radek[i+1])
dalsi_radek.append(1)
aktualni_radek = dalsi_radek
37 / 50
Prvočísla
dělitelné jen 1 a sebou samým
předmět zájmu matematiků od pradávna, cca od 70. let i
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ů)
38 / 50
Výpis prvočísel přímočaře
def vypis_prvocisel(kolik):
n = 1
while kolik > 0:
if len(seznam_delitelu(n)) == 2:
print n,
kolik -= 1
n += 1
39 / 50
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 6k ± 1
dělíme pouze do
√
n
40 / 50
Test prvočíselnosti: chytřejší algoritmy
náhodnostní algoritmy
polynomiální deterministický algoritmus (objeven 2002)
(vysoce) nad rámec tohoto kurzu
umí se to dělat rychle
41 / 50
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
42 / 50
Příklad aplikace: asymetrická kryptologie
http://en.wikipedia.org/wiki/Public-key_cryptography
43 / 50
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, ...
44 / 50
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
45 / 50
Eratosthenovo síto
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
31 32 33 34 35 36 37 38 39 4021 22 23 24 25 26 27 28 29 30
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
31 32 33 34 35 36 37 38 39 4021 22 23 24 25 26 27 28 29 30
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
1. krok
2. krok
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
31 32 33 34 35 36 37 38 39 4021 22 23 24 25 26 27 28 29 30
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
3. krok
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
31 32 33 34 35 36 37 38 39 4021 22 23 24 25 26 27 28 29 30
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
4. krok
46 / 50
Eratosthenovo síto
def eratosthenes(pocet):
je_kandidat = [ 1 for i in range(pocet) ]
for i in range(2, pocet):
if je_kandidat[i]:
print i,
k = 0
while k < pocet:
je_kandidat[k] = 0
k += i
47 / 50
Funkcionální prvky v Pythonu
funkcionální programování
výpočet jako vyhodnocení matematické funkce
předmět IB015, jazyk Haskell
Python obsahuje funkcionální prvky, např.
generátorová notace seznamů (list comprehension)
funkce map, reduce, filter
lambda výrazy
48 / 50
Funkcionální prvky v Pythonu – ukázka
n = 12
delitele = [ i for i in range(1, n+1) if n % i == 0 ]
print delitele
print map(str, delitele)
print map(lambda x: ’I’*x, delitele)
print filter(lambda x: x > 3, delitele)
print reduce(lambda x,y: x*y, delitele)
x = 3589
print sum(map(int,str(x))) # ciferny soucet
49 / 50
Shrnutí
seznamy, řetězce:
základní operace
ukázky použití
kryptografické příklady (historické) a souvislosti (moderní)
příště: vyhledávání, řadicí algoritmy
50 / 50