Funkcionális programozás C++-ban
VERSENY IDEJE, HELYSZÍNE
Elméleti rész: november 7. 12:15-13:45, Terem: IB139
Gyakorlati rész: november 9. 16:00-20:00 (távolról)
VERSENYFELELŐS TANSZÉK
Távközlési és Mesterséges Intelligencia Tanszék
VERSENYFELELŐS OKTATÓ
Varga Pál, Németh Gábor
A VERSENY SZÖVEGES LEÍRÁSA
Hogy melyik a legjobb programozási paradigma? A versenynek nem célja ennek a kérdésnek a megválaszolása. De azok számára, akik már elgondolkodtak azon, hogy a modern C++-ban megjelenő új típusoknak hol kereshető a gyökere, azok számára kíván érdekes feladatok mentén betekintést nyújtani a funkcionális programozás tárházába.
A verseny két részből áll. A gyakorlati részén rövid, elgondolkodtató C++ programok, függvények megírása a feladat, amelyek nem algoritmikus nehézségükkel, hanem elsősorban a megoldás során használható eszközökben való megkötéssel sarkallják funkcionális gondolkodásra a versenyzőket. Az elméleti megmérettetés a funkcionális programozás matematikai gyökereihez kalauzolja a versenyzőket: a lambda kalkulus és a kategóriaelmélet világába.
A verseny elméleti részének a megoldására másfél, a gyakorlati rész megoldására pedig négy óra áll a rendelkezésre. A versenyen nem cél az összes feladat megoldása, a feladatokat úgy válogatjuk, hogy akár csak az elméleti, vagy akár csak a gyakorlati feladatok megoldásával előkelő helyezést lehessen elérni. Így tetszőlegesen részt lehet venni akár csak a verseny egyik részén is. A versenyen a BME minden BSc-s és MSc-s képzésén résztvevő hallgatója indulhat.
VERSENYEREDEMÉNY BESZÁMÍTÁSA
A tárgyat hallgatók számára a sikeres szereplés a vizsgán elért eredménybe is beleszámít, kiemelkedő eredmény esetén megajánlott jelest is eredményezhet.
MINTA FELADATSOR
A versenyen alapvetően az alábbi feladattípusokkal találkozhatnak a résztvevők:
- Programozás: egyszerű feladatok megoldása C++-ban megadott kritériumok mellett (pl. nem szabad ciklust használni)
- Sablonok: általános funkcionális függvények, adatstruktúrák tervezése és implementálása
- Bizonyítás: kategória- és funktortulajdonságok bizonyítása
- Redukciós szabályok, evolúciós szabályok: λ-kalkulus, illetve annak bővítése szintaktikus édesítőszerekkel
KATEGÓRIÁK
Nincs.
HASZNÁLHATÓ SEGÉDESZKÖZÖK
Az elméleti rész megoldásához bármilyen kézzel írt vagy nyomtatott segédlet felhasználható. A gyakorlati rész feladatainak a megoldása során bármilyen segítség felhasználható.
TÉMAKÖRÖK
λ-kalkulus, redukció, kategóriaelmélet, funktorok, monádok, funkcionális programozás, variadikus sablonok
FELKÉSZÜLÉST SEGÍTŐ ANYAGOK
- Csörnyei Zoltán: Lambda-kalkulus
- Benjamin C. Pierce: Types and Programming Languages
- Ivan Čukić: Functional Programing in C++
- Bartosz Milewski: Category Theory for Programmers
- Ivan Horton, Peter Van Weert: Beginning C++17, From Novice to Professional
- Tai-Danae Bradley: What is Applied Category Theory?
- Philip Wadler: Propositions as Types