IB111 Základy programování Radek Pelánek
2018
Otrávené studny
• 8 studen, jedna z nich je otrávená
• laboratorní rozbor
• dokáže rozpoznat přítomnost jedu
• je drahý
• kolik rozborů potřebujeme?
• jak určit otrávenou studnu?
• 8 studen, jedna z nich je otrávená
• laboratorní rozbor
• dokáže rozpoznat přítomnost jedu ve vodě
• je drahý
• je časově náročný (1 den)
o jak určit otrávenou studnu za 1 den pomocí 3 paralelních rozborů?
Otrávené studny: řešení
Řešení s využitím binárních čísel
studna	kód			studna	kód
A	000			E	100
B	001			F	101
C	010			G	110
D	011			H	111
test	přidělené studny				
1	B,	D,	F,	H	
2	c,	D,	G,	H	
3	E,	F,	G,	H	
4 □ ►   < [S ►
Vyhledávání: hra
• Myslím si přirozené číslo X mezi 1 a 1000.
• Povolená otázka: „Je X menší než A/?"
• Kolik otázek potřebujete na odhalení čísla?
4 □ ►   < S
Vyhledávání: hra
• Myslím si přirozené číslo X mezi 1 a 1000.
• Povolená otázka: „Je X menší než A/?"
• Kolik otázek potřebujete na odhalení čísla?
• Mezi kolika čísly jste schopni odhalit skryté číslo K otázek?
Výhled
v v
avani: reseni
• půlení intervalu
• K otázek: rozlišíme mezi 2K čísly
• N čísel: potřebujeme log2 N otázek
6/58
řipomenutí: logaritmus
log10(1000) =3 log2(16) = 4 log2(1024)   = 10
http://www.khanacademy.org/math/algebra/logarithms https://www.umimematiku.cz/pocitani-logaritmy-3-uroven
Logaritmus - graf
4 3 2 1 0 -1 -2 ■3
y				
				2/=log2(
				
				
	1 i	X i	5 \	3 1
				
				
				
\
Vyhledávání: motivace
vyhledávání v (připravených) datech je velmi častý problém
• web
• slovník
9 informační systémy
• dílčí krok v algoritmech
10/58
Vyhledávání: konkrétní problém
• vstup: seřazená posloupnost čísel + dotaz (číslo)
• výstup: pravdivostní hodnota (True/False)
příp. index hledaného čísla v posloupnosti (-1 pokud tam není)
příklad:
• vstup: 2, 3, 7, 8, 9, 14 + dotaz 8
• výstup: True, resp. 3 (číslování od nuly)
Vyhledávání a logaritmus
• naivní metoda = průchod seznamu
• lineární vyhledávání, O(n)
• pomalé (viz např. databáze s milióny záznamů)
• jen velmi krátké seznamy
• základní rozumná metoda = půlení intervalu
• logaritmický počet kroků (vzhledem k délce seznamu), 0(log(n))
Vyhledávání: půlení intervalu
o binární vyhledávání
• podobné jako: hra s hádáním čísel, aproximace odmocniny
• podíváme se na prostrední člen ^> podle jeho hodnoty pokračujeme v levém/pravém intervalu
• udržujeme si „horní mez" a „spodní mez"
1, 3, 7, 12, 13, 18, 24, 35, 37, 39, 42, 53, 87, 88, 91, 98
13/58
Binární vyhledávání - ilustrace
I
		i—4 < 6 r i								
1	3		4	6	7		8	10	13	14
Wikipedia
14/58
1
Vyhledávání: program
def binary_search(value, alist): lower_bound = 0 upper_bound = len(alist) - 1 while lower_bound <= upper_bound:
middle = (lower_bound + upper_bound) if alist[middle] == value:
return True elif alist[middle] > value:
upper_bound = middle - 1 else:
lower_bound = middle + 1 return False
// 2
15/58
Pripomenutí: výpočet odmocniny
def square_root(x, precision=0.01): upper = x lower = 0
middle = (upper + lower) / 2 while abs(middle**2 - x) > precision if middle**2 > x:
upper = middle if middle**2 < x:
lower = middle middle = (upper + lower) / 2 return middle
16/58
Vyhledávání, přidávání, ubírání
• seřazený seznam - rychlé vyhledávání, ale pomalé přidávání prvků
• rychlé vyhledávání, přidávání i ubírání prvků - datová struktura slovník; vyhledávací stromy, hašovací tabulky
• více později / v IB002
(a) (b)
T. H. Cormen, C. E. Leiserson, R. L. Rívest, C. Stein: Introduction to Algorithms.
Řadicí algoritmy: terminologická poznámka
• anglicky „sorting algorithm"
o česky používáno: řadicí algoritmy nebo třídicí algoritmy
• řadicí vesměs považováno za „správnější"
18/58
Řadicí algoritmy: komentár
• mnoho různých algoritmů pro stejný účel
• většina programovacích jazyků má vestavěnou podporu (funkce sortO)
Proč se tím tedy zabýváme?
< □ ►  < [f? ►  < -E ►  < -ž ►     -š     -O Q, O
19/58
Řadicí algoritmy: komentá
Proč se tím tedy zabýváme? O procvičení práce se seznamy
O ilustrace algoritmického myšlení, technik návrhu algoritmů
O typický příklad drobné změny algoritmu s velkým dopadem na rychlost programu
O hezky se to vizualizuje a vysvětluje
O tradice, patří to ke vzdělání informatika
O občas se to může i hodit
20/58
Řadicí algoritmy: komentár
• zde důraz na jednoduché algoritmy, základní použití seznamů, intuici
• detailněji v IB002 Algoritmy a datové struktury I
• pokročilejší algoritmy
• důkazy korektnosti
• složitost formálně
21/58
Doporučené zdroje
9
http://www.sorting-algorithms.com/
• animace
• kódy
• vizualizace
http://sorting.at/
• elegantní animace
více podobných: Google —sorting algorithms a na zpestření:
• xkcd Ineffective Sorts: https://xkcd.com/1185/
• Bubble-sort with Hungarian folk dance:
http://www.youtube.com/watch?v=lyZQPjUT5B4
22/58
v
Řadicí algoritmy: problém
• vstup: posloupnost (přirozených) čísel např. 8, 2, 14, 3, 7, 9
• výstup: seřazená posloupnost např. 2, 3, 7, 8, 9, 14
pozn. většina zmíněných algoritmů aplikovatená nejen na čísla, ale na „cokoliv, co umíme porovnávat"
23/58
• zkoušíme systematicky všechna možná uspořádání prvků
• pro každé z nich ověříme, zda jsou prvky korektně uspořádány
• je to dobrý algoritmus?
24/58
Co vy na to?
• zkuste vymyslet
• řadicí algoritmus
• co nejvíce různých principů
• co nejefektivnější algoritmus
• možná inspirace: jak řadíte karty?
25/58
n - délka vstupní posloupnosti
počet operací	
jednoduché algoritmy	0(n2)
složitější algoritmy	0{n\og{n))
< □ ►  < [f? ►  < -E ►  < -ž ►     -š     O Q, O
26/58
Bublinkové řazení (Bubble sort)
• „probublávání" vyšších hodnot nahoru 9 srovnávání a prohazování sousedů
• po / iteracích je nejvyšších / členů na svém místě
Bublinkové řazení: program
def bubble_sort(a): n = len(a) for i in range(n):
for j in range(n-i-1): if a [j] > a[j+l] :
invariant cyklu: a[n-i-l:] ve finální pozici
tmp = a [j] a [j] = a[j+l] a[j+l] = tmp
28/58
Bublinkové řazení: příklad běhu
[8,	2,	7,	14,	3,	1]
[2,	7,	8,	3,	1,	14]
[2,	7,	3,	1,	8,	14]
[2,	3,	1,	7,	8,	14]
[2,	1,	3,	7,	8,	14]
[1,	2,	3,	7,	8,	14]
Implementační detail: prohazování prvků
• prohození hodnot dvou proměnných a, b
• na slidech psáno „běžným" způsobem pomocí pomocné proměnné: t = a; a = b; b = t
• Python umožňuje zápis: a, b = b, a
30/58
zení výběrem (Select sort)
• řazení výběrem
• projdeme dosud neseřazenou část seznamu a vybereme nejmenší prvek
• nejmenší prvek zařadíme na aktuální pozici (výměnou)
v
Razení výběrem: program
def select_sort(a):
for i in range(len(a)): selected = i
for j in range(i+l, len(a)): if a[j] < a[selected] : selected = j tmp = a[i] a[i] = a [selected] a [selected] = tmp
32/58
Řazení vkládáním (Insert sort)
• podobně jako „řazení karet"
• prefix seznamu udržujeme seřazený
• každou další hodnotu zařadíme tam, kam patří
33/58
Razení vkládáním: program
def insert_sort(a):
for i in range(1,len(a)): current = a[i]
while j > 0 and a[j-l] > current:
a[j] = a[j-l]
j -= 1 a[j] = current
4 ^ >■   4 ± k   4  S ►
34/58
Význam proměnných
• proměnná selected u řazení výběrem
• index vybraného prvku
• používame k indexování: a [selected]
• proměnná current u řazení vkládáním
• hodnota „posunovaného" prvky
• a[j] = current
• v našich případech mají stejný typ (int), ale jiný význam a použití (záměna = častý zdroj chyb)
• zřejmější pokud řadíme řetězce
35/58
• rekurzivní algoritmus
• vybereme „pivota" a seznam rozdělíme na dvě části:
• větší než pivot
• menší než pivot
• obě části pak nezávisle seřadíme (rekurzivně pomocí quicksortu)
• pokud máme smůlu při výběru pivota, tak je stejně pomalý jako předchozí
• v průměrném případě je rychlý - quick 0(nlog(n))
36/58
Řazení slučováním (Merge sort)
• rekurzivní algoritmus
• seznam rozdělíme na dvě poloviny a ty seřadíme (pomocí Merge sort)
• ze seřazených polovin vyrobíme jeden seřazený seznam -„zipování"
• vždy efektivní - 0(nlog(n))
37/58
Specifické předpoklady - efektivnější algoritmus
• předchozí algoritmy využívají pouze operaci porovnání dvou hodnot
• aplikovatelné na cokoliv, co lze porovnávat, žádné další předpoklady
• s doplňujícími předpoklady můžeme dostat nové algoritmy (obecný princip)
• řazení (krátkých) čísel —Radix sort
ix sort
• seznam („krátkých") čísla
• postupujeme od nejméně významné cifry k nejvýznamnější
• seřadíme čísla podle dané cifry = rozdělení do 10 „kyblíčků" (jednoduché, rychlé)
329	720	720	329
45 7	355	329	355
657	436	436	436
839 -	....;i„. 457 ■•	...■in-  839 ■■	...;)„.. 457
436	657	355	657
720	329	457	720
355	839	657	839
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms.
39/58
Složitost trochu podrobněji
• složitost algoritmu - jak je algoritmus výpočetně náročný
• časová, prostorová
• měříme počet operací, nikoliv čas na konkrétním stroji
• vyjadřujeme jako funkci délky vstupu
• O notace - zanedbáváme konstanty
• na
pí. O(n), 0(n\og(n)), 0(n2)
40/58
Ilustrace rozdílů v složitosti
n	logn	n	nlogn			2n
8	3 nsec	0.01 /*	0.02 íx	0.06 //	0.51 fi	0.26 fi
16	4 nsec	0.02 fi	0.06 fi	0.26 fi	4.10 fi	65.5 fi
32	5 nsec	0.03 jti	0.16 /i	1.02 /x	32.7 ft	4.29 sec
64	6 nsec	0.06 fi	0.38 ju	4.10/x	262 fi	5.85 cent
128	0.01 fi	0.13 /i	0.90 fi	16.38 fi	0.01 sec	1020 cent
256	0.01 fi	0.26 pt	2.05 /x	65.54 ^	0.02 sec	1058 cent
512	0.01 n	0.51 fi	4.61 fi	262.14 ^	0.13 sec	10135 cent
2048	0.01 fi	2.05 m	22.53 /*	0.01 sec	1.07 sec	10598 cent
4096	0.01 /x	4.10 fi	49.15 /z	0.02 sec	8.40 sec	101214 cent
8192	0.01 \i	8.19 m	106.50 m	0.07 sec	1.15 min	102447 cent
16384	0.01 fi	16.38 p	229.38 /x	0.27 sec	1.22 hrs	104913 cent
32768	0.02 fi	32.77 fi	491.52 fj.	1.07 sec	9.77 hrs	109845 cent
65536	0.02 /x	65.54 /x	1048.6 /x	0.07 min	3.3 days	1019709 cent
131072	0.02 p	131.07p	2228.2 íx	0.29 min	26 days	103943S cent
262144	0.02 it	262,14 fi	4718.6 fi	1.15 min	7 mnths	1078894 cent
524288	0.02 fi	524,29 /x	9961.5 //	4.58 min	4.6 years	10157808 cent
1048576	0.02 fi	1048.60 fi	20972 fi	18.3 min	37 years	10315634 cent
Table 1.1   Running times for different sizes of input,  "nsec'1 stands for nanoseconds, ufi" is one microsecond and "cent" stands for centuries.
M. H, Alsuwaiyel: Algorithms, Design Techniques and Analysis.
Složitost řadicích algoritmů
n - délka vstupní posloupnosti
počet operací
jednoduché algoritmy složitější algoritmy
0{n2) 0(nlog(n))
4 ^ >■   <       >   4 S ►
42/58
43/58
Kahoot: Program A
def magic(alist, x): c = 0
for v in alist: if v > x: c += 1
return c
print(magic([8, 2, 7, 4, 6, 10], 5))
44/58
a = [3, 7, 53 1, 8]
for i in range(len(a)-l): if a[i] > a[i+l] : a[i+l] = a[i] a[i] = a[i+l]
print(a)
2 ^)C\(V
45/58
Pvthon: Seznam funkcí
Pro zajímavost: v Pythonu můžeme mít třeba i seznam funkcí
def test_sorts():
for sort in [bubble_sort, insert_sort, select_sort]: a = [41, 71, 46, 15, 97, 44, 30, 11] sort(a) print(a)
46/58
Vyhledávání a razení v Pythonu
• x in alist - test prítomnosti x v seznamu
• alist. index (x) - pozice x v seznamu
• alist. count (x) - počet výskytů x v seznamu
• alist.sort() - seřadí položky seznamu
• sorted(alist) - vrátí seřazené položky seznamu (ale nezmění vlastní proměnnou)
pro řazení používá Python Timsort - kombinaci řazení slučováním a vkládáním
47/58
Různé způsoby razení
s = ["prase", "Kos", "ovoce", "Pes", "koza",
"kokos"]
"ovce"
print(sorted(s)) print(sorted(s, reverse=True)) print(sorted(s, key=str.lower)) print(sorted(s, key=len))
print(sorted(s, key=lambda x: x.count("o")))
48/58
proxy values
		T aa	aa'		rbbT
len y			\   \ \		
3		4		1	2
Sort the original list using the proxy values
TbbT TcccT TaaaaT
https://developers.google.com/edu/python/sorting
49/58
Razení v Pythonu: poznámky
ukázky sorted:
• reverse, key - pojmenované argumenty o parametrem funkce (key) je funkce
• vestavěná funkce: len, str. lower
• vlastní funkce: count_letter_o, get_third_letter
• „anonymní" lambda funkce: lambda x: x. count ("o")
praktické použití:
• příklad: seřazení jmen studentů podle bodů na písemce
• využití dalších datových struktur, ukázky později
50/58
Unikátní prvky, nejčastější prvek
• máme seznam prvků, např. výsledky dotazníku (oblíbený programovací jazyk):
["Python", "Java", "C", "Python", "PHP", "Python", "Java", "JavaScript", "C", "Pascal"]
• chceme:
• seznam unikátních hodnot
• nejčastější prvek
51/58
Unikátní prvky, nejčastější prvek
• máme seznam prvků, např. výsledky dotazníku (oblíbený programovací jazyk):
["Python", "Java", "C", "Python", "PHP", "Python", "Java", "JavaScript", "C", "Pascal"]
• chceme:
• seznam unikátních hodnot
• nejčastější prvek
• přímočaře: opakované procházení seznamu
• efektivněji: seřadit a pak jednou projít
• elegantněji: využití pokročilých datových struktur / konstrukcí
51/58
Unikátní prvky
def unique(alist):
alist = sorted(alist)
# rozdilne chovani od alist.sort() 11
result = []
for i in range(len(alist)):
if i == 0 or alist[i-1]   != alist[i] result.append(alist [i]) return result
def unique(alist):
return list(set(alist))
52/58
Nejčastější prvek přímočaře
def most_common(alist): alist = sorted(alist) max_value, max_count = None, 0 current_value, current_count = None, for value in alist:
if value == current_value:
current_count += 1 else:
current_value = value current_count = 1 if current_count > max_count: max_value = current_value max_count = current_count return max_value
< □ ► < si ►
častější prvek sofisti kovanej
def most_common(alist):
return max(alist, key=alist.count)
Stack Overflow diskuze:
http: //stackoverf low. com/questions/1518522/python-most-common-element-in-a-list
54/58
• přesmyčky = slova poskládaná ze stejných písmen
• úkol: rozpoznat, zda dvě slova jsou přesmyčky
• vstup: dva řetězce
o příklady:
• odsun, dusno —> True
• kostel, les Falše
• houslista, souhlasit True
• ovoce, ovace Falše
• seřadíme písmena obou slov
• přesmyčky <^> po seřazení identické
• implementace za využití sorted přímočará
def anagram(wordl, word2):
return sorted(wordl) == sorted(word2)
56/58
řazení:
• velmi častý dílčí krok při programování
• i když to na první pohled nemusí být vidět
• vhodné uspořádání výstupů programu
•   a koření v supermarketu! a taky se hodí, když jste krab: https : //www.youtube. com/watch?v=f ldnocPQXDQ
57/58
• vyhledávání: půlení intervalu
• řadicí algoritmy:
o jednoduché (kvadratické): bublinkové, výběrem, vkládáním
• složitější (r? • log(r?), rekurzivní): quick sort, slučování
• praktické použití řazení
• příklady