Geonote — (cons geo note)
Raccolta work in progress (†) di note teoriche pensate come riferimento rapido e materiale di ripasso. Gli appunti spaziano dai fondamenti dei linguaggi di programmazione (sistemi di tipi, OOP, closure) alla teoria della computazione (riduzioni, classi di complessità, costo algoritmico) e qualche richiamo di matematica e statistica.
Chiude la raccolta una sezione di problemi tipici da colloquio tecnico e competizioni, risolti con più approcci (ricorsione diretta, programmazione dinamica, forme chiuse).
Teoria, fondamenti e curiosità
Teoria dei linguaggi
- Sistemi di tipi — statico/dinamico, forte/debole, inferenza, null/option, ADT, polimorfismo.
- I tipi Go e OOP — predicati, contratti, struct type, interfacce, ereditarietà, multiple dispatch.
- I tipi Guile e GOOPS — predicati, contratti, record type, classi, ereditarietà, multiple dispatch.
- I tipi R e S3/S4/R6 — predicati, contratti, coercizioni, S3, S4, multiple dispatch, R6.
- Closure — definizione, upward funarg problem, rappresentazione a runtime e confronti.
- Regex — sintassi, matching, flavor (POSIX/PCRE/RE2/ECMAScript), ReDoS, con esempi.
Teoria della computazione
- Classi di complessità — notazione, MdT, P, NP, co-NP, NP-completezza, PSPACE, EXPTIME.
- Costo algoritmico — caso pessimo, ottimo, medio e ammortizzato con tecniche di calcolo.
- Riduzioni — many-one, Turing, da SAT a Vertex Cover, teorema di Cook-Levin.
Fondamenti
- Fondamenti Go — sintassi base (variabili e tipi, strutture di controllo, funzioni, concorrenza).
- Fondamenti Guile — sintassi base (S-espressioni, tipi di dato, funzioni, ricorsione e scripting).
- Fondamenti R — elementi per il calcolo statistico (tipi di dato, vettori, matrici, strutture dati).
Matematica e statistica
- Elementi di Analisi — successioni, serie, integrale di Riemann.
- Elementi di Probabilità † — spazi di probabilità, variabili aleatorie, distribuzioni.
- Elementi di Statistica † — variabili aleatorie, distribuzioni, stima e test d'ipotesi.
- Catene di Markov † — stati e transizioni, proprietà di Markov, ergodicità, distribuzione stazionaria.
Strumenti e curiosità
- Geoteo CSS — come ereditare stile, MathJax e Mermaid da
geoteo.net. - GitHub Actions — workflow YAML, eventi, DAG di job, matrix, cache e permessi/OIDC.
Interview problems e programmazione competitiva
Programmazione dinamica
- Risolvere Fibonacci — ricorsione diretta, PD top-down (memoization) e bottom-up.
- Numero di BST — ricorsione, PD, forma chiusa e numeri di Catalan.
- Matching di regex — implementazione di
.e*con ricorsione diretta e PD. - Partizione insieme — ricorsione diretta e PD, ottimizzazione spazio e tempo.
- Scomposizione di stringhe — ricorsione diretta, PD top-down e bottom-up (BFS).
Problemi famosi
- Knapsack problem † — ottimizzazione con vincolo di capacità, PD 0/1 e frazionario.
- Ponti di Königsberg † — teoria dei grafi, cammini e circuiti euleriani.
- Travelling salesman † — NP-hardness, ricerca esaustiva, PD con bitmask (Held-Karp), euristiche.
- Postino cinese † — teoria dei grafi, matching perfetto minimo, estensione del caso euleriano.
- N-Regine † — backtracking, pruning e PD con bitmask.
- Secretary problem † — arresto ottimale, strategia a soglia e regola $1/e$.