Vyhledávání, řazení, složitost
IB111 Úvod do programování skrze Python
2013
1 / 47
Otrávené studny
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ý)
kolik rozborů (času) potřebujeme?
jak určit otrávenou studnu?
2 / 47
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
3 / 47
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?
4 / 47
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
5 / 47
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
6 / 47
Logaritmus – graf
7 / 47
Logaritmus – test
log3(81) = ?
log2(2) = ?
log5(1) = ?
log10(0.1) = ?
log2(
√
2) = ?
log0.5(4) = ?
8 / 47
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
9 / 47
Vyhledávání: konkrétní problém
vstup: seřazená posloupnost čísel + dotaz (číslo)
např. 2, 3, 7, 8, 9, 14 + dotaz 8
výstup: index hledaného čísla v posloupnosti (případně -1
pokud tam není)
výsledek příkladu: 3 (číslování od nuly)
10 / 47
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))
11 / 47
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
12 / 47
Vyhledávání: program
def binarni_vyhledavani(hodnota, seznam):
spodni_mez = 0
horni_mez = len(seznam) - 1
while spodni_mez <= horni_mez:
stred = (spodni_mez + horni_mez) / 2
if seznam[stred] == hodnota:
return True
elif seznam[stred] > hodnota:
horni_mez = stred - 1
else:
spodni_mez = stred + 1
return False
13 / 47
Vyhledávání: rekurzivní varianta
def binarni_vyhledavani(hodnota, seznam,
spodni_mez, horni_mez):
if spodni_mez > horni_mez:
return False
stred = (spodni_mez + horni_mez)/2
if seznam[stred] < hodnota:
return binarni_vyhledavani(hodnota, seznam,
stred+1, horni_mez)
elif seznam[stred] > hodnota:
return binarni_vyhledavani(hodnota, seznam,
podni_mez, stred-1)
else:
return True
14 / 47
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
15 / 47
Ř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ší
16 / 47
Ř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?
17 / 47
Ř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
18 / 47
Doporučený zdroj
http://www.sorting-algorithms.com/
animace
kódy
vizualizace
Více podobných: Google → sorting algorithms
A na zpestření: http://www.youtube.com/watch?v=lyZQPjUT5B4
19 / 47
Ř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
20 / 47
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?
21 / 47
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?
22 / 47
Složitost
n – délka vstupní posloupnosti
počet operací
jednoduché algoritmy O(n2
), „kvadratická
složitější algoritmy O(n log(n))
Zde: základní myšlenka algoritmů a složitost intuitivně,
důkladněji v IB002.
23 / 47
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ě
24 / 47
Bublinkové řazení: program
def bublinkove_razeni(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
25 / 47
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]
26 / 47
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
27 / 47
Ř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)
28 / 47
Řazení výběrem: program
def razeni_vyberem(a):
for i in range(len(a)):
vybrany = i
for j in range(i+1, len(a)):
if a[j] < a[vybrany]: vybrany = j
tmp = a[i]
a[i] = a[vybrany]
a[vybrany] = tmp
29 / 47
Ř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ří
30 / 47
Řazení vkládáním: program
def razeni_vkladanim(a):
for i in range(1,len(a)):
aktualni = a[i]
j = i
while j > 0 and a[j-1] > aktualni:
a[j] = a[j-1]
j -= 1
a[j] = aktualni
31 / 47
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)
32 / 47
Quick sort ilustrace dělení
33 / 47
Quick sort
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))
34 / 47
Ř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))
35 / 47
Radix sort
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)
36 / 47
Radix sort
aplikovatelné na (krátká) čí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é)
37 / 47
Radix sort ilustrace
38 / 47
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
)
39 / 47
Ilustrace rozdílů v složitosti
40 / 47
Složitost řadicích algoritmů
n – délka vstupní posloupnosti
počet operací
„jednoduché algoritmy O(n2
), „kvadratická
„složitější algoritmy O(n log(n))
41 / 47
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)
42 / 47
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
43 / 47
Přesmyčky řešení
seřadíme písmena obou slov
přesmyčky ⇔ po seřazení identické
implementace: převedení řetězce na seznam, pak seřazení
def presmycky(slovo1, slovo2):
return sorted(list(slovo1)) == sorted(list(slovo2))
44 / 47
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
45 / 47
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
46 / 47
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
47 / 47