IB111 Základy programování Radek Pelánek
2018
1/59
Rozcvička: Co je jiné?
• smrk, lípa, borovice, jedle
• prase, koza, husa, ovce
Odd one out: varianta pro pokročilé
o
Odd one out: varianta pro začátečníky
prase, pes, prase, prase
Odd one out: varianta pro začátečníky
prase, pes, prase, prase
• vstup: seznam
• výstup: prvek, který je v seznamu osamocen
4 □ ►   < SI ► <
Odd one out: základní řešení
def odd_one_out(alist): for x in alist: count = 0 for y in alist: if x == y:
count += 1 if count == 1: return x return None
zpracování dotazníku, hledání cesty v bludišti, předpověď počasí, úprava obrázků
• Jaká data budu zpracovávat?
• Jaká data budu potřebovat k řešení problému?
• Jaké operace s daty budu chtít provádět?
• Jak rychle budu chtít, aby operace s daty fungovaly?
Oddělení dat a funkcionality
Důležitý princip v mnoha oblastech informatiky
Príklad web
webový portál: oddělení funkcionality, dat a vzhledu
typická realizace:
• funkcionalita - program (Python, PHP...)
• data - databáze (MySQL...)
• vzhled - grafický styl (CSS)
Ukázka nevhodného kódu
if currency == ;euro;:
value = amount * 25.72
elif currency == ;dollar;: value = amount * 21.90
elif currency == ;rupee;: value = amount * 0.34
Reálnější příklad
def print_stats():
•     • •
if success_rate < 0.5: bg_color = "red"
elif success_rate < 0.85 bg_color = "yellow"
else:
bg_color = "green"
def print_stats():
• • •
bg_color = get_color(success_rate,
[0.5, 0.85, 1],
["red", "yellow", "green"])
• • •
Další úpravy:
• parametry jako globální konstanty „vytknuté" na začátek kódu
* použití nějaké standardní „colormap" (tip: viridis)
11/59
Abstraktní datové typy
Datový typ
• rozsah hodnot, které patří do daného typu
• operace, které je možno s těmito hodnotami provádět Abstraktní datový typ (ADT)
• rozhraní
• popis operací, které chceme provádět (případně i složitost)
Konkrétní datová struktura
9 implementace
9 přesný popis uložení dat v paměti
• definice funkcí pro práci s těmito daty
Poznámky: hranice není vždy úplně ostrá, rozdíl mezi „formálním" a „praktickým" pojetím ADT; nejednotná terminologie „datový typ", „datová struktura"
Dva pohledy na data
abstraktní, „uživatelský"
o operace, která s daty budu provádět
• co musí operace splňovat, efektivita...
• množina: ulož, najdi, vymaž
• tento předmět
konkrétní, implementační
9 jak jsou data reprezentována v paměti
• jak jsou operace implementovány
• hašovací tabulka, binární vyhledávací strom
• IB002
13/59
Abstraktní pohled na data
Výhody:
• snadný vývoj
a jednodušší přemýšlení o problémech Riziko:
• svádí k ignorování efektivity
Abstraktní datové typy
Nejpoužívanější ADT:
• seznam
• zásobník
• fronta, prioritní fronta
• množina
• slovník (asociativní pole)
•<□►   4 S" ►   4 S ►   <  š ►
15/59
Datový typ seznam: různé varianty
• obsahuje posloupnost prvků
• stejného typu
• různého typu
• přidání prvku
• na začátek
• na konec
• na určené místo
• odebrání prvku
• ze začátku
• z konce
• konkrétní prvek
• test prázdnosti, délky
• případně další operace, napr. přístup pomocí indexu
16/59
Seznamy v Pythonu
opakování
• seznamy v Pythonu velmi obecné
• prvky mohou být různých typů
• přístup skrze indexy
• indexování od konce pomocí záporných čísel
• seznamy lze modifikovat na libovolné pozici
a = [;bacon;,  ;eggs;,  ;spam;, 42]
print (a[l:3]) # [}eggs}, }spam}]
print(a[-2:-4:-l])     # [}spam}, }eggs}]
a[-l] = 17 print(a) print(len(a))
17/59
eznamy v Pythonu - operace
s = [4, 1, 3] #
s.append(x) #
s.extend(t) #
s.insert(i, x) #
s.remove(x) #
s.pop(i) #
s.popO #
s.index(x) #
s.count(x) #
s.sortO #
s. reverse () #
x in s #
#
seznam
přidá prvek x na konec přidá všechny prvky t na konec přidá prvek x před prvek na pozici i odstraní první prvek rovný x odstraní (a vrátí) prvek na pozici i odstraní (a vrátí) poslední prvek vrátí index prvního prvku rovného x vrátí počet výskytů prvků rovných x seřadí seznam obrátí seznam
test, zda seznam obsahuje x (lineární průchod seznamem!)
18/59
Odd one out: řešení pomocí count
def odd_one_out(alist): for x in alist:
if alist.count(x) = return x return None
= 1
19/59
Generátorová notace pro seznamy
list comprehension specialita Pythonu
s = [x for x in range(1, 7)] print (s) # [1, 2, 3, 4, 5, 6]
s = [2 * x for x in ranged, 7)] print(s) # [2, 4, 6, 8, 10, 12]
s = [(a, b) for a in range(l, 5)
for b in ["A", "B"]] print (s) # [(1,   'A'),   (1,   >B>),  (2, 'A'),
#   (2,   'B'), ...
4 □ ►   4 ^ >■   4       >   4 S ►
20/59
Odd one out: generátorová notace
def odd_one_out(alist):
return [x for x in alist
if alist.count(x) == 1]
Pozn. Mírně odlišné chování od předchozích ukázek - vrací seznam všech osamocených.
21/59
Vnořené seznamy
• prvky seznamů mohou být opět seznamy
• použití: vícerozměrná data (např. matice)
mat = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]] print(mat [1] [2]) #6
def null_matrix(m, n):
return [[0 for col in range(n)] for row in range(m)]
Pozn. efektivnější způsob práce s maticemi: knihovna numpy
22/59
23/59
Vnořené seznamy: Násobení matic
def matrix_mult(matL, matR): rows = len(matL) cols = len(matR[0]) common = len(matR) result = null_matrix(rows, cols) for i in range(rows): for j in range(cols): for k in range(common):
result [i] [j] += matL[i] [k] * matR[k] [j] return result
24/59
Interpretace dvojitého indexování
• „data [i] [j]11
• data indexuji „dvojicí čísel" 9 intuitivní
• neodpovídá implementaci v Pythonu
• „data [i]   [j]11
• indexuji prvním číslem, dostanu seznam
• tento seznam indexuji druhým číslem
• speciální případ obecného postupu
Pozn. V Pythonu můžeme mít i data[i, j] - to však není seznam, ale slovník indexovaný dvojicí. Více později.
25/59
čteme „zleva", resp. „z vnitřku":
• mat [2] [: :-l] [0]
• sortedCmat [1]) [2]
• (mat [0] *5) [7]
Čistě ilustrativní příklady, rozhodně ne ukázky pěkného kódu.
Fronta a zásobník
fronta a zásobník - „seznamy s omezenými možnostmi
11
Proč používat něco omezeného?
27/59
fronta a zásobník - „seznamy s omezenými možnostmi"
Proč používat něco omezeného?
• vyšší efektivita implementace
• citelnější a cistejsi kod
• „sebe-kontrola"
Sebe-kontrola, historická poznámka: GOTO; xkcd.com/292/
I COULĎRKTRUCIURE THE FTO&RMS FlW		EHSCREWGOODFfiňcnCE. HOUBADCAM IT8E?		
OR IJSEľ ONE LiTTIL 'GOID1 INSTEľAD.		\    goto i^*'n_äu!)3;		
			n	
27/59
« LIFO = Last In First Out • operace
• push (vložení)
• pop (odstranění) top (náhled na horní prvek) empty (test prázdnosti)
mnohá použití
• procházení grafů
• analýza syntaxe
• vyhodnocování výrazů o rekurze
9 9
28/59
implementace pomocí seznamu
• místo push máme append
• místo top máme [-1]
def push(stack, element): stack.append(element)
def pop(stack):
return stack.pop()
def top(stack):
return stack[-1]
def empty(stack):
return stack.empty()
29/59
Príklad aplikace: postfixová notace
• infixová notace
• operátory mezi operandy
• (3 + 7) * 9
• je třeba používat závorky
• prefixová notace (polská notace)
9 operátory před operandy
• * + 3 7 9
• nepotřebujeme závorky
• postfixová notace (reverzní polská notace, RPN)
• operátory za operandy
• 37 + 9*
• nepotřebujeme závorky
využití zásobníku: převod mezi notacemi, vyhodnocení postfixová notace
Vyhodnocení postfixové notace
def eval_postfix(line): stack = []
for token in line.split():
if token == ;*;: b = pop(stack) a = pop(stack) push(stack, a * b)
elif token == ;+;: b = pop(stack) a = pop(stack) push(stack, a + b)
else:
push(stack, int(token)) return top(stack)
31/59
vstup			akce	zásobník	
7 4 7	+	* 8 +	push		
4 7 +	*	8 +	push	7	
7 + *	8	+	push	7	4
+ * 8	+		+	7	4 7
* 8 +			*	7	11
8 +			push	77	
+			+	77	8
				85	
32/59
• FIFO = First In First Out
• operace
• enqueue (vložení)
• dequeue (odstranění)
• front (náhled na přední prvek)
• empty (test prázdnosti)
• použití
• zpracovávání příchozích požadavků
• procházení grafu do šířky
• pokročilejší varianta: prioritní fronta
33/59
• implementace pomocí seznamů snadná, ale neefektivní
• přidávání a odebírání na začátku seznamu vyžaduje přesun
• pomalé pro dlouhé fronty
• použití knihovny collections
• datový typ deque (oboustranná fronta)
• vložení do fronty pomocí append
• odebrání z fronty pomocí poplef t
• přední prvek fronty je [0]
34/59
Fronta: ukázka deque
from collections import deque
q = deque([MEricM,  "John", "Michael"])
q.append("Terry")     # Terry arrives
q.append("Graham")    # Graham arrives
q.popleftO        # Eric leaves
q.popleftO        # John leaves
print(q) # deque([3 Michael3,   3Terry3,
Datový typ množina
• neuspořádaná kolekce dat bez vícenásobných prvků
• operace
• insert (vložení)
• find (vyhledání prvku, test přítomnosti)
• remove (odstranění)
• použití
• grafové algoritmy (označení navštívených vrcholů)
• rychlé vyhledávání
• výpis unikátních slov
< [f? ► < -e ► < -ž ►    š   o q, o
38/59
Množina v Pythonu
set(alist)	#	vytvoří množinu ze seznamu
len(s)	#	počet prvků množiny s
s. add(x)	#	přidání prvku do množiny
s .remove(x)	#	odebrání prvku z množiny
x in s	#	test, zda množina obsahuje x
sl <= s2	#	test, zda je sl podmnožinou s2
sl.union(s2)	#	sjednocení množin sl a s2
sl 1 s2	#	— totéž —
sl.intersection(s2)	#	průnik množin sl a s2
sl & s2	#	— totéž —
sl.difference(s2)	#	rozdíl množin sl a sl
sl - s2	#	— totéž —
sl.symmetric_diference(s2) # symetrický rozdíl množin		
sl ~ s2		# — totéž —
39/59
Množina v Pythonu
basket = ['apple', 'orange', 'apple', 'orange', 'banana fruit = set(basket)
print(fruit) # {'orange',  'apple', 'banana'}
print('orange' in fruit)    # True print('tomato' in fruit)    # False
a = set("abracadabra") b = set("engineering")
print(a) # {'a',  'r', 'b', 'c', 'd'}
print(b) # {'%',  'r', 'e', 'g', 'n'}
print(a I b)   # {'a',  'c', 'b', 'e',  'd',  'g',  'i', 'n
print(a & b)   # {'r'}
print(a - b)   # {'a',  'c', 'b', 'd'}
print(a ~ b)   # {'a',  'c', 'b', 'e',  'd',  'g',  'i', 'n
40/59
Aplikace množiny
def unique(alist):
return list(set(alist))
def odd_one_out(alist):
return set(alist)-set([x for x in alist
if alist.count(x) > 1])
41/59
Datový typ slovník
dictionary, map, asociativní pole
• neuspořádaná množina dvojic (klíč, hodnota)
• klíče jsou unikátní
• operace jako u množiny (insert, find, delete)
• přístup k hodnotě pomocí klíče (indexování pomocí [])
• klíče jsou neměnné, ale hodnoty se smí měnit 9 příklady použití
• překlad UČO na jméno, jméno na tel. číslo
• počet výskytů slov v textu
• „cache" výsledků náročných výpočtů
Slovník vs. seznam
zjednodušené srovnání:
• indexování (klíče):
• seznam: čísla
• slovník: cokoliv (neměnitelného)
• pořadí klíčů:
• seznam: fixně dáno
• slovník: neřazeno
Slovník v Pythonu
phone = {"Buffy": 5550101, "Xander": 5550168} phone["Dawn"] = 5550193 print(phone)
# {'Xander': 5550168, 'Daum': 5550193, 'Buffy': 5550101 print(phone["Xander"])
# 5550168
del phone ["Buffy"] print(phone)
# {'Xander': 5550168, print(phone.keys() )
# dict_keys(['Xander', print("Dawn" in phone)
# True
'Dawn': 5550193} 'Dawn'])
44/59
ovnřk v Pythonu
užitečné funkce pro slovníky
d.keys() # vrátí seznam klíčů
d.values() # vrátí seznam hodnot
d.items() # vrátí seznam záznamů (dvojic)
d.get(key, default)    # pokud existuje klíč key, vrátí
# jeho hodnotu, jinak vrátí
# hodnotu default d.get(key)                   # jako předtím,
# jen default je ted; None
45/59
Slovník v Pythonu
.itemsO - použití napr. pro kompletní výpis (nikoliv vyhledávání!)
for name, num in phone.items(): print (name + 11 ;s number is"
# Xander's number is 5550168
# Dawn's number is 5550193
num)
46/59
one out: řešení se slovníkem
def odd_one_out(alist): count = {} for x in alist:
count [x] = count.get(x, for x in count:
if count [x] == 1: return x return None
0)
Odd one out: řešení se slovníkem
def odd_one_out(alist): count = {} for x in alist:
count [x] = count.get(x, 0) + 1 return min(count.keys(), key=count.get)
Pozn. Odlišné chování od ostatních ukázek v případě, kdy není splněn předpoklad unikátního osamoceného prvku.
48/59
Prevod do morseovky
připomenutí: dřívější řešení přes seznamy
morse = [".-", "-.."] #e
def to_morse(text): result = 1111
for i in range(len(text)):
if ord(11A11) <= ord(text[i]) <= ord c = ord(text[i]) - ord ("A") result += morse [c] + "I" return result
Převod do morseovky
morse = {"A": "B": "C":  "-.-."} # etc.
def to_morse(text): result = 1111 for c in text:
result += morse.get(c, "?") + "I" return result
# advanced version def to_morse(text):
return(M|M.join(list(map(lambda x: morse.get(x, "?"),
text))))
50/59
def encrypt(text, subst): result = 1,11 for c in text:
if c in subst:
result += subst [c] else:
result += c return result
my.cipher = {"A":  "Q", "B":  "W", "C":  "E"} # etc.
print(encrypt("BAC", my_cipher)) # WQE
51/59
text = """It is a period of civil war. Rebel spaceships, striking [...] restore freedom to the galaxy """
output_word_freq(text)
the 7
to 4
rebel 2
plans 2
of 2
her 2
52/59
Frekvenční analýza slov
def is_word_char(char):
return char not in ; ! M#$°/0&\; ()*+,-./: ;<=>?Q[\\] ~_'{
def word_freq(text):
text = 1111.join(filter(is_word_char, text)) text = text.lower() word_list = text.split() freq = {}
for word in word_list:
freq[word] = freq.get(word, 0) + 1 return freq
< [f? ►    <        ►    <  -Ž  ►        -Š       -O °s O
53/59
def output_word_freq_simple(text): freq = word_freq(text) for word in freq:
print(word,  "\t", freq[word])
Jak udělat výpis seřazený podle četnosti a vypisovat pouze nejčetnější slova?
54/59
v
Razení výstupu: pomocný seznam dvoji
def output_word_freq(text, topN=10): freq = word_freq(text)
tmp = [(freq[word], word) for word in freq] tmp.sort(reverse=True) for count, word in tmp[:topN]: print(word,  "\t", count)
55/59
Razení výstupu: využití lambda funkce
def output_word_freq(text, topN=10): freq = word_freq(text)
words = sorted(freq, key=lambda x: -freq[x]) for word in words [:topN]:
print(word,  "\t", freq[word])
56/59
ndexování slovníku
slovník můžeme indexovat „neměnitelnými" datovými typy
v ' I
• cisla
• řetězce
• dvojice
• n-tice (neměnná forma seznamu)
57/59
data = {}
data[(l, 5)] = "white king" data[2, 6] = "black rookM
print(data.keys()) #dict_keys([(1, 5),   (2, 6)])
Můžeme vynechávat kulaté závorky u n-tice.
Pozor na rozdíl:
• data[x] [y] - seznam seznamů
• data[x, y] - slovník indexovaný dvojicí
• datové typy: abstraktní vs konkrétní
• seznam, vnořený seznam („vícerozměrné pole")
• zásobník, fronta
• množina
• slovník
59/59