Giorgio Gambosi
Dipartimento di Matematica
Centro di Ricerca e Formazione Permanente per l’Insegnamento delle Discipline Scientifiche
Università di Roma “Tor Vergata”
11 aprile 20231
Sono convinto che l'informatica abbia molto in comune con la fisica. Entrambe si occupano di come funziona il mondo a un livello abbastanza fondamentale. La differenza, naturalmente, è che mentre in fisica devi capire come è fatto il mondo, in informatica sei tu a crearlo. Dentro i confini del computer, sei tu il creatore. Controlli -- almeno potenzialmente -- tutto ciò che vi succede. Se sei abbastanza bravo, puoi essere un dio. Su piccola scala.
Linus Torvalds
L’informatica ha a che fare con i computer non più di quanto l’astronomia abbia a che fare con i telescopi.
Edsger W. Dijkstra
11 aprile 20232
Problemi di immagine dell’informatica
11 aprile 20233
Disciplina culturalmente povera rispetto a “hard sciences” lo stesso avviene per scienze rispetto a materie
umanistiche tecnologia, non scienza informatica come programmazione assenza (irrilevanza) di fondamenti concettuali modello “garage programming”
Problemi di immagine
11 aprile 20234
Informatico = nerd, “smanettone” Non è una professione “di successo” Problema comune con le altre discipline
scientifiche scienziato = secchione
Grande fatica, scarso ritorno Fondamenti poco importanti
L’informatica nella scuola
11 aprile 20235
Apprendimento strumentale: informatica = computer Scuola media: utilizzo strumenti Scuola secondaria superiore: al massimo,
programmazione In generale, informatica vista come
funzionale ad altre discipline Produzione documenti, presentazioni, piccoli
programmi di simulazione, fogli elettronici
L’informatica nella scuola
11 aprile 20236
Riforma Gelmini Informatica soltanto nel Liceo scientifico,
opzione scienze applicate Impostazione tecnologica del programma
Scarso appeal della matematica
11 aprile 20237
Materia difficile Scarso stimolo concettuale per gli studenti Non sembra avere applicazioni
immediatamente significative
Test PISA, TIMSS, INVALSI
11 aprile 20238
Insufficienti risultati a partire dalla scuola media (K8)
Soprattutto relativamente alle competenze e agli aspetti procedurali e di problem solving
Difficoltà di descrizione dei procedimenti di soluzione
La matematica insegnata sembra troppo poco attenta agli aspetti di applicazione delle conoscenze ed alla risoluzione (algoritmica) di problemi
Cosa fare?
11 aprile 20239
Come valorizzare l’informatica? Come rendere più gratificante la matematica?
Sinergie: i concetti e i metodi fondamentali dell’informatica sono utili nell’insegnamento della matematica (e non solo)
Come rendere più gratificante la matematica?
11 aprile 202310
Maggiore attenzione all’utilizzo di metodi e concetti Modellazione matematica Computazione Risoluzione di problemi
Pensare in modo computazionale
Come valorizzare l’informatica?
11 aprile 202311
Combattere idee sbagliate Dare una definizione chiara della disciplina
Come corpus concettuale fondamentale Rilevanza sull’acquisizione di un modo di
pensare (rispetto a competenze specifiche)
Idee sbagliate
11 aprile 202312
CS = programmazione CS = alfabetizzazione informatica (es.
ECDL) CS = strumento per lo studio di altre
discipline CS = non disciplina scientifica CS = per maschi
Come valorizzare l’informatica?
11 aprile 202313
Informatica intesa come disciplina inerente: La modellizzazione La rappresentazione e la gestione
dell’informazione La risoluzione procedurale di problemi La programmazione ha un ruolo del tutto
ancillare
Come valorizzare l’informatica?
11 aprile 202314
Distinzione tra informatica e computer Avvicinamento all’informatica non
incentrato su computer Unplugged CS Presto: scuola elementare, scuola media Presenza “trasversale” (ad es. relazioni con
linguistica)
Come valorizzare l’informatica?
11 aprile 202315
Programmazione come formalizzazione di una procedura algoritmica Utilizzo di ambienti di programmazione di tipo
“educational” Storytelling (Alice, Scratch)
Test e verifica di correttezza come “sfida mentale”
Concetti chiave
11 aprile 202316
Informazione, codifica e organizzazione Algoritmi e loro implementazione Astrazioni concettuali Correttezza di una procedura Efficienza
Ruolo dei docenti
11 aprile 202317
Formazione insegnanti fondamentale Percezione sbagliata della CS trasmessa da
docenti a studenti Studenti validi orientati verso altri corsi di studio
Chi insegna cosa? Ruolo dei laureati in informatica e in ingegneria
informatica
Cosa fare?
11 aprile 202318
Presenza della comunità accademica per la definizione di programmi e obiettivi (non solo per informatica)
Collaborazione scuola-università Non finalizzata alle sole immatricolazioni
Iniziative nazionali (olimpiadi informatica)
Lauree scientifiche
Matematica
11 aprile 202319
Definisce un linguaggio Esprime situazioni e problemi reali in un
formalismo rigoroso (modelli) definisce proprietà che risultano in possibili
modalità di risoluzioni dei problemi
Rimane una questione aperta
11 aprile 202320
quanto è effettivamente praticabile risolvere un problema?
quanto devo calcolare?
Praticabile: quante risorse di calcolo mi servono?
Tempo: il tempo è una risorsa
Risolubilità effettiva di problemi. Esempio: TSP
11 aprile 202321
110 province in Italia, per ogni coppia tempo stimato di trasferimento
Voglio partire da Roma e tornare a Roma attraverso tutti i capoluoghi nel minor tempo possibile
Soluzione semplice: prova tutti i percorsi e scegli il più veloce
percorso=permutazione dei rimanenti 109 capoluoghi
Risolubilità effettiva di problemi. Esempio: TSP
11 aprile 202322
sono 109! permutazioni, circa 1.45x10^176 permutazioni
supponiamo di poter esaminare un percorso al minuto: servono circa 3x10^160 miliardi di anni!
Idea! Potrei usare un computer! un percorso ogni miliardesimo di secondo
servono circa 5x10^150 miliardi di anni
Cosa fare?
11 aprile 202323
Devo trovare un modo più efficiente di risolvere il problema
Ma esiste un modo più efficiente? Magari esiste un modo efficiente per
trovare un percorso molto vicino al migliore, ma non proprio quello
Questioni
11 aprile 202324
Dato un problema: Quanto efficientemente è possibile risolverlo? In che modo? Possiamo trovare modi efficienti per risolverlo
“più o meno”? Come descriviamo il problema e le sue
soluzioni? Come descriviamo il modo di risolverlo? E’ possibile, in assoluto, risolvere il problema in
generale?
Obiettivi dell’informatica
11 aprile 202325
soluzione efficiente di problemi mediante procedure generali
rappresentazione efficiente dell’informazione
Algoritmi
11 aprile 202326
Sequenze di istruzioni elementari (modello di calcolo) di composizione
Modelli di calcolo istruzioni possibili loro significato in termini di esecuzione
Algoritmi
11 aprile 202327
Linguistica: Algoritmi come testi di lunghezza finita Eseguibili da un agente (modello di calcolo):
esecuzione potenzialmente infinita Generalità della soluzione
funzionano su input diversi (calcolano una funzione) input ammissibili codifica (ancora linguistica)
Problema e algoritmo
11 aprile 202328
Problema: Insieme input ammissibili Output definito da funzione dell’input
Soluzione algoritmica
Input ammissibile
Output richiesto
Algoritmo
Tipi di problemi
11 aprile 202329
P1 input, J,K interi output J^2+3K problema aritmetico, esecuzione di durata
costante (sotto qualche ipotesi)
Tipi di problemi
11 aprile 202330
P2 input K intero output somma dei primi K interi aritmetico, la durata dell’esecuzione dipende
dall’input
Tipi di problemi
11 aprile 202331
P3 input K intero output “Y” se K è primo, “N” se composto problema di decisione, output non numerico
Tipi di problemi
11 aprile 202332
P4 Insieme di N parole Le N parole in ordine alfabetico non numerico
Tipi di problemi
11 aprile 202333
P5 input due testi output parole comuni non numerico
Tipi di problemi
11 aprile 202334
P6 input carta stradale, 2 città output descrizione tragitto più breve tra le due
città problema di ottimizzazione, input strutturato
Tipi di problemi
11 aprile 202335
P7 input carta stradale, N città, K intero output “Y” se esiste un percorso tra tutte le città
di lunghezza al più K, “N” altrimenti problema di ottimizzazione visto come problema
di decisione
Tipi di problemi
11 aprile 202336
P8 input, posizione degli scacchi output “Y” se esiste una sequenza di mosse per
il bianco che gli fa vincere la partita, “N” altrimenti
problema di decisione relativo ad un gioco
Tipi di problemi
11 aprile 202337
P9 input programma P, 2 variabili X (di input), Y, K
intero output 2K se P pone sempre Y=X^2, 3k
altrimenti riguarda il comportamento di un programma
“osservato”
Tipi di problemi
11 aprile 202338
decisionali di ricerca di ottimizzazione In molti casi difficile enunciare esattamente
output difficile: scacchi: come definire la mossa migliore
input complesso: problema di distribuzione (20000 giornali, 1000 rivenditori, 100 città, 50 furgoni) insieme dei costi, funzione di costo
previsioni del tempo (input?, output?): codifica di input e output
Risolubilità
11 aprile 202339
Problema risolubile se esiste un algoritmo che deriva l’output corretto per ogni input ammissibiledipendenza dal modello di calcolo
Problema trattabile se è risolubile ed esiste un algoritmo che lo risolve in modo efficiente (? Da definire)
I computer
11 aprile 202340
Sono una implementazione di un particolare modello di calcolo
Implementazione realizzata per mezzo di circuiti elettronici
Modello di calcolo molto semplice: sa fare poche cose elementari ==> è complicato descrivere un algoritmo per essere eseguito da questo modello di calcolo
Perché li usiamo? Perché l’implementazione elettronica del modello di calcolo fornisce operazioni molto veloci da eseguire
Linguaggi di programmazione
11 aprile 202341
Modelli di calcolo più articolati Implementazione realizzata mediante
software eseguito dal modello di calcolo del computer
Modello di calcolo più potente: sa fare a livello elementare più cose ==> è più semplice descrivere un algoritmo
Perché li usiamo? Sono un buon compromesso tra semplicità di descrizione di algoritmi e velocità di esecuzione
Comunicazione
11 aprile 202342
Definizione di algoritmi intesa come comunicazione
Destinatario: agente di calcolo, conosce la semantica, sa come eseguire i passi dell’algoritmo
Messaggio: descrizione dell’algoritmo, programma
Linguistica
11 aprile 202343
Algoritmi (e programmi) come frasi di un linguaggio
Sintassi: definisce cosa è corretto dal punto di vista di un insieme di regole di costruzione di “frasi”
Semantica: definisce il significato di una frase (in termini di esecuzione)
Modello di calcolo (linguaggio di programmazione): insieme delle frasi (programmi) corretti che posso scrivere
La macchina di Turing
11 aprile 202344
Modello di calcolo particolarmente semplice Nastro di memoria Testina di lettura/scrittura Stato interno Funzione di transizione
La macchina di Turing
11 aprile 202345
Esempio: un algoritmo di copia
La tesi di Church-Turing
11 aprile 202346
Un problema risolubile da un algoritmo su un qualche modello di calcolo è risolubile da una macchina di Turing
La macchina di Turing è il modello di calcolo più potente
Esistono modelli di calcolo meno potenti Automi a stati finiti
Algoritmi “sbagliati”
11 aprile 202347
Su qualche input, viene fornito un output scorretto
Potrei accettarlo, se succede raramente (valutazione probabilistica)
A volte, non termina mai
Un problema, tanti algoritmi
11 aprile 202348
Ricerca in un insieme Ricerca sequenziale:
quanti passi? tempo peggiore, tempo medio, tempo migliore
Ricerca a caso (1-1/n)^(k-1)1/n probabilità in k passi, media n
Ci potrei mettere di meno? No, come minimo li devo guardare
Un problema, tanti algoritmi
11 aprile 202349
Ricerca in un insieme Ipotesi aggiuntiva: insieme ordinato Ricerca binaria
tempo peggiore lg n Ci potrei mettere di meno? No (è possibile
mostrarlo)
Proporzionalità nella valutazione
11 aprile 202350
Consideriamo la proporzione tra il numero di passi (il tempo) e la dimensione dell’istanza di problema
Semplificazione: le istanze di stessa dimensione non richiedono lo stesso tempo Caso peggiore (caso medio)
Un problema, tanti algoritmi
11 aprile 202351
Ordinamento di un insieme Generazione permutazioni e verifica sequenza
ordinata n! permutazioni, circa (n/2.7)^n, per ognuna n passi per
verificare che sia ordinata Selezione/inserimento: n^2 Fusione: nlgn Ci potrei mettere di meno?
Sicuramente non meno di n (li devo guardare tutti): lower bound
Sicuramente non più di nlgn (ce la so fare, così): upper bound Gap di complessità: o abbasso l’u.b. (trovo algoritmi più
efficienti) o alzo il l.b. (faccio una analisi più precisa) Vale il secondo caso: mi serve almeno nlgn (se il mio
algoritmo è basato su confronti)
Un problema, tanti algoritmi
11 aprile 202352
Torri di Hanoi Soluzione iterativa: 2^n-1 mosse
ad esempio, n=30, una mossa al minuto, 2000 anni circa
Soluzione ricorsiva: 2^n-1 mosse Ci potrei mettere di meno? No (è stato mostrato) In effetti, l’output è lungo 2^n-1 (elenco delle
mosse)
1 secondo per mossa:
Un problema, tanti algoritmi
11 aprile 202353
Sistemi logici formali sull’aritmetica affermazioni del tipo “se P è vera allora Q è vera” P,Q proposizioni su interi 0,1 con = e +, oltre a
operatori logici (aritmetica di Presburger) ad esempio “se X=1 allora non esiste Y tale che X=Y+Y” P: “X=1” Q: “non esiste Y tale che X=Y+Y”
Problema: data una affermazione, stabilire se è vera
Qualunque algoritmo richiede tempo (numero di passi) almeno 2^2^n (n lunghezza dell’affermazione)
n=1 --> 4; 2 --> 16 ; 3 --> 256; 4 --> 65536; ...; 9 --> 1.3x10^154; 10 --> 1.8x10^308
Complessità esponenziale e polinomiale
11 aprile 202354
N=2 N=5 N=10 N=20 N=50 N=100 N=1000
N 2 s 5 s 10 s 20 s 50 s 2 m 17 m
N lgN 2 s 11 s 33 s 86 s 5 m 11 m 2h 45 m
N^2 4 s 25 s 1 m 40 s
6 m 41 m 2h 45 m
11 g
N^3 8 s 2 m 16 m 2 h 1.5 g 11 g 31 a
2^n 4 s 32 s 17 m 12 g 35 M anni
4x10^22 anni
3x10^293 anni
Età dell’universo: 14x10^9 anni
Complessità esponenziale e polinomiale
11 aprile 202355
La tecnologia aiuta poco
Aumenti della velocità di ordini di grandezza fanno diventaretrattabili istanze poco più grandi
Complessità esponenziale e polinomiale
11 aprile 202356
Identifichiamo trattabilità con tempo di soluzione polinomiale
Correlazione polinomiale tra modelli di calcolo (tesi di Church-Turing)
Limiti Costanti moltiplicative Grado elevato
Problemi polinomiali
11 aprile 202357
MCD Ricerca in un insieme Massimo in un insieme Ordinamento Ricerca in un labirinto Percorso minimo Ciclo euleriano 2-soddisfacibilità nel calcolo proposizionale …
Zona intermedia
11 aprile 202358
La classicazione dei problemi ha in realtà una zona grigia localizzata tra i problemi trattabili e quelli intrattabili
Sudoku Si procede per tentativi-errori-ritorno indietro
(backtrack)
Zona intermedia
11 aprile 202359
Tempo di soluzione esponenziale, al più 9^n (n è il numero di caselle vuote, n<=9x9)
Avendo N cifre, tabella di dimensioni NxN Al più N^(N^2)=2^(N^2*log N)
Per verificare se una possibile soluzione (assegnazione di interi a caselle) è corretta, basta tempo proporzionale a N
Trovare una soluzione sembra difficile Verificare una soluzione è semplice
Problemi verificabili
11 aprile 202360
Moltissimi problemi con le stesse caratteristiche Verificabili in tempo limitato (polinomiale)
Problemi di decisione Verifica effettuata su istanza + certificato
Certificato: informazione aggiuntiva, di lunghezza limitata (polinomiale)
Tipicamente, la soluzione stessa Algoritmo di verifica: esamina istanza +
certificato e stabilisce che l’istanza è positiva In tempo polinomiale
E se l’istanza è negativa?
Problemi verificabili
11 aprile 202361
Un problema risolubile in tempo polinomiale è anche verificabile in tempo polinomiale Certificato vuoto
P è l’insieme dei problemi risolubili in tempo polinomiale
NP è l’insieme dei problemi verificabili in tempo polinomiale
Esistono problemi in NP che non si sa risolvere in tempo polinomiale
Artù, Merlino e la tavola rotonda
11 aprile 202362
Artù: ha intelligenza limitata Merlino: infinitamente intelligente Tavola rotonda: ha N posti I cavalieri (N) non vogliono sedersi vicino ai loro
rivali E’ possibile disporre i cavalieri intorno alla
tavola? Difficile da risolvere: Merlino può farlo, Artù no Possibile: Merlino può convincere Artù (gli
mostra la soluzione) Non possibile: come può Merlino convincere
Artù?
Esempi di problemi NP
11 aprile 202363
Numero composto Isomorfismo tra grafi Colorazione di grafi Percorso hamiltoniano TSP 3 soddisfacibilità nel calcolo proposizionale Bisaccia Sequenziamento di attività Copertura di nodi Insieme indipendente …
Problemi NP
11 aprile 202364
Non sappiamo risolvere i problemi precedenti in modo efficiente (polinomiale)
Sono tutti verificabili in modo efficiente (polinomiale)
Per quasi tutti, non si sa verificare in modo efficiente il problema complementare (istanze positive e negative scambiate): eccezione, numero composto
Alcuni sono simili a problemi in P (2-SAT e 3-SAT, percorso euleriano e hamiltoniano)
Trasformazione di problemi
11 aprile 202365
Una istanza di un problema può essere trasformata in una istanza equivalente di un altro problema in modo efficiente (polinomiale)
Esempio:Copertura con nodi e Insieme indipendente In G=(V,E), un insieme S di nodi copre tutti gli archi
se e solo se V-S è un insieme indipendente Istanza di Insieme indipendente: G=(V,E), K Trasformata in istanza di Copertura con nodi:
G=(V,E), |V|-K Se so risolvere CN n modo efficiente posso
risolvere in modo efficiente II
Problemi NP-completi
11 aprile 202366
Esistono problemi per cui esistono trasformazioni efficienti delle istanze da qualunque problema NP
Se so risolvere in modo efficiente uno qualunque di questi problemi so risolvere tutti i problemi NP
Sono i problemi su cui conviene “concentrare” gli sforzi: se un problema NP-completo è in P, allora P=NP
I problemi citati sopra (eccetto i primi due) sono NP-completi
La questione P=NP?
11 aprile 202367
Il maggiore problema aperto in informatica Uno dei maggiori nell’intera matematica Se P=NP (improbabile), grandi
conseguenze pratiche Problemi di ottimizzazione intera Ricerca operativa: gestione risorse, logistica,
sequenziamento, allocazione risorse Biologia: struttura proteine Crittografia: indebolimento schemi
Problemi di ottimizzazione
11 aprile 202368
Sono sicuramente non più semplici dei corrispondenti problemi di decisione
Spesso, sono equivalenti (polinomialemente): se so risolvere efficientemente il problema di decisione, so risolvere efficientemente il problema di ottimizzazione
NP-completi NP-hard
Ma esistono sempre algoritmi di soluzione?
11 aprile 202369
Quanti sono gli algoritmi? Un algoritmo è descritto da una sequenza di simboli
da un alfabeto Può essere interpretato come codifica di un intero
(in una base opportuna) Gli algoritmi sono non più degli interi: infiniti
numerabili Quanti sono i problemi?
Consideriamo i soli problemi di decisione su interi Un problema è descritto da una sequenza infinita di
simboli 0,1 associati ai vari interi; ogni sequenza infinita corrisponde a un problema
I problemi sono almeno pari ai reali: infiniti non numerabili
Problemi senza algoritmi
11 aprile 202370
Dimostrazione più precisa per diagonalizzazione Esistono (infinitamente) più problemi che
algoritmi Esistono infiniti problemi non risolubili
Lo stesso argomento vale se consideriamo la descrizione di un problema Esistono infiniti problemi che non possono essere
descritti
“Ci sono più cose in cielo e terra, Orazio, di quante ne sogni la tua filosofia”, Amleto 1,5
Problemi non risolubili
11 aprile 202371
Problema della fermata Dato un programma P e un suo input X,
l’esecuzione di P su X si fermerà o continuerà indefinitamente? In generale, P eseguirà una qualche azione specifica
(restituirà un valore, porrà una variabile a un valore, etc.)?
Il problema non è risolubile in modo algoritmico Vale un argomento di auto-referenzialità:
Paradosso del mentitore Paradosso del barbiere
Teorema di incompletezza di Godel
Problema della fermata
11 aprile 202372
Termina(P,X) determina se P si ferma su input X
Paradosso(P) While (Termina(P,P));
Paradosso(P) termina se e solo se Termina(P,P) è falso; quindi solo se P non termina su input P
Paradosso(Paradosso) termina se e solo se Paradosso non termina su input Paradosso: contraddizione
Termina(P,X) non esiste
Altre tematiche interessanti
11 aprile 202373
Rappresentazione e gestione dell’informazione Codici di compressione e di correzione Teoria dell’informazione Strutture di dati
Linguistica Grammatiche generative Automi di riconoscimento Analisi lessicale e sintattica
Programmazione e linguaggi Paradigmi di programmazione