IB113 Radek Pelánek
2021
Rozcvička I
a = [3, 1, 7] print(sorted(a)) print(a) b = [4, 3, 1] print(b.sort()) print(b)
2/71
Rozcvička
a = ["magic"] a.append(a)
print (a [1] [1] [1] [1] [1] [0] [1] [0] [0] [0])
„záludnější partie"
• globální a lokální proměnné
• reprezentace dat v paměti, kopírování
• předávání parametrů funkcím
• typy
• rekurze
základní témata obecně důležitá detaily specifické pro Python
Dnešní programy
Varování: Dnešní ukázky programů jsou často ,,
• minimalistické ukázky důležitých jevů
• nikoliv pěkný, prakticky používaný kód
Python Tutor - vizualizace
Vizualizace použité ve slidech: http://www.pythontutor.com
Odkazy na dnešní ukázky:
https://www.fi.muni.cz/~xpelanek/IB113/tutor-codes.html
Doporučeno projít si interaktivně.
6/71
Názvy proměnných - konvence
• konstanty - velkými písmeny
• běžné proměnné:
• smysluplná slova
• víceslovné názvy: lower_case_with_undersc
• krátké (jednopísmenné) názvy:
• indexy
• souřadnice: x, y
• pomocné proměnné s velmi lokálním využitím
Globální a lokální proměnné
Globální proměnné
• definovány globálně (tj. ne uvnitř fun
• jsou viditelné kdekoli v programu
Lokální proměnné
• definovány uvnitř funkce
• jsou viditelné jen ve své funkci
Rozsah proměnných obecněji
9 proměnné jsou viditelné v rámci svého „rozsah • rozsahem mohou být:
• funkce
• moduly (soubory se zdrojovým kódem)
• třídy (o těch se dozvíme později)
• a jiné (závisí na konkrétním jazyce)
relevantní terminologie: „namespace", „scope"
Globální a lokální proměnné
a = "This is global."
def examplel():
b = "This is local." print(a) print(b)
examplel()     # This is global.
# This is local. print(a) # This is global.
print(b) # ERROR!
# NameError: name 'b' is not defined
Globální a lokální proměnné
Python 3.6
1 a = "This is global."
2
def examplel():
b = "This is local pri nt(a) print(b)
3
4 Í
6
7
examplel ()
3
print(a) 11 print(b)
# This is global
# This i s local.
# This is global
# ERROR!
Edit code I Live programming
Print output (drag lower right corner to resize)
This is global
Fra rnes
Global frame
examplel
This is global."
examplel
b   "This is local
Objects
function examplel()
1
Globální a lokální proměnné
vytváříme novou lokální proměnnou, neměníme tu globální
a = "Think global."
def example2():
a = "Act local." print(a)
print(a) # Think global.
example2()     # Act local. print(a) # Think global.
12/71
Globální a lokální proměnné
Python 3.6
a = "Think global."
2
3 def example? ():
a = "Act local." print(a)
6
print(a)        # Think global. example2()     # Act local, print(a)        # Think global.
Edit code | Live programming
st executed jcute
> set a breakpoint; use the Back and Forward buttons to jump there.
Print output (drag lower right corner to resize)
Think global.
Frames
Global frame
example2
example2
Think global
Objects
function example2()
a   "Act local.
13/71
Globální a lokální proměnné
Jak měnit globální proměnné?
a = "Think global."
def example3(): global a a = "Act local." print(a)
print(a) # Think global
example3() # Act local. print(a) # Act local.
Lokální proměnné: deklarace
lokální proměnná vzniká, pokud je přirazení kdekoli uvnitř f u n kce
a = "Think global, def example4(change_opinion=False): print(a)
if change_opinion: a = "Act local." print("Changed opinion:", a)
print(a) # Think global.
example4()       # ERROR!
# UnboundLocalError: local variable 'a' reference
# assignment < □ ► <e ► < z= ► < i ► i
Globální a lokální proměnné: příklad
a = 5
def testi(): print(a)
def test2(): print(a) a = 8
testi()    # 5
test2()   # UnboundLocalError
□ ► <
Rozsah proměnných: for cyklus
• rozsah proměnné v Pythonu není pro „dílčí blok kódu ale pro celou funkci (resp. globální kód)
• častá chyba (záludný preklep): proměnná for cyklu použita po ukončení cyklu
n = 9
for i in range(n):
print(i) if i °/0 2 == 0:
print("I like even length lists")
Globální a lokální proměnné
Doporučení:
• vyhýbat se globálním proměnným
• pouze ve specifických případech, např. globální konstanty
Proč?
o horší čitelnost kódu
• náročnější testování
• zdroj chyb
obecně: „lokalita kódu" je užitečná
18/71
Globální proměnné: alternativy
• předávání parametrů funkcím a vracení hodnot z funkcí
• objekty (probereme stručně později)
• a další (nad rámec předmětu): statické proměnné (C, C++, Java, ...), návrhový vzor Singleton, ...
příklad: herní plán
Připomenutí z dřívější přednášky
vstupy (parametry)
return
návratová hodnota
vedlejší efekty
výpisy
změny globálních proměnných
20/71
Čisté funkce jsou vaši přátelé!
• ladění
• modularita
• přemýšlení o problému
• čitelnost kódu
21/71
Funkce: vedlejší efekty
• změna měnitelných parametrů
• OK, ale nemíchat s návratovou hodnotou, vhodně pojmenovat, dokumentovat
• změna globálních proměnných (které nejsou parametry)
• většinou cesta do pekla
• změna stavu systému (libovolné „výpisy", zápis do souboru, databáze, odeslání na tiskárnu, ...)
• nutnost, ale nemíchat chaoticky s výpočty
22/71
Proměnné a paměť
Proměnné v různých jazycích
• pojmenované místo v paměti
• odkaz na místo v paměti (Python)
• kombinace obou možností
PVv r nrazeni
• proměnné ve stylu C: změna obsahu paměti
• proměnné ve stylu Pythonu: změna odkazu na jiné místo v paměti
23/71
Proměnné a paměť
int a} b; a - i;
a = 2;
b = a;
Jazyk C Proměnné jako hodnoty
a = 1
a = 2;
b = a;
Jazyk Python Proměnné jako odkazy
24/71
Proměnné a paměť
funkce id() - vrací „identitu" objektu (± adresa v paměti)
a = 1000 b = a
a = [1] b = a
print(a, b)
print(id(a), id(b))
b += 1
print(a, b)
print(id(a), id(b))
print(a, b)
print(id(a), id(b))
b.append(2)
print(a, b)
print(id(a), id(b))
25/71
Rovnost vs. „stejná identita"
a = [1, 2, 3] b = [1, 2, 3]
print(a == b) # Tru
print(idCa) == id(b))     # Fal
operátor is - stejná identita
Predávaní parametru v Pythonu
• paramater drží odkaz na predanou proměnnou
• změna parametru změní i predanou proměnnou
• neměnitelné typy (čísla, řetězce, ntice)
• nelze „změnit", každé prirazení znamená vytvoření odkazu na něco nového
9 neprojeví se mimo funkci
• měnitelné typy (seznam, slovník)
9 lze měnit, změna typu append, x [3] =8 se projeví i mimo funkci
• pozor: přiřazení znamená změnu odkazu, neprojeví se mimo funkci
Predávaní parametru: ukázky
číselný parametr je neměnitelný, toto nic neprovede
def update_param_int(x): x = x + 1
a = 1
print(a)    # 1 update_param_int(a) print(a)    # 1
Predávaní parametru: ukázky
seznam je měnitelný, změna se projeví i mimo funkci
def update_param_list(x): x append(3)
a = [1, 2] print (a)    # [1, 2] update_param_list(a) print (a)    # [1, 2, 3]
29/71
Predávaní parametru: ukázky
odkaz se změní na nový seznam, původní je nezměněn změna se neprojeví mimo funkci
def change_param_list(x) x = [1, 2, 3]
a = [1, 2] print (a)    # [1, 2] change_param_list(a) print (a)    # [1, 2]
Š      -f) C^O
30/71
Predávaní parametru: kvíz
def test(s):
s.append(3) s = [42, 17] s.append(9) print(s)
t = [1, 2] test(t) print(t)
Předávání parametrů: vizualizace
Python 3.6
Print output (drag lower right corner to resize)
def testis):
s.append(3) s = [42, 17] s.append(9)
p r i n t (s)
2
3
4
5
6
t = [1. 2]
testttj 9 print(t)
Edit code I Live programming
ted
;akpoint; use the Back and Forward buttons to jump there.
Frames
Global frame test t
Objects
function test(s)
•---.—^	list		
	0	1	2
	1	2	3
			
0	l	2
42	17	9
32/71
Kopírování objektů
Vytvoření aliasu b = a
• odkaz na stejnou věc
Mělká kopie b = a[:] nebo b = list (a)
• vytváříme nový seznam, ale prvky tohoto seznamu jsou aliasy
• obecně i pro jiné typy než seznamy (knihovna copy)
• b = copy.copy(a)
Hluboká kopie
• kompletní kopie všech dat
• obecné řešení (opět knihovna copy)
• b = copy.deepcopy(a)
Kopírování objektů
mělká kopie
[3, 5] [2,9]
[1,7]
listB
hluboká kopie
[3, 5] [2,9] [1,7]
[3, 5] [2, 9] [1,7]
34/71
import copy
a = [[3, 5] ,  [2, 9] ,  [1, 7]] b = a c = a[:]
d = copy.deepcopy(a) a[0] [0] = 100
print(b[0] [0] , c[0][0], d[0] [0])
a[0] = [200, 200]
print (b [0] [0] , c [0] [0] , d [0] [0])
35/71
Datové typy
Datové typy určují:
• význam dat
• operace, které lze s daty provádět
• hodnoty kterých mohou data nabývat
• bool
9 int, float, complex - číselné typy
• str - řetězec
• list - seznam
• tuple - n-tice
• diet - slovník
• set - množina
(vyber nejdulezitejsichj
37/71
print(type(3)) print(type(3.0)) print(type(3==0)) print(type("3")) print(type([3])) print(type((3,0))) print(type({3:0})) print(type({3}))
Typy: kvíz
type(3) type(3.0) type(3==0) type("3") type ([3]) type((3,0)) type({3:0}) type({3})
# <class ' int '>
# <class 'float '>
# <class 'bool '>
# <class 'str'>
# <class 'list '>
# <class 'tuple '>
# <class 'diet '>
# <class 'set '>
39/71
• neměnitelné (immutable):
bool, int, float, str, tuple
• měnitelné (mutable): list, diet, set
Příklady, kde důležité:
• změna indexováním
• předávání parametrů funkcím o indexování slovníku
40/71
• None - jedinečná hodnota typu NoneType
• význam: „prázdné", „žádná hodnota"
• využití: např. defaultní hodnota parametrů funkcí
• implicitní návratová hodnota z funkcí (pokud nepoužijeme return)
AI/ll
ravdivostnŕ hodnota
if value:
print("foo")
Pro které z těchto hodnot value se vypíše f <
True, False, 3, 0, 3.0, -3, [3], [] , None
ravdivostnŕ hodnota
test je úspěšný ("tme") vždy, kromě následujících prípadu
• konstanty: None, False
• nulové hodnoty u numerických typů: 0, 0.0, Oj
• prázdné sekvence (nulová délka měřená pomocí len)
D. ().
(mírně zjednodušeno, např. u objektů může být komplikovanější)
• type(x) - zjištění typu
• isinstance(x, t) - test, zdaje proměnná určitého typu
values = [3, 8, "deset", 4, "dva", "sedm", 6] s = 0
for value in values:
if isinstance(value, int):
s += value else:
print("Not int:", value) print("Sum of ints:", s)
44/71
• použití funkce při její vlastní definici
• volání sebe sama (s jinými parametry)
To iterate is human, to recurse divine. (L. Peter Deutsch)
45/71
xkcd: Tabletop Roleplaying
YOUR PARTY ENTERS THE TAVERN.
I GATHER EVERYONE AROUND / A TABLE. I HAVE THE ELVE5 / START WHITTLING PICE AND / GET OUT SOME RURCHMENT / FOR CHARACTER 5HEETS. /
\       HEY, NO RECURSW.
\ I
https://xkcd.com/244/
46/71
https://xkcd.com/688/
47/71
Sebereferenčnř test
O Které písmeno není správnou odpovědí na žádnou otázku: (A) A   (B) C   (C) B
O Odpověď na 3. otázku je:
(A) stejná jako na 1. otázku   (B) stejná jako na 2. otázku   (C) jiná než odpovědi na 1. a 2. otázku
O První otázka, na kterou je odpověď A, je otázka: (A)l   (B)2 (C)3
Hlavolamikon
48/71
Rekurze a sebereference
Rekurze a sebereference - klíčové myšlenky v informatice
některé souvislosti:
• matematická indukce
• funkcionální programování
• rekurzivní datové struktury (napr. stromy)
• gramatiky
• logika, neúplnost
• nerozhodnutelnost, diagonalizace
49/71
Rekurze a sebereference
nejen v informatice
M. C. Escher; Drawing Hands, 1948
Gödel, Escher, Bach: An Eternal Golden Braid; Douglas Hofstadter
50/71
Faktoriá
n! = 1 • 2 • • • (n — 1) • n
f{n) =
1
pokud n = 1
n • f (n — 1)   pokud n > 1
51/71
Faktoriál iterativně (pomocí cyklu)
def fact(n): f = 1
for i in range(1,n+l):
f = f * i return f
52/71
Faktoriál rekurzivně
def fact(n):
if n == 1: return 1
else: return n * fact(n-l)
5    vT) c\ o 53/71
Faktoriál rekurzivně - ilustrace výpočtu
fact (4)
24
4 * fact(3
3 * fact (2
'2
ftctd) 1
54/71
Vymyslete funkci, která:
• vypíše čísla od 1 do N
• pomocí rekurze - bez použití cyklů f or, while
55/71
Vymyslete funkci, která:
• vypíše čísla od 1 do N
• pomocí rekurze - bez použití cyklů for, while
def sequence(n): if n > 1:
sequence(n-1) print(n)
56/71
Co udělá tento program?
def test(n): print(n) if n > 1:
test(n-1) print(-n)
test(5)
57/71
Ilustrace zanořování
test(3)
3 test(2)
def
def
a rekurze
even(n):
print("even", n) odd(n-l)
odd(n) :
print("odd", n) if n > 1:
even(n-l)
even(lO)
<  □  ►   4 ^ t   <  -Ž  ►   4 *
59/71
60/71
Rekurzivní stromeček
nakreslit stromeček znamená:
• udělat stonek
• nakreslit dva menší stromečky (pootočené)
• vrátit se na původní pozici
Stromeček želví grafikou
def tree(length): forward(length) if length > 10: left(45)
tree(0.6 * length) right(90)
tree(0.6 * length) left(45) back(length)
62/71
oby rekurze, odstranění rekurze
• koncová rekurze (tail recursion)
• rekurzivní volání je poslední příkaz funkce
• lze vesměs přímočaře nahradit cyklem
• „plná" rekurze
• „zanořující se" volání
• např. stromeček
o lze přepsat bez použití rekurze za použití zásobníku
• rekurzivní podoba často výrazně elegantnější
63/71
Hanojské věže aneb 0 konci světa
a klášter kdesi vysoko v horách u města Hanoj
• velká místnost se třemi vyznačenými místy
• 64 různě velkých zlatých disků
• podle věštby mají mniši přesouvat disky z prvního na třetí místo
• a až to dokončí ...
•<□►   4 ^ t   <  -ž  ►   <  -š ►
64/71
Hanojské věže: pravidla
• N disků různých velikostí naskládaných na sobě
• vždy může být jen menší disk položen na větším
• možnost přesunout jeden horní disk na jiný kolíček
• cíl: přesunout vše z prvního na třetí
65/71
Hanojské věže: řešení
JZEZL
: [
i i
1 cE
i i
i c
I I
66/71
Hanojské věže: výstup programu
»> solve(3, "A", "B", "C")
A -> B
A -> C
B -> C
A -> B
C -> A
C -> B
A -> B
Hanojské věže: rekurzivní řešení
ľ
def solve(n, start, end, auxiliary): if n == 1:
print(start, "->", end) else:
solve(n-1, start, auxiliary, end) solved, start, end, auxiliary) solve(n-1, auxiliary, end, start)
68/71
Hanojské věže: souvislosti
• Sierpiňského fraktál
• Pascalův trojúhelník
https://www.youtube.com/watch?v=8yaoED8j c8Y
69/71
• Předpokládejme, že y je seznam. Jaký je rozdíl mezi x = yax = y [: ] ?
• Jaký je význam pojmů „globální proměnná" a „lokální proměnná "?
• Jaké jsou nevýhody použití globálních proměnných?
• Jaký je význam pojmů „hluboká kopie" a „mělká kopie"?
• Jaké jsou v Pythonu hlavní vestavěné typy? Které z nich jsou měnitelné a které neměnitelné?
• Co je to rekurze?
• Jak zapíšeme výpočet faktoriálu: a) za použití rekurze, b) bez použití rekurze?
•<□►   4 ^ t   <  -ž  ►   <  -š ►
70/71
• představa o reprezentaci v paměti je potřeba
• globální, lokální proměnné
• předávání parametrů funkcím
• mělká vs. hluboká kopie
9 typy, měnitelné, neměnitelné
• rekurze
příště: regulární výrazy, zpracování textu
71/71