Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per...
-
Upload
benigna-napolitano -
Category
Documents
-
view
214 -
download
0
Transcript of Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per...
![Page 1: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/1.jpg)
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
![Page 2: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/2.jpg)
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
![Page 3: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/3.jpg)
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”
![Page 4: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/4.jpg)
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
![Page 5: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/5.jpg)
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
![Page 6: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/6.jpg)
L’informatica nella scuola
11 aprile 20236
Riforma Gelmini Informatica soltanto nel Liceo scientifico,
opzione scienze applicate Impostazione tecnologica del programma
![Page 7: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/7.jpg)
Scarso appeal della matematica
11 aprile 20237
Materia difficile Scarso stimolo concettuale per gli studenti Non sembra avere applicazioni
immediatamente significative
![Page 8: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/8.jpg)
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
![Page 9: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/9.jpg)
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)
![Page 10: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/10.jpg)
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
![Page 11: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/11.jpg)
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)
![Page 12: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/12.jpg)
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
![Page 13: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/13.jpg)
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
![Page 14: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/14.jpg)
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)
![Page 15: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/15.jpg)
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”
![Page 16: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/16.jpg)
Concetti chiave
11 aprile 202316
Informazione, codifica e organizzazione Algoritmi e loro implementazione Astrazioni concettuali Correttezza di una procedura Efficienza
![Page 17: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/17.jpg)
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
![Page 18: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/18.jpg)
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
![Page 19: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/19.jpg)
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
![Page 20: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/20.jpg)
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
![Page 21: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/21.jpg)
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
![Page 22: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/22.jpg)
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
![Page 23: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/23.jpg)
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
![Page 24: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/24.jpg)
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?
![Page 25: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/25.jpg)
Obiettivi dell’informatica
11 aprile 202325
soluzione efficiente di problemi mediante procedure generali
rappresentazione efficiente dell’informazione
![Page 26: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/26.jpg)
Algoritmi
11 aprile 202326
Sequenze di istruzioni elementari (modello di calcolo) di composizione
Modelli di calcolo istruzioni possibili loro significato in termini di esecuzione
![Page 27: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/27.jpg)
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)
![Page 28: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/28.jpg)
Problema e algoritmo
11 aprile 202328
Problema: Insieme input ammissibili Output definito da funzione dell’input
Soluzione algoritmica
Input ammissibile
Output richiesto
Algoritmo
![Page 29: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/29.jpg)
Tipi di problemi
11 aprile 202329
P1 input, J,K interi output J^2+3K problema aritmetico, esecuzione di durata
costante (sotto qualche ipotesi)
![Page 30: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/30.jpg)
Tipi di problemi
11 aprile 202330
P2 input K intero output somma dei primi K interi aritmetico, la durata dell’esecuzione dipende
dall’input
![Page 31: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/31.jpg)
Tipi di problemi
11 aprile 202331
P3 input K intero output “Y” se K è primo, “N” se composto problema di decisione, output non numerico
![Page 32: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/32.jpg)
Tipi di problemi
11 aprile 202332
P4 Insieme di N parole Le N parole in ordine alfabetico non numerico
![Page 33: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/33.jpg)
Tipi di problemi
11 aprile 202333
P5 input due testi output parole comuni non numerico
![Page 34: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/34.jpg)
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
![Page 35: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/35.jpg)
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
![Page 36: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/36.jpg)
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
![Page 37: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/37.jpg)
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”
![Page 38: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/38.jpg)
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
![Page 39: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/39.jpg)
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)
![Page 40: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/40.jpg)
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
![Page 41: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/41.jpg)
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
![Page 42: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/42.jpg)
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
![Page 43: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/43.jpg)
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
![Page 44: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/44.jpg)
La macchina di Turing
11 aprile 202344
Modello di calcolo particolarmente semplice Nastro di memoria Testina di lettura/scrittura Stato interno Funzione di transizione
![Page 45: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/45.jpg)
La macchina di Turing
11 aprile 202345
Esempio: un algoritmo di copia
![Page 46: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/46.jpg)
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
![Page 47: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/47.jpg)
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
![Page 48: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/48.jpg)
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
![Page 49: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/49.jpg)
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)
![Page 50: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/50.jpg)
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)
![Page 51: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/51.jpg)
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)
![Page 52: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/52.jpg)
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:
![Page 53: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/53.jpg)
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
![Page 54: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/54.jpg)
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
![Page 55: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/55.jpg)
Complessità esponenziale e polinomiale
11 aprile 202355
La tecnologia aiuta poco
Aumenti della velocità di ordini di grandezza fanno diventaretrattabili istanze poco più grandi
![Page 56: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/56.jpg)
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
![Page 57: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/57.jpg)
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 …
![Page 58: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/58.jpg)
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)
![Page 59: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/59.jpg)
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
![Page 60: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/60.jpg)
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?
![Page 61: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/61.jpg)
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
![Page 62: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/62.jpg)
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ù?
![Page 63: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/63.jpg)
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 …
![Page 64: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/64.jpg)
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)
![Page 65: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/65.jpg)
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
![Page 66: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/66.jpg)
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
![Page 67: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/67.jpg)
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
![Page 68: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/68.jpg)
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
![Page 69: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/69.jpg)
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
![Page 70: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/70.jpg)
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
![Page 71: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/71.jpg)
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
![Page 72: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/72.jpg)
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
![Page 73: Giorgio Gambosi Dipartimento di Matematica Centro di Ricerca e Formazione Permanente per lInsegnamento delle Discipline Scientifiche Università di Roma.](https://reader035.fdocumenti.com/reader035/viewer/2022070312/5542eb4f497959361e8be7bc/html5/thumbnails/73.jpg)
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