Giorgio Gambosi
Dipartimento di Matematica
Centro di Ricerca e Formazione Permanente per
l’Insegnamento delle Discipline Scientifiche
Università di Roma “Tor Vergata”
1
19 dicembre 2015
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
2
19 dicembre 2015
Problemi di immagine dell’informatica
Disciplina culturalmente povera rispetto a “hard
sciences”






3
lo stesso avviene per scienze rispetto a materie umanistiche
tecnologia, non scienza
informatica come programmazione
assenza (irrilevanza) di fondamenti concettuali
modello “garage programming”
19 dicembre 2015
Problemi di immagine
Informatico = nerd, “smanettone”
Non è una professione “di successo”
Problema comune con le altre discipline scientifiche




scienziato = secchione
Grande fatica, scarso ritorno
Fondamenti poco importanti


4
19 dicembre 2015
L’informatica nella scuola
Apprendimento strumentale: informatica = computer



Scuola media: utilizzo strumenti
Scuola secondaria superiore: al massimo, programmazione
In generale, informatica vista come funzionale ad altre
discipline


5
Produzione documenti, presentazioni, piccoli programmi di
simulazione, fogli elettronici
19 dicembre 2015
L’informatica nella scuola
Riforma Gelmini



6
Informatica soltanto nel Liceo scientifico, opzione scienze
applicate
Impostazione tecnologica del programma
19 dicembre 2015
Scarso appeal della matematica
Materia difficile
Scarso stimolo concettuale per gli studenti
Non sembra avere applicazioni immediatamente
significative



7
19 dicembre 2015
Test PISA, TIMSS, INVALSI
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




8
19 dicembre 2015
Cosa fare?
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)

9
19 dicembre 2015

Maggiore attenzione all’utilizzo di metodi e concetti




Modellazione matematica
Computazione
Risoluzione di problemi
Pensare in modo computazionale
10
19 dicembre 2015
Come valorizzare l’informatica?


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)
11
19 dicembre 2015
Idee sbagliate





CS = programmazione
CS = alfabetizzazione informatica (es. ECDL)
CS = strumento per lo studio di altre discipline
CS = non disciplina scientifica
CS = per maschi
12
19 dicembre 2015
Come valorizzare l’informatica?

Informatica intesa come disciplina inerente:




13
La modellizzazione
La rappresentazione e la gestione dell’informazione
La risoluzione procedurale di problemi
La programmazione ha un ruolo del tutto ancillare
19 dicembre 2015
Come valorizzare l’informatica?


Distinzione tra informatica e computer
Avvicinamento all’informatica non incentrato su
computer



14
Unplugged CS
Presto: scuola elementare, scuola media
Presenza “trasversale” (ad es. relazioni con linguistica)
19 dicembre 2015
Come valorizzare l’informatica?

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”
15
19 dicembre 2015
Concetti chiave





Informazione, codifica e organizzazione
Algoritmi e loro implementazione
Astrazioni concettuali
Correttezza di una procedura
Efficienza
16
19 dicembre 2015
Ruolo dei docenti

Formazione insegnanti fondamentale



Percezione sbagliata della CS trasmessa da docenti a
studenti
Studenti validi orientati verso altri corsi di studio
Chi insegna cosa?

17
Ruolo dei laureati in informatica e in ingegneria informatica
19 dicembre 2015
Cosa fare?


Presenza della comunità accademica per la
definizione di programmi e obiettivi (non solo per
informatica)
Collaborazione scuola-università



18
Non finalizzata alle sole immatricolazioni
Iniziative nazionali (olimpiadi informatica)
Lauree scientifiche
19 dicembre 2015
Matematica

Definisce un linguaggio


19
Esprime situazioni e problemi reali in un formalismo
rigoroso (modelli)
definisce proprietà che risultano in possibili modalità di
risoluzioni dei problemi
19 dicembre 2015
Rimane una questione aperta




quanto è effettivamente praticabile risolvere un
problema?
quanto devo calcolare?
Praticabile: quante risorse di calcolo mi servono?
Tempo: il tempo è una risorsa
20
19 dicembre 2015
Risolubilità effettiva di problemi. Esempio:
TSP




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
21
19 dicembre 2015
Risolubilità effettiva di problemi. Esempio:
TSP




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
22
19 dicembre 2015
Cosa fare?



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
23
19 dicembre 2015
Questioni

Dato un problema:






24
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?
19 dicembre 2015
Obiettivi dell’informatica


soluzione efficiente di problemi mediante procedure
generali
rappresentazione efficiente dell’informazione
25
19 dicembre 2015
Algoritmi

Sequenze di istruzioni



elementari (modello di calcolo)
di composizione
Modelli di calcolo


26
istruzioni possibili
loro significato in termini di esecuzione
19 dicembre 2015
Algoritmi

Linguistica:



Algoritmi come testi di lunghezza finita
Eseguibili da un agente (modello di calcolo): esecuzione
potenzialmente infinita
Generalità della soluzione



27
funzionano su input diversi (calcolano una funzione)
input ammissibili
codifica (ancora linguistica)
19 dicembre 2015
Problema e algoritmo

Problema:



Insieme input ammissibili
Output definito da funzione dell’input
Soluzione algoritmica
Input
ammissibile
28
Algoritmo
Output
richiesto
19 dicembre 2015
Tipi di problemi

P1



29
input, J,K interi
output J^2+3K
problema aritmetico, esecuzione di durata costante (sotto
qualche ipotesi)
19 dicembre 2015
Tipi di problemi

P2



30
input K intero
output somma dei primi K interi
aritmetico, la durata dell’esecuzione dipende dall’input
19 dicembre 2015
Tipi di problemi

P3



31
input K intero
output “Y” se K è primo, “N” se composto
problema di decisione, output non numerico
19 dicembre 2015
Tipi di problemi

P4



32
Insieme di N parole
Le N parole in ordine alfabetico
non numerico
19 dicembre 2015
Tipi di problemi

P5



33
input due testi
output parole comuni
non numerico
19 dicembre 2015
Tipi di problemi

P6



34
input carta stradale, 2 città
output descrizione tragitto più breve tra le due città
problema di ottimizzazione, input strutturato
19 dicembre 2015
Tipi di problemi

P7



35
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
19 dicembre 2015
Tipi di problemi

P8



36
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
19 dicembre 2015
Tipi di problemi

P9



37
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”
19 dicembre 2015
Tipi di problemi




decisionali
di ricerca
di ottimizzazione
In molti casi difficile enunciare esattamente



38
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
19 dicembre 2015
Risolubilità


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)
39
19 dicembre 2015
I computer




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
40
19 dicembre 2015
Linguaggi di programmazione




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
41
19 dicembre 2015
Comunicazione



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
42
19 dicembre 2015
Linguistica




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
43
19 dicembre 2015
La macchina di Turing

Modello di calcolo particolarmente semplice




44
Nastro di memoria
Testina di lettura/scrittura
Stato interno
Funzione di transizione
19 dicembre 2015
La macchina di Turing

Esempio: un algoritmo di copia
45
19 dicembre 2015
La tesi di Church-Turing



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

46
Automi a stati finiti
19 dicembre 2015
Algoritmi “sbagliati”



Su qualche input, viene fornito un output scorretto
Potrei accettarlo, se succede raramente (valutazione
probabilistica)
A volte, non termina mai
47
19 dicembre 2015
Un problema, tanti algoritmi

Ricerca in un insieme

Ricerca sequenziale:


Ricerca a caso


48
quanti passi? tempo peggiore, tempo medio, tempo migliore
(1-1/n)^(k-1)1/n probabilità in k passi, media n
Ci potrei mettere di meno? No, come minimo li devo
guardare
19 dicembre 2015
Un problema, tanti algoritmi

Ricerca in un insieme


Ipotesi aggiuntiva: insieme ordinato
Ricerca binaria


49
tempo peggiore lg n
Ci potrei mettere di meno? No (è possibile mostrarlo)
19 dicembre 2015
Proporzionalità nella valutazione


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

50
Caso peggiore (caso medio)
19 dicembre 2015
Un problema, tanti algoritmi

Ordinamento di un insieme

Generazione permutazioni e verifica sequenza ordinata




Selezione/inserimento: n^2
Fusione: nlgn
Ci potrei mettere di meno?




51
n! permutazioni, circa (n/2.7)^n, per ognuna n passi per verificare che
sia ordinata
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)
19 dicembre 2015
Un problema, tanti algoritmi

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:


52
19 dicembre 2015
Un problema, tanti algoritmi

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
53
19 dicembre 2015
Complessità esponenziale e polinomiale
N=2
N=5
N=10
N=20
N=50
N=100
N=1000
N
2s
5s
10 s
20 s
50 s
2m
17 m
N lgN
2s
11 s
33 s
86 s
5m
11 m
2h 45 m
N^2
4s
25 s
1 m 40 s
6m
41 m
2h 45 m
11 g
N^3
8s
2m
16 m
2h
1.5 g
11 g
31 a
2^n
4s
32 s
17 m
12 g
35 M
anni
4x10^22
anni
3x10^293
anni
Età dell’universo: 14x10^9 anni
54
19 dicembre 2015
Complessità esponenziale e polinomiale

La tecnologia aiuta poco
Aumenti della velocità di ordini di grandezza fanno diventare
trattabili istanze poco più grandi
55
19 dicembre 2015
Complessità esponenziale e polinomiale



Identifichiamo trattabilità con tempo di soluzione
polinomiale
Correlazione polinomiale tra modelli di calcolo (tesi
di Church-Turing)
Limiti


56
Costanti moltiplicative
Grado elevato
19 dicembre 2015
Problemi polinomiali









MCD
Ricerca in un insieme
Massimo in un insieme
Ordinamento
Ricerca in un labirinto
Percorso minimo
Ciclo euleriano
2-soddisfacibilità nel calcolo proposizionale
…
57
19 dicembre 2015
Zona intermedia


La classicazione dei problemi ha in realtà una zona
grigia localizzata tra i problemi trattabili e quelli
intrattabili
Sudoku

58
Si procede per tentativi-errori-ritorno indietro (backtrack)
19 dicembre 2015
Zona intermedia


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
59
19 dicembre 2015
Problemi verificabili

Moltissimi problemi con le stesse caratteristiche



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


Verificabili in tempo limitato (polinomiale)
In tempo polinomiale
E se l’istanza è negativa?
60
19 dicembre 2015
Problemi verificabili

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
61
19 dicembre 2015
Artù, Merlino e la tavola rotonda








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ù?
62
19 dicembre 2015
Esempi di problemi NP











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
…
63
19 dicembre 2015
Problemi NP




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)
64
19 dicembre 2015
Trasformazione di problemi


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
65
19 dicembre 2015
Problemi NP-completi




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 NPcompleti
66
19 dicembre 2015
La questione P=NP?



Il maggiore problema aperto in informatica
Uno dei maggiori nell’intera matematica
Se P=NP (improbabile), grandi conseguenze pratiche




67
Problemi di ottimizzazione intera
Ricerca operativa: gestione risorse, logistica, sequenziamento,
allocazione risorse
Biologia: struttura proteine
Crittografia: indebolimento schemi
19 dicembre 2015
Problemi di ottimizzazione



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
68
19 dicembre 2015
Ma esistono sempre algoritmi di soluzione?

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?



69
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
19 dicembre 2015
Problemi senza algoritmi


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
70
19 dicembre 2015
Problemi non risolubili

Problema della fermata

Dato un programma P e un suo input X, l’esecuzione di P su
X si fermerà o continuerà indefinitamente?



Il problema non è risolubile in modo algoritmico
Vale un argomento di auto-referenzialità:



71
In generale, P eseguirà una qualche azione specifica (restituirà un
valore, porrà una variabile a un valore, etc.)?
Paradosso del mentitore
Paradosso del barbiere
Teorema di incompletezza di Godel
19 dicembre 2015
Problema della fermata


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
72
19 dicembre 2015
Altre tematiche interessanti

Rappresentazione e gestione dell’informazione




Linguistica




Codici di compressione e di correzione
Teoria dell’informazione
Strutture di dati
Grammatiche generative
Automi di riconoscimento
Analisi lessicale e sintattica
Programmazione e linguaggi

73
Paradigmi di programmazione
19 dicembre 2015