Vyhledávání, řazení, složitost
IB111 Úvod do programování
2016
1 / 62
Výpočet odmocniny
vstup: číslo x
výstup: přibližná hodnota
√
x
Jak na to?
2 / 62
Výpočet odmocniny
vstup: číslo x
výstup: přibližná hodnota
√
x
Jak na to?
Mnoho metod, ukázka jedné z nich (rozhodně ne nejvíce
efektivní)
2 / 62
Výpočet odmocniny: binární půlení
horní odhadspodní odhad
0 1 20.5 1.5
0 1 20.5 1.5
0 1 20.5 1.5
0 1 20.5 1.5
0 1 20.5 1.5
střed
3 / 62
Výpočet odmocniny: binární půlení
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
4 / 62
Výpočet odmocniny – chyba
Drobný problém: Program není korektní.
Kde je chyba?
5 / 62
Výpočet odmocniny – poznámky
Funguje korektně jen pro čísla ≥ 1.
Co program udělá pro čísla < 1?
Proč?
Jak to opravit?
6 / 62
Obecný kontext
problém
⇓
algoritmus
⇓
program
⇓
ladění
7 / 62
Poznámka o ladění
laděním se nebudeme (na přednáškách) příliš zabývat
to ale neznamená, že není důležité...
Ladění je dvakrát tak náročné, jak psaní vlastního kódu. Takže
pokud napíšete program tak chytře, jak jen umíte, nebudete
schopni jej odladit. (Brian W. Kernighan)
8 / 62
Postřeh k ladění
Do průšvihu nás nikdy nedostane to, co nevíme. Dostane nás
tam to, co víme příliš jistě a ono to tak prostě není. (Y. Berry)
9 / 62
Ladění
ladící výpisy
např. v každé iteraci cyklu vypisujeme stav proměnných
doporučeno vyzkoušet na ukázkových programech ze
slidů
použití debuggeru
dostupný přímo v IDLE
sledování hodnot proměnných, spuštěných příkazů,
breakpointy, ...
více: cvičení, pozdější přednáška
10 / 62
Otrávené studny
8 studen, jedna z nich je otrávená
laboratorní rozbor
dokáže rozpoznat přítomnost jedu ve vodě
je drahý
kolik rozborů potřebujeme?
jak určit otrávenou studnu?
11 / 62
Otrávené studny II
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)
jak určit otrávenou studnu za 1 den pomocí 3 paralelních
rozborů?
12 / 62
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
13 / 62
Vyhledávání: hra
Myslím si přirozené číslo X mezi 1 a 1000.
Povolená otázka: „Je X menší než N?
Kolik otázek potřebujete na odhalení čísla?
Kolik předem formulovaných otázek potřebujete?
Mezi kolika čísly jste schopni odhalit skryté číslo na
K otázek?
14 / 62
Vyhledávání: řešení
„dynamické otázky : půlení intervalu
„předem formulované otázky : dotazy na bity v bitovém
zápisu (stejně jako u studen)
N čísel: potřebujeme log2 N otázek
K otázek: rozlišíme mezi 2K
čísly
15 / 62
Připomenutí: logaritmus
x = by
⇔ y = logb(x)
log10(1000) = 3
log2(16) = 4
log2(1024) = 10
logb(xy) = logb(x) + logb(y)
http://www.khanacademy.org/math/algebra/logarithms
http://khanovaskola.cz/logaritmy/uvod-do-logaritmu
16 / 62
Logaritmus – graf
17 / 62
Logaritmus – test
log3(81) = ?
log2(2) = ?
log5(1) = ?
log10(0.1) = ?
log2(
√
2) = ?
log0.5(4) = ?
18 / 62
Vyhledávání: motivace
vyhledávání v (připravených) datech je velmi častý problém:
web
slovník
informační systémy
dílčí krok v algoritmech
19 / 62
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)
20 / 62
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),
O(log(n))
21 / 62
Vyhledávání: půlení intervalu
binární vyhledávání
podobné jako: hra s hádáním čísel, aproximace odmocniny
podíváme se na prostřední člen ⇒ podle jeho hodnoty
pokračujeme v levém/pravém intervalu
udržujeme si „horní mez a „spodní mez
22 / 62
Binární vyhledávání – ilustrace
Wikipedia
23 / 62
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) // 2
if alist[middle] == value:
return True
elif alist[middle] > value:
upper_bound = middle - 1
else:
lower_bound = middle + 1
return False
24 / 62
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
25 / 62
Řadicí algoritmy: terminologická poznámka
anglicky „sorting algorithm
česky používáno: řadicí algoritmy nebo třídicí algoritmy
řadicí vesměs považováno za „správnější
26 / 62
Řadicí algoritmy: komentář
mnoho různých algoritmů pro stejný účel
většina programovacích jazyků má vestavěnou podporu
(funkce sort())
Proč se tím tedy zabýváme?
27 / 62
Řadicí algoritmy: komentář
Proč se tím tedy zabýváme?
1 ukázka programů se seznamy
2 ilustrace algoritmického myšlení, technik návrhu algoritmů
3 typický příklad drobné změny algoritmu s velkým
dopadem na rychlost programu
4 hezky se to vizualizuje a vysvětluje
5 tradice, patří to ke vzdělání informatika
6 občas se to může i hodit
28 / 62
Řadicí algoritmy: komentář
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ě
29 / 62
Doporučené zdroje
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í: http://www.youtube.com/watch?v=lyZQPjUT5B4
30 / 62
Ř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
31 / 62
Pokus č. 1
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?
32 / 62
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?
33 / 62
Složitost
n – délka vstupní posloupnosti
počet operací
jednoduché algoritmy O(n2
)
složitější algoritmy O(n log(n))
34 / 62
Bublinkové řazení (Bubble sort)
„probublávání vyšších hodnot nahoru
srovnávání a prohazování sousedů
po i iteracích je nejvyšších i členů na svém místě
35 / 62
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+1]:
tmp = a[j]
a[j] = a[j+1]
a[j+1] = tmp
invariant cyklu: a[n-i-1:] ve finální pozici
36 / 62
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]
37 / 62
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
38 / 62
Řazení 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)
39 / 62
Řazení výběrem: program
def select_sort(a):
for i in range(len(a)):
selected = i
for j in range(i+1, len(a)):
if a[j] < a[selected]: selected = j
tmp = a[i]
a[i] = a[selected]
a[selected] = tmp
40 / 62
Ř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ří
41 / 62
Řazení vkládáním: program
def insert_sort(a):
for i in range(1,len(a)):
current = a[i]
j = i
while j > 0 and a[j-1] > current:
a[j] = a[j-1]
j -= 1
a[j] = current
42 / 62
Význam proměnných
proměnná selected u řazení výběrem
index vybraného prvku
používáme 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 třeba řetězce
43 / 62
Quicksort
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
O(n log(n))
44 / 62
Ř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í – O(n log(n))
45 / 62
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
46 / 62
Radix 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é)
47 / 62
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
např. O(n), O(n log(n)), O(n2
)
48 / 62
Ilustrace rozdílů v složitosti
49 / 62
Složitost řadicích algoritmů
n – délka vstupní posloupnosti
počet operací
jednoduché algoritmy O(n2
)
složitější algoritmy O(n log(n))
50 / 62
Python: 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)
51 / 62
Vyhledávání a řazení v Pythonu
x in seznam – test přítomnosti x v seznamu
seznam.index(x) – pozice x v seznamu
seznam.count(x) – počet výskytů x v seznamu
seznam.sort() – seřadí položky seznamu
sorted(seznam) – 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
52 / 62
Různé způsoby řazení
s = [ "prase", "Kos", "ovoce", "Pes", "koza",
"ovce", "kokos" ]
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")))
53 / 62
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
54 / 62
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í
54 / 62
Unikátní prvky
def unique(alist):
alist = sorted(alist)
# rozdilne chovani od alist.sort() !!
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))
55 / 62
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, 0
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
56 / 62
Nejčastější prvek sofistikovaněji
def most_common(alist):
return max(alist, key=alist.count)
Stack Overflow diskuze:
http://stackoverflow.com/questions/1518522/python-most-common-element-in-a-list
57 / 62
Přesmyčky
přesmyčky = slova poskládaná ze stejných písmen
úkol: rozpoznat, zda dvě slova jsou přesmyčky
vstup: dva řetězce
výstup: True/False
příklady:
odsun, dusno → True
kostel, les → False
houslista, souhlasit → True
ovoce, ovace → False
58 / 62
Přesmyčky řešení
seřadíme písmena obou slov
přesmyčky ⇔ po seřazení identické
implementace za využití sorted přímočará
def anagram(word1, word2):
return sorted(word1) == sorted(word2)
59 / 62
Rozměňování peněz
vstup: částka X
výstup: vyplacení částky pomocí co nejméně mincí
(bankovek)
předpokládejme „klasické hodnoty peněz: 1, 2, 5, 10, 20,
50, 100, . . .
příklady:
29 → 2, 2, 5, 20
401 → 1, 200, 200
60 / 62
Rozměňování peněz
hladový algoritmus: „použij vždy nejvyšší minci, která je
menší než cílová částka
cvičení – naprogramovat
funguje pro klasické hodnoty
nefunguje pro obecný případ – najděte konkrétní příklad
zkuste vymyslet algoritmus pro obecný případ
61 / 62
Shrnutí
vyhledávání: půlení intervalu, rekurze
řadicí algoritmy:
jednoduché (kvadratické): bublinkové, výběrem,
vkládáním
složitější (n · log(n), rekurzivní): quick sort, slučování
příklady
62 / 62