IB113 Radek Pelánek
2019
Seznamy (pole) - motivace
• razení studentů podle bodů na písemce
• reprezentace herního plánu (piškvorky, šachy) o frekvence písmen v textu
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) print('C , freqC)
3/48
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 IB113)
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
Seznamy: použití v Pythonu
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 na konec
s[l:4] # indexace intervalu, s[l:4] = [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]
listO - pretypovaní na seznam
anipulace se seznamy
alist = [3, 8, 7] alist.append(10) alist.insert(1, 11) alist.remove(7)
# přidání na konec seznamu
# přidání na zadanou pozic
# odstranění dané hodnoty
Seznamy: konvence zápisu (PEP8)
• mezera se dělá: za čárkou
• mezera se nedělá: před čárkou, na „okrajích"
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))
< [S? ► < i ► < ± >   i •o^o
9/48
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)
10/48
Vestavěná podpora pro práci se seznamy
»> numbers = [4, 1, 8, 12, 3]
>» sum (numbers)
28
>» min(numbers) 1
>» max (numbers) 12
>» 8 in numbers True
11/48
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)
Vytvorení seznamu
různé způsoby vytvoření seznamu písmen abecedy: alist = list("abcdefghijklmnopqrstuvwxyz")
alist = []
for i in range(26):
alist.append(chr(ord(1 a')+i))
alist = [chr(ord(1 a')+i) for i in range(26)]
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) print('C , freqC)
14/48
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(1A1)+i), frequency [i])
imulace 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 += print ("Party 1:11, 100 * count 1 / size) print("Party 2:", 100 * count2 / size) print("Party 3:", 100 * count3 / size)
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.
< [S? ► < i ► < ± >   i •o^o
17/48
• vstup: řetězec
• výstup: zápis v Morseově abecedě
• příklad: PES —. —. I . I . . .
18/48
Prevod do Morseovy abecedy nevhodně
def to_morse(text): result = 11
for i in range(len(text)):
if text[i] == 'A': result += 1 elif text[i] == 'B': result += elif text[i] == 'C: result += elif text[i] == 'D': result += # etc
return result
Prevod do Morseovy abecedy: využití seznamu
morse = ['.-', '-..'] # etc
def to_morse(text): result = 11
for i in range(len(text)):
if ord('A') <= ord(text[i]) <= ord('Z'):
c = ord(text [i]) - ord('A')
result += morse [c] + 1 I1 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 1?1
def from_morse(message): result = 11 sequence = 11 for symbol in message: if symbol == 1|1:
result += find_letter sequence = 11 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)
['a',  'e',  'i',  'o',  'u', 'y']
»> message = 11. -. . I---| -. . | .
»> message. split (11111)
r i _ i     i___i     i _     i     i   _ 11
L     •      •  •      y 9 •   •      J -I
Príklad - načítaní vstupu od uživatele
»> input_string = input () 3 7
»> xstring, ystring = input_string.split( »> x = int(xstring) »> y = int (ystring)
Výškový prof i
475 m n.m.
Stoupání: 367 m
Klesaní: 363 m
mapy.cz
24/48
heights_profile( [3, 4, 5, 3, 4, 3, 2, 4, 5, 6, 5])
###### #### ########### ###########
Ascent 7 Descent 5
#
# #
#
#
# # # # # # #
25/48
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()
26/48
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)
27/48
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
28/48
zualizace 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
vhodné např. pokud je nejasný některý z příkladů ve
Zdvojnásobení seznamu
Příklad: vstupem seznam čísel (např. [4, 1, 6]), chceme „získat dvojnásobky" (tj. 8, 2, 12)
Důležité ujasnit, co přesně chceme:
• vypsat dvojnásobky
• vrátit nový seznam, který obsahuje dvojnásobky
• změnit seznam, aby obsahoval dvojnásobky
Jak vypadají jednotlivé programy?
30/48
• 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
31/48
Pascalův trojúhelník
4   6   4 1 10 10 5 1
0
0 G) © (?) (?) 0 (?) (?) (?)
Explicitní vzorec n!
(n-fe)!fc!
Rekurzivní vztah n—1
© = r?)+(V)
32/48
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]
34/48
a 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
35/48
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=" 11) how_many -= 1 n += 1 print()
36/48
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
37/48
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
38/48
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
39/48
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
•<□►  4 ^ t  < -ž ►  < -š ►
40/48
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, ...
41 /48
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
42/48
43/48
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.
44/48
Zajímavosti
• 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
45/48
Kontrolní otázky
• Je u datové struktury seznam důležité pořadí prvků?
• Může v Pythonu seznam obsahovat položky různého typu?
• Jakým příkazem přidáme do seznamu nový prvek?
• Jak zjistíme délku seznamu?
• Proč není dobrý nápad dát proměnné obsahující seznam jméno list?
• Řetězec je v mnoha ohledech podobný jako „seznam znaku . V cem se lisí (
• Jak vytvořit seznam obsahující čísla od 1 do 5? (uveďte několik různých způsobů)
• Jak zjistíme poslední prvek seznamu? Zkuste najít 3 různé způsoby.
46/48
https://www.umimeprogramovat.cz/rozhodovacka https://www.umimeprogramovat.cz/porozumeni https://www.umimeprogramovat.cz/vystup-programu
^> sada „Seznamy"
47/48
• datová struktura seznam
• základní operace se seznamy
• příklady
příště: algoritmy se seznamy - vyhledávání, řazení
48/48