Observații generale
Această programă se bazează pe programa SEPI pentru ONI liceu, folosită începînd cu ONI 2024. În mai mică măsură, programa se inspiră din subiecte date la barajele ONI și la loturile din anii anteriori. Ocazional vom relua noțiuni considerate cunoscute pentru a corecta diverse implementări ineficiente sau neelegante care plutesc prin supa culturală.
Cercul tratează și partea practică a programării. Un program scris, dar care nu merge, nu este „99% gata, am doar un bug”. Depanarea poate ocupa între 0% și 99% din timpul scrierii unui program, în funcție de calitatea codului. Vom învăța principii și unelte cu care să putem scrie cod mai robust și să găsim bugurile sistematic și rapid atunci cînd ele totuși apar.
Temele sînt obligatorii și veți primi feedback individual pentru ele. Mă aștept să le faceți fără excepție și să țineți cont de feedbackul anterior. Dacă veniți la cerc ca să creșteți ca programatori, atunci lăsați-mă pe mine să decid cum se va întîmpla asta, nu alegeți doar ce credeți voi că este suficient. 🙂 Două programe care funcționează pot diferi radical ca lizibilitate, robustețe, calitate. Elevii care nu își însușesc feedbackul și nu îl aplică vor primi avertismente.
Raportul cu anul 2023-2024
Pentru elevii care au participat la cercul de anul trecut și se întreabă dacă să revină și anul acesta: schimbările vor fi mici. Voi rafina notele de curs pentru a include mai multe detalii și figuri. Voi căuta probleme noi pentru teme și, eventual, pentru cursuri. Ocazional vom trece mai lent prin subiecte pe care în anul 2023-2024 le-am parcurs în grabă sau le-am omis cu totul din lipsa timpului. Dar 90% din materia acoperită va fi aceeași.
Programa
Bune practici în programare
- cod curat și cod spaghetti, incluzînd
- designul codului pentru claritate
- invarianți de buclă
- programarea prin contract
- adaptarea la nevoile problemei (prin contrast cu dopajul / rețetele)
- depanarea programelor, incluzînd
- metoda „forță brută + generator + rulare în buclă”
- generatoare de vectori, de permutări, de arbori, de grafuri
Structuri de date
Baze necesare: vectori, liste, stive ordonate, structuri de mulțimi disjuncte, preferabil arbori Fenwick.
- arbori Fenwick („aib”)
- construcție în \(\mathcal{O}(n)\)
- actualizări punctuale
- actualizări pe interval
- căutare binară în \(\mathcal{O}(n)\)
- aflarea unei valori punctuale în \(\mathcal{O}(1)\) amortizat
- alte funcții decît adunarea (exemplu: bitset și OR)
- funcții neinversabile (exemplu: max)
- arbori Fenwick 2D
- arbori de segmente („aint”)
- construcție în \(\mathcal{O}(n)\)
- actualizări punctuale, implementare iterativă
- actualizări pe interval, implementare recursivă
- nou actualizări pe interval, implementare iterativă
- căutare binară
- structuri de date echilibrate
- treaps
- exemple de alte structuri (skip lists, arbori roșu-negru etc.)
- comparație cu structurile din STL și PBDS
- stivă ordonată, cazuri interesante
- ca suport pentru RMQ (cu ordonarea interogărilor, în \(\mathcal{O}(\log n)\))
- pe calea curentă din arbore, menținută pe durata DFS-ului
- structuri de mulțimi disjuncte, cazuri interesante
- șmenul lui Mars peste vectorul de mulțimi disjuncte
- bit hacks (compactarea variabilelor, logaritm în baza 2, popcount)
Metode de programare
Baze necesare: programare dinamică.
- probleme core („ad-hoc”)
- descompunere în radical
- evitarea împărțirilor
- alegerea mărimii blocurilor cînd operațiile au costuri inegale
- metode pentru probleme de interogare + actualizare
- sortarea operațiilor
- algoritmul lui Mo
- simularea ștergerilor cu un cost extra de \(\mathcal{O}(\log n)\) („aint pe timp”)
- evitarea duplicării codului prin oglindirea/rotirea datelor
- tehnica meet in the middle
- analiză sintactică (cu gramatici)
- programare dinamică (exemple concrete cînd le întîlnim în probleme)
Matematică
- combinatorică
- permutări și combinări, cu și fără repetiții: ranking, unranking,
next() - calculul semnului unei permutări
- permutări și combinări, cu și fără repetiții: ranking, unranking,
- algoritmul lui Euclid extins
- funcția Möbius
- principiul includerii și excluderii expus rapid, doar ca suport
- exponențiere prin ridicare la pătrat
- aplicabilă și la permutări, matrice etc.
- exponențiere de permutări în \(\mathcal{O}(n)\) prin descompunere în cicluri
- exponențiere în \(\mathcal{O}(1)\) cu precalculare în \(\mathcal{O}(\sqrt{n})\)
- iterarea prin toți divizorii unui număr
- inverse modulare
- Teorema chineză a resturilor
Șiruri de caractere
Șirurile nu mai sînt în programă, dar anumiți algoritmi au aplicabilitate generală.
- sortare ternară
- hashing; rolling hash; căutare cu metoda Rabin-Karp
- paradoxul zilei de naștere
- trie
Arbori
Baze necesare: reprezentare, DFS.
- reprezentare prin vectori de părinți
- reprezentare („parcurgere”) Euler; aplicații cu interogări + actualizări
- test de strămoș („este \(u\) strămoșul lui \(v\)?”)
- LCA (lowest common ancestor)
- algoritmul cu reprezentare Euler
- algoritmul offline (Tarjan)
- descompunere în radical
- binary lifting cu \(\mathcal{O}(\log n)\) pointeri per nod
- binary lifting cu 2 pointeri per nod
- distanțe în arbore
- arbori parțiali minimi
- acoperire minimă cu noduri
- recurențe pe arbore
- tehnica small-to-large
- heavy-light decomposition
- descompunere în centroizi
Ultimele două subiecte depășesc programa, dar sînt tehnici foarte puternice și generale.
Grafuri
Baze necesare: reprezentare, DFS, BFS, conexitate.
- BFS și DFS: observații teoretice, culori, timpi de vizitare, clasificarea muchiilor
- BFS pe graf implicit (exemplu: Invesort)
- DFS iterativ (cînd memoria este o problemă)
- sortare topologică (doi algoritmi)
- componente tare conexe (doi algoritmi)
- graful componentelor
- 2-SAT
- componente biconexe, punți, puncte de articulație
- distanțe în grafuri
- algoritmii lui Dijkstra și Bellman-Ford
- algoritmul lui Dial
- 0-1 BFS
- tratarea costurilor în noduri (exemplu: Regate)
- drumuri și circuite euleriene
- grafuri bipartite
- cuplaje
- teorema lui Kőnig, acoperire minimă, set independent maxim
- fluxuri
- elemente de teorie: Teorema flux maxim – tăietură minimă
- algoritmi bazați pe drumuri de creștere: Ford-Fulkerson, Edmonds-Karp, Dinitz
- algoritmul push-relabel
- flux maxim de cost minim
Geometrie computațională
- deziderate practice: evitarea împărțirilor, a erorilor de precizie a cazurilor particulare
- puncte, vectori, produse, unghiuri, drepte
- orientare, determinanți
- posibil: dualitatea punct-dreaptă
- Teorema lui Pick
- algoritmi
- baleiere
- înfășurătoarea convexă
- șublerul rotitor
Rudimente de GNU/Linux și Bash
- măsurarea timpului și a memoriei
- piping și redirecționarea ieșirii
- rularea în buclă a două programe pentru compararea rezultatelor
- alte unelte:
grep,cut,diff,awk,sed,bc,factor, generarea de numere aleatorii
Miscellanea
În limita timpului, putem explora cîteva dintre subiectele de mai jos (voi alegeți).
- stringuri
- căutare cu automate finite
- noțiuni teoretice despre automatele finite
- căutare cu metoda Knuth-Morris-Pratt
- funcția Z
- arbori de sufixe
- șiruri de sufixe
- vectorul LCP (longest common prefix)
- algoritmul lui Manacher
- căutare cu automate finite
- criptografie
- elemente de aritmetică modulară
- algoritmi de criptare și semnare
- algoritmi pentru jocuri logice
- euristici statice
- alfa-beta
- Proof Number Search
- Monte Carlo Tree Search
- tabele de finaluri
- servere și site-uri web
- anatomia unui request HTTP
- servere HTTP (sau de email etc.)
- baze de date
- nivelurile de cod ale unui site web
- caching
- backup
- compresia datelor
- analiză lexicală și sintactică (parsare)
- sisteme de control al versiunilor (git etc.)
- noțiuni de programare orientată pe obiect (clase, interfețe etc.)
- noțiuni de design software (testare și altele)
- criptomonede
Discuții filozofice
Ca mici intermezzouri în alte subiecte sau ca dialoguri mai ample:
- Olimpiada nu este scopul suprem.
- Minte sănătoasă în corp sănătos.
- Cariera academică și cariera în industrie.
- Viața la facultate în România, în afara României.
- Software liber, libertăți digitale.
- Abordarea concursurilor.
[mathjax]