Algoritmusok Python nyelven

1. Előadás, Bevezetés a programozásba és a Python nyelvbe.

2020. február 13.

Technikai információk

Diák elérhetősége:

damasdigabor.web.elte.hu/teaching

Oktatók

Előadás: Damásdi Gábor damasdigabor@caesar.elte.hu

  • Iroda: Déli 3.508
  • Fogadó óra: Csütörtök 10:00-12:00

Gyakorlat: Csanády Bálint csbalint@cs.elte.hu

Gyakorlat: Varga Bálint balorkany@gmail.com

  • Iroda: Déli 3.605

Előadás időpontja: 14:00-15:30

Tantárgy célja

  • Matematikusok számára hasznos programozási tudás átadása
  • Programozás általános folyamatának gyakorlása
  • Egy programozási nyelv (Python) alapjainak elsajátítása
  • Matematikusoknak hasznos programozási könyvtárak megismerése

  • Matematikai algoritmusok implementálása

  • Alapozás későbbi órákhoz(Algoritmusok tervezése és elemzése, Adatbányászat, Deep learning)

Tematika

Három fő témakör lesz:

  • Python alapjai
  • Hasznos könyvtárak
  • Matematikai algoritmusok

Tananyag

Az előadás és a gyakorlat anyaga mindig elérhető lesz a honlapon az óra kezdete előtt. damasdigabor.web.elte.hu/teaching

Források

Tutorialok

Gyakorlat

Követelmények

  • A gyakorlat elvégzése
  • Két beadandó feladat elkészítése
  • A második beadandó feladat bemutatása (viszgaidőszakban)
  • Mindkét feladat osztályozva lesz 1-től 5-ig.
  • A végső jegy, A és B osztályzat esetén:
In [1]:
def vegsojegy(a,b):
    if a==1 or b==1:
        return 1
    if (a+b)%2==0:
        return (a+b)/2
    else:
        if b>a:
            return (a+b+1)/2
        else:
            return (a+b-1)/2

Tehát a két jegy átlaga, és ha az nem egész, akkor a második beadandó jegye dönt.

Kérdések?

Az általunk használt programozási környezet

A programozás sokszínűsége

  • Python
  • Anaconda
  • Jupyter

Jupyter

  • Jupyter - Egy web applikáció melyben olyan dokumentumokat hozhatunk létre, melyek élő kódot, képleteket, grafikonokat tartalmaznak.
  • A Jupyter fájlok kiterjesztése .ipynb
  • de konvertálható sok féle formátumba (HTML, PDF, LateX ...)
  • A tartalom cellákba van rendezve.

Cella típusok

  1. kód cella (Python/R/Lua/... kód)
  2. szöveg cella
  3. markdown cella: Markdown által formatált szöveg

Kód cella

In [2]:
print("Hello world")

Hello world

Az utolsó parancs visszatérési értéke kiíródik. (Általában)

In [3]:
2 + 3
3 + 4
Out[3]:
7

Ez akár egy több értékből álló "tuple" is lehet. (Ahogy sok mindenre, a "tuple" szóra sem találtam jó fordítást. Talán "többes"?)

In [4]:
2 + 3, 3 + 4, "hello " + "world"
Out[4]:
(5, 7, 'hello world')

Markdown cella

Ez itt félkövér

Ez meg dőlt

Ez meg itt
egy táblázat

Még a Latex is működik:

$$ \frac{1}{n}\sin x= \frac{sinx}{n}= \frac{sixn}{n}= six\frac{n}{n}=six=6 $$
Ez meg csak egy unalmas szöveges cella

Jupyter használata

Parancs mód és szerkesztési mód

  1. Parancs mód: utasítások végrehajtása a cellákon, a tartalmuk megváltoztatása nélkül.
    • A kijelölt cellák kékek
  2. Szerkesztési mód: Egy adott cella tartalmának módosítása.
    • A kijelölt cella zöld színű

Váltás a módok között

  1. Esc: Szerkesztési -> Parancs
  2. Enter vagy dupla klikk: Parancs -> Szerkesztési

Cella futtatása szerkesztési módban

  1. Ctrl + Enter: cella futtatása
  2. Shift + Enter: cella futtatása és ugrás a következőre
  3. Alt + Enter: cella futtatása és új cella beszúrása

Hasznos shortcutok parancs módban

  • enter: cella szerkesztése
  • a/b : cella beszúrása a kijelölt cella alá/fölé (az above/below alapján)
  • m/y : cella típusának váltása: Markdown/Kód
  • dd : cella törlése
In [5]:
2+2
Out[5]:
4

Cella mágia (cell magic)

Speciális parancsok, amik módosítják a cella működését.

In [6]:
%%time

for x in range(1000000):
    pass

Wall time: 101 ms
In [7]:
%%timeit

x = 2

59.1 ns ± 4.99 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
In [8]:
%%writefile hello.py

print("Hello world")

Overwriting hello.py
In [9]:
!python hello.py

Hello world

Az elérhető mágiák listája:

In [10]:
%lsmagic
Out[10]:
Available line magics:
%alias  %alias_magic  %autoawait  %autocall  %automagic  %autosave  %bookmark  %cd  %clear  %cls  %colors  %conda  %config  %connect_info  %copy  %ddir  %debug  %dhist  %dirs  %doctest_mode  %echo  %ed  %edit  %env  %gui  %hist  %history  %killbgscripts  %ldir  %less  %load  %load_ext  %loadpy  %logoff  %logon  %logstart  %logstate  %logstop  %ls  %lsmagic  %macro  %magic  %matplotlib  %mkdir  %more  %notebook  %page  %pastebin  %pdb  %pdef  %pdoc  %pfile  %pinfo  %pinfo2  %pip  %popd  %pprint  %precision  %prun  %psearch  %psource  %pushd  %pwd  %pycat  %pylab  %qtconsole  %quickref  %recall  %rehashx  %reload_ext  %ren  %rep  %rerun  %reset  %reset_selective  %rmdir  %run  %save  %sc  %set_env  %store  %sx  %system  %tb  %time  %timeit  %unalias  %unload_ext  %who  %who_ls  %whos  %xdel  %xmode

Available cell magics:
%%!  %%HTML  %%SVG  %%bash  %%capture  %%cmd  %%debug  %%file  %%html  %%javascript  %%js  %%latex  %%markdown  %%perl  %%prun  %%pypy  %%python  %%python2  %%python3  %%ruby  %%script  %%sh  %%svg  %%sx  %%system  %%time  %%timeit  %%writefile

Automagic is ON, % prefix IS NOT needed for line magics.
In [11]:
help()

Welcome to Python 3.7's help utility!

If this is your first time using Python, you should definitely check out
the tutorial on the Internet at https://docs.python.org/3.7/tutorial/.

Enter the name of any module, keyword, or topic to get help on writing
Python programs and using Python modules.  To quit this help utility and
return to the interpreter, just type "quit".

To get a list of available modules, keywords, symbols, or topics, type
"modules", "keywords", "symbols", or "topics".  Each module also comes
with a one-line summary of what it does; to list the modules whose name
or summary contain a given string such as "spam", type "modules spam".

help> quit

You are now leaving help and returning to the Python interpreter.
If you want to ask for help on a particular object directly from the
interpreter, you can type "help(object)".  Executing "help('string')"
has the same effect as typing a particular string at the help> prompt.

Mi történik a háttérben

  • minden notebook rendelkezik egy saját Kernel -el (Python interpreter)
    • a kernel megszakítható vagy újraindítható a menüből (interrupt/restart)
    • mindig futtasd a Kernel -> Restart & Run All parancsot mielőtt beadnád a házifeladatot/beadandót, hogy megbizonyosodj róla, hogy minden rendben működik
  • minden cella egy közös namespace-ben él.
  • a cellák tetszőleges sorrendben futtathatóak
  • ha újra megnyitunk egy notebookot akkor alapvetően az inputok és az outputok maradnak meg. Az objektumok nem!
In [12]:
print("Ez fut először")

Ez fut először
In [13]:
print("Aztán meg ez. Figyeld a számot bal oldalt.")

Aztán meg ez. Figyeld a számot bal oldalt.
In [14]:
a=2

a mutasson a 2 értékre.

In [15]:
a
Out[15]:
2

a még mindig a 2-re mutat

A cellák ki és bemenete később is elérhető.

In [16]:
42
Out[16]:
42
In [17]:
_
Out[17]:
42

Utolsó előtti output:

In [18]:
"first"
Out[18]:
'first'
In [19]:
"second"
Out[19]:
'second'
In [20]:
__
Out[20]:
'first'
In [21]:
__
Out[21]:
'second'

Utolsó előtti előtti:

In [22]:
___
Out[22]:
'second'

Az n. output is elérhető a _output_count változón keresztül. Ez csak akkor definiált ha az n. cellának volt kimenete.

Itt egy módszer az összes elérhető output listázására. (A kódot majd később megérted)

In [23]:
list(filter(lambda x: x.startswith('_') and 
            x[1:].isdigit(), globals()))
Out[23]:
['_3',
 '_4',
 '_5',
 '_10',
 '_15',
 '_16',
 '_17',
 '_18',
 '_19',
 '_20',
 '_21',
 '_22']

A bemenet hasonlóan elérhető

Előző input:

In [24]:
_i
Out[24]:
"list(filter(lambda x: x.startswith('_') and \n            x[1:].isdigit(), globals()))"

N. input:

In [25]:
_i2
Out[25]:
'print("Hello world")'

A Python programozási nyelv

A Python története

  • A Python egy holland programozó hobbi projektjeként indult. (Guido van Rossum)
  • Python 1.0 1994
  • Python 2.0 2000
    • garbage collector
    • Unicode támogatás
  • Python 3.0 2008
    • nem kompatibilis a korábbi verziókkal!!
  • Python2 End-of-Life (EOL): January 1, 2020
    • Ezért mi is csak a 3-al foglalkozunk
    • Frissítsétek a SAGE-t!

Python közösség és fejlesztés

  • Python Software Foundation nonprofit szervezet (Delaware, US)
  • egy erős közösség alakult ki, akik aktívan részt vesznek a fejlesztésben
  • nagy standard library
  • nagyon nagy third-party modul rendszer: PyPI (Python Package Index)
  • pip installer (pip = pip installs packages)
In [26]:
import wikipedia
In [27]:
wikipedia.search("London")
Out[27]:
['London',
 'City of London',
 'London, Ontario',
 'London Underground',
 'Greater London',
 'Wimbledon, London',
 'London boroughs',
 'University College London',
 'Jack London',
 'The London Gazette']
In [28]:
import antigravity

Python felhasználása

  • Web és Internet
  • Tudományos számítások
  • Tanítás

A Python általános tulajdonságai

Interpretált és fordított (compiled) nyelvek.

interpreted compiled

Valójában sok nyelv használ vegyes stratégiát, így a python is. Mi főleg interpretált nyelvként fogjuk használni.

Interpretált
  • gyors programírás
  • könnyű hibajavítás
  • általában lassabb
  • kód és program nincs szétválasztva

Whitespaces

  • zárójelek helyett indentáció van és befolyásolja a program futását
  • nincsenek pontosvesszők
In [29]:
n = 12
if n % 2 == 0:
    print("n páros")
else:
    print("n páratlan")

n páros

Dinamikus típuskezelés

  • Típusellenőrzés futásidőben történik és nem fordítási időben.
In [30]:
n = 2
print(type(n))

n = 2.1
print(type(n))

n = "foo"
print(type(n))

<class 'int'>
<class 'float'>
<class 'str'>

Értékadás (Assignment)

Kicsit más mint a legtöbb nyelvben:

  • C++-ban i = 2 kb azt jelenti, hogy a típussal rendelkező i változó megkapja a 2 érték másolatát.

  • Python i = 2 kb azt jelenti hogy az i név kap egy referenciát egy egy numerikus objektumhoz, aminek az értéke 2.

  • mindig a jobb oldal értékelődik ki először, majd pedig a bal oldali név kap egy referenciát a jobb oldali értékhez

Az id függvény visszaadja az objektum egyedi azonosító számát. (Miért lehet gond az id használatából?)

In [31]:
i = 2
print(id(i))

i = 3
print(id(i))

140733682196912
140733682196944
In [32]:
i = "elte"
print(id(i))

s = i
print(id(s) == id(i))

old_id = id(s)
s += "matek"
print(id(s) == id(i))
print(old_id == id(s))

2715208153648
True
False
False
In [33]:
a = 2
b = a
print(id(a) == id(b))
a += 1
print(id(a) == id(b))

True
False
In [34]:
a=25
b=25
a is b
Out[34]:
True
In [35]:
a=257
b=257
a is b
Out[35]:
False
In [36]:
25 is 25
Out[36]:
True
In [37]:
300 is 300
Out[37]:
True

Egyszerű utasítások

if, elif, else

In [38]:
n = int(input())
#n = 12

if n < 0:
    print("abrakadara")
    print("N negatív")
elif n > 0:
    print("N pozitív")
else:
    print("N se nem negatív se nem pozitív")

10
N pozitív

Feltételes kifejezések

  • egysoros if utasítások is vannak
  • Az operátorok sorrendje viszont különbözik a C nyelvben megszokottaktól. C-ben így nézne ki a kód:
int x = -2;
int abs_x = x>=0 ? x : -x;
  • Csak nagyon rövid kódok esetén ajánlott.

Pythonban:

<kifejezés1> if <feltétel> else <kifejezés2>

In [39]:
n = -2
abs_n = n if n >= 0 else -n
print(abs_n)

2

Listák

  • leggyakrabban használt beépített adatszerkezet
  • operációk: indexelés, hossz, hozzáfűzés
  • részletesen szó lesz róla később
In [40]:
l = []  # empty list
l.append(2)
l.append(2)
l.append("foo")

len(l), l
type(l)
Out[40]:
list
In [41]:
l[1] = "bar"
l.extend([-1, True])
len(l), l
Out[41]:
(5, [2, 'bar', 'foo', -1, True])

for, range

lista iterálása

In [42]:
for e in ["foo", "bar"]:
    print(e)
    print(e)

foo
foo
bar
bar

Az egészek egy intervallumán való iterálás

Így nézne ki C++-ban:

for (int i=0; i<5; i++)
    cout << i << endl;

A range mindig 0-val kezdődik!

In [43]:
for i in range(5):
    print(i)

0
1
2
3
4

Megadhatjuk a kezdőértéket:

In [44]:
for i in range(2, 5):
    print(i)

2
3
4

Megadhatjuk a növekedés értékét is. Ekkor viszont kötelező megadni a kezdőértéket is.

In [45]:
for i in range(0, 10, 2):
    print(i)

0
2
4
6
8

while

In [46]:
i = 0
while i < 5:
    print(i)
    i += 1
i

0
1
2
3
4
Out[46]:
5

Nincs do...while Pythonban.

break és continue

  • break: ha korábban ki akarunk lépni egy ciklusból
  • continue: ha korábban szeretnénk a következő ciklus futásra lépni
In [47]:
for i in range(10):
    if i % 2 == 0:
        continue
    print(i)

1
3
5
7
9
In [48]:
for i in range(10):
    if i > 4:
        break
    print(i)

0
1
2
3
4

Függvények

Fontos, hogy ezek nem matematikai függvények. Például nem csak a bemenettől függ a függvényérték.

Függvény definíció

Függvényeket a def kulcsszó segítségévek használhatunk:

In [49]:
def foo():
    print("én egy nagyon okos függvény vagyok")
     
foo()

én egy nagyon okos függvény vagyok

Függvény argumentumok, paraméterek

  1. pozíció szerinti (positional)
  2. kulcsszavas (named or keyword arguments)

Először a pozíció szerintieket kell írni aztán a kulcsszavasokat

In [50]:
def foo(arg1, arg2, arg3):
    print("arg1 ", arg1)
    print("arg2 ", arg2)
    print("arg3 ", arg3)
    
foo(1, 2, "asdfs")

arg1  1
arg2  2
arg3  asdfs
In [51]:
import this

The Zen of Python, by Tim Peters

Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
Flat is better than nested.
Sparse is better than dense.
Readability counts.
Special cases aren't special enough to break the rules.
Although practicality beats purity.
Errors should never pass silently.
Unless explicitly silenced.
In the face of ambiguity, refuse the temptation to guess.
There should be one-- and preferably only one --obvious way to do it.
Although that way may not be obvious at first unless you're Dutch.
Now is better than never.
Although never is often better than *right* now.
If the implementation is hard to explain, it's a bad idea.
If the implementation is easy to explain, it may be a good idea.
Namespaces are one honking great idea -- let's do more of those!
In [52]:
import random
def make_maze(w = 16, h = 8):
    vis = [[0] * w + [1] for _ in range(h)] + [[1] * (w + 1)]
    ver = [["|  "] * w + ['|'] for _ in range(h)] + [[]]
    hor = [["+--"] * w + ['+'] for _ in range(h + 1)]
 
    def walk(x, y):
        vis[y][x] = 1
 
        d = [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)]
        random.shuffle(d)
        for (xx, yy) in d:
            if vis[yy][xx]: continue
            if xx == x: hor[max(y, yy)][x] = "+  "
            if yy == y: ver[y][max(x, xx)] = "   "
            walk(xx, yy)
 
    walk(random.randrange(w), random.randrange(h))
 
    s = ""
    for (a, b) in zip(hor, ver):
        s += ''.join(a + ['\n'] + b + ['\n'])
    return s
In [53]:
print(make_maze())

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|              |              |                 |
+  +  +--+--+  +--+--+  +--+  +--+--+--+  +--+  +
|  |  |     |  |     |  |  |           |  |     |
+--+  +  +  +  +  +  +  +  +--+--+--+  +  +--+  +
|     |  |  |     |     |  |        |  |     |  |
+  +--+  +  +--+--+--+--+  +  +--+  +  +--+  +  +
|  |     |              |     |  |     |     |  |
+  +  +--+--+--+--+  +  +  +--+  +--+--+  +--+  +
|  |  |  |        |  |  |  |              |     |
+  +  +  +  +--+  +  +  +  +--+  +--+--+--+  +--+
|        |  |  |  |  |  |  |     |        |     |
+--+--+--+  +  +--+  +  +  +  +--+  +  +--+--+  +
|           |        |  |  |     |  |           |
+  +--+--+--+--+--+--+  +  +--+  +  +--+--+--+--+
|                       |        |              |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
In [ ]: