Funkcionális programozás C++-ban
VERSENY IDEJE, HELYSZÍNE
November 21 (hétfő) 9:00-12:00, J202
VERSENYFELELŐS TANSZÉK
Távközlési és Médiainformatikai Tanszék
VERSENYFELELŐS OKTATÓ
Varga Pál
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 időtartama három óra, amelyet a versenyzők tetszőlegesen oszthatnak meg a gyakorlati és elméleti rész között. 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. 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
Egy saját kézzel írt A4-es lap (2 oldal), számológép (amire nem lesz szükség), illetve papír és íróeszköz. A gyakorlati feladatok megoldása során használható laptop (használatát ajánljuk is), de annak használata után már nem lehet visszatérni az elméleti feladatokhoz. Nem szabad használni telefont, másik versenyzőt, ill. a felügyelő oktató(ka)t.
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