Borromeo gyűrűk
BSc Matematika Alapszak
Tantárgyleírás
2020.

Matematikai algoritmusok és felfedezések1

  • Óraszám (ea+gy): 2 + 2
  • Specializáció: matematikus
  • Kredit (ea+gy): 3 + 3
  • Számonkérés: kollokvium + gyak. jegy
  • Tárgykód (ea, gy): felfed1x0_m20ea, felfed1x0_m20ga
  • Ajánlott félév: 4
  • Státusz: köt. vál.
  • Specializáció: alk. mat.
  • Kredit (ea+gy): 3 + 3
  • Számonkérés: kollokvium + gyak. jegy
  • Tárgykód (ea, gy): felfed1x0_m20ea, felfed1x0_m20ga
  • Ajánlott félév: 4
  • Státusz: köt. vál.
  • Specializáció: elemző
  • Kredit (ea+gy): 3 + 3
  • Számonkérés: kollokvium + gyak. jegy
  • Tárgykód (ea, gy): felfed1x0_m20ea, felfed1x0_m20ga
  • Ajánlott félév: 4
  • Státusz: köt. vál.
Óraszám
ea(+k) + gy(+k)
Kredit
ea + gy
Számonkérés Specializáció Tárgykód
ea/gy
Ajánlott
félév
Státusz
2 + 2 3 + 3 kollokvium +
gyak. jegy
matematikus felfed1x0_m20ea
felfed1x0_m20ga
4 köt. vál.
3 + 3 kollokvium +
gyak. jegy
alk. mat. felfed1x0_m20ea
felfed1x0_m20ga
4 köt. vál.
3 + 3 kollokvium +
gyak. jegy
elemző felfed1x0_m20ea
felfed1x0_m20ga
4 köt. vál.
Erős Gyenge előfeltételek
Gyakorlat
Erős:
Matematika kritériumtárgyG (bevmat1x0_m17ga)
Előadás
Gyenge:
a gyakorlat

Megjegyzések

  • A tantárgy oktatásának módja: Előadás és géptermi gyakorlat.
  • Követelmény: Gyakorlaton beadandók és zárthelyi. Előadáson a követelmény vizsga, az oktató azonban megajánlhat jegyet az évközi munka alapján.

A tematikát kidolgozta:

Szükséges előismeretek

Ajánlott a Véges matematika1 és a Számelmélet1 tantárgyak ismerete. Az alábbi Python ismereteket átvesszük a kurzus során: értékadás, függvény definiálás, adattípusok és adatstruktúrák (int, float, Boole változó, string, lista, tuple, szótár), for ciklus, while ciklus, kondicionálás, rekurzió, osztályok definiálása (öröklés), list comprehension, többszörös ciklusok, kivétel kezelés (try, except), Numpy és Scipy könyvtárak.

A tantárgy célkitűzése

  • A tantárgy elsődleges célja a hogy megismertesse a hallgatókat a matematikai és tudományos programozás alapjaival. Olyan témakörök, algoritmusok, módszerek bemutatására törekszünk, amelyek segítséget nyújtanak mind elméleti, mind alkalmazott matematikai problémák megoldásában.
  • A tantárgy másodlagos célja Python programozási nyelven komolyabb (de 1000 sor alatti) hallgatói programok létrehozása.
  • A kurzus során az oktatásban, valamint a beadandó feladatok esetében is olyan példák és feladatok kiválasztására törekszünk, ami segíti a diákok algoritmikus gondolkodásának fejlesztését valódi matematikai problémákon keresztül.

Irodalom

  • Peter Wentworth, Jeffrey Elkner, Allen B. Downey and Chris Meyers: Hogyan gondolkozz úgy, mint egy informatikus: Tanulás Python 3 segítségével 3. Online elérhető.
  • Peter Wentworth, Jeffrey Elkner, Allen B. Downey and Chris Meyers: How to think like a computer scientist. Online elérhető (ennek a könyvnek sok verziója van).
  • Mark Lutz: Learning Python. Online elérhető.
  • A Python nyelv hivatalos honlapja.
  • Magyar fordítás a Python 3.6 dokumentációjához.

Tematika

  • Számelméleti algoritmusok: számrendszer váltás, is_prime függvény, prímszámláló függvény, legnagyobb közös osztó (egyidejű értékadás), prímfelbontás, Eratoszthenészi szita, lánctörtek (rekurzió), Legendre szimbólum kiszámítása, RSA algoritmus (gyors hatványozás modulárisan).
  • Kombinatorikus problémák, algoritmusok: Fibonacci sorozat, Collatz sejtés (3n+1), dinamikus programozás, hátizsák probléma.
  • Gráfelméleti algoritmusok: szélességi és mélységi keresés, legrövidebb út keresése, összefüggő-e a gráf,  Prüfer-kód, topológiai rendezés, PERT módszer.
  • Algebrai algoritmusok: maradékos osztás polinomokkal, mátrixok (összetett adatstruktúra), Gauss elimináció.
  • Numerikus és analitikus módszerek: Newton algoritmus gyökkeresésre.
  • Statisztikai vizsgálatok, kriptográfia: szövegben betűeloszlás (szótár használata). Mono és polialfabetikus rejtjelezés és megfejtésük.