Funkcionális programozás C++-ban

VERSENY IDEJE, HELYSZÍNE
2021. november. 24., 8:30-11:30, R504

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 íróeszköz. A gyakorlati feladatok megoldása során használható laptop is, de annak használata után már nem lehet visszatérni az elméleti feladatokhoz. Nem szabad használni a telefont, a 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