Luca Dan Șerbănați all'esame di maturità, 1961
Luca Dan Șerbănați nei primi anni Settanta
Luca Dan Șerbănați all'ultima lezione del quinto anno, aprile 1989

Luca Dan Șerbănați

Professore emerito alla Politehnica di Bucarest

Ricerca, insegnamento, industria e memorie

RO | EN | IT
Luca Dan Șerbănați a Venezia, 1990
Luca Dan Șerbănați a New York, 2005
Luca Dan Șerbănați

Riferimenti essenziali

Il contesto in cui nacque il corso

Nei primi anni Settanta, il progetto PNUD di cui beneficiò la Cattedra di Calcolatori ebbe, per me e per i miei colleghi, l’effetto di una finestra improvvisamente aperta: al di là delle nostre mura, l’informatica cambiava rapidamente e nelle grandi università stavano già prendendo forma nuove discipline, con un rigore e un’ambizione che il nostro vecchio piano di studi non poteva più coprire. Da questo confronto nacque, nel 1973, la proposta di un nuovo piano di studi, davvero rivoluzionario rispetto al precedente.

Ricordo bene il momento in cui comparvero, nello schema del piano, due titoli che allora suonavano quasi esotici per il Politecnico: “Teoria degli automi” e “Teoria dei linguaggi formali”. Erano corsi che sarebbero stati introdotti per la prima volta al Politecnico e, credo, anche in Romania. Un giorno, il direttore della cattedra mi disse semplicemente: «Li terrà lei.»

Sulla carta sembrava un incarico didattico come tanti altri. In realtà, fu per me l’inizio di una ricerca. Ciò che avrei dovuto insegnare non faceva parte della mia formazione di ingegnere automatico; dovetti costruirmi da solo il percorso necessario per portare la disciplina a una forma insegnabile al Politecnico. In quegli anni non avevamo una tradizione locale, né manuali facilmente disponibili, né una “scuola” capace di spiegare come insegnare gli automi e come collegarli naturalmente alla calcolabilità.

Dopo il primo anno di insegnamento, vidi quanto il corso fosse difficile e quanto facilmente se ne potesse perdere il filo se gli studenti disponevano soltanto degli appunti presi alla lavagna. Per questo mi affrettai a scrivere e pubblicare localmente un manuale dettagliato, che fissasse la materia, offrisse agli studenti un sostegno reale e, nello stesso tempo, registrasse il modo in cui allora comprendevo i fondamenti: automi, linguaggi, calcolabilità e funzioni ricorsive.

Visto oggi, questo manuale — di una qualità tipografica quasi preistorica — mi ricorda anche il lavoro minuzioso che vi stava dietro: formule battute a macchina, correzioni, discussioni con la tipografia, la fretta di mettere a disposizione degli studenti un supporto coerente. Per me rimane non soltanto uno strumento didattico del suo tempo, ma anche la traccia di una fase in cui l’informatica teorica era diventata, in modo esplicito, una delle mie preoccupazioni centrali.

Struttura e idee principali del manuale

  • Parte I – Introduzione. Stabilisce il vocabolario di base — stati, transizioni, ingressi e uscite — e la distinzione finito / infinito, come soglia concettuale prima della formalizzazione.
  • Parte II – Teoria degli automi finiti. Sviluppa l’apparato matematico e tecnico: definizioni, rappresentazioni, relazioni tra automi, equivalenze, automi parzialmente definiti, realizzazione e automa come accettore, vale a dire il legame tra automi e linguaggi.
  • Struttura degli automi finiti. Tratta la “scatola nera”, l’interconnessione degli automi, la sostituzione, le partizioni e la riduzione, nonché le decomposizioni in serie e in parallelo. La conclusione prepara il passaggio ai linguaggi: teorema di Kleene, espressioni regolari e automa finito non deterministico.
  • Parte III – Automi infiniti. Calcolabilità. Introduce la macchina di Turing — definizione, esempi, simulazione, macchina universale —, discute i limiti della calcolabilità, in particolare il problema dell’arresto, e mette in relazione la calcolabilità secondo Turing con la teoria delle funzioni ricorsive — primitive ricorsive, minimizzazione e funzioni ricorsive generali.

Significato del corso

Il corso non era concepito soltanto come una raccolta di definizioni e teoremi. Doveva offrire al futuro ingegnere informatico una disciplina del rigore: comprendere che cosa significa un modello formale, come si esprime il comportamento di un sistema simbolico e dove si trovano i limiti del calcolo effettivo.

In questo senso, Teoria degli automi apriva la strada verso settori che sarebbero diventati importanti più tardi nella mia attività: linguaggi formali, compilatori, semantica dei linguaggi e, più in generale, l’idea che la progettazione software abbia bisogno di modelli astratti precisi.

Materiali relativi al corso e al manuale

Collegamenti

Cronologia: per il contesto biografico e istituzionale, si veda Il mio percorso nella ricerca.