Giorgio Gambosi

Giorgio Gambosi

Dipartimento di Matematica

Centro di Ricerca e Formazione Permanente per l’Insegnamento delle Discipline Scientifiche

Università di Roma “Tor Vergata”

21 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

21 aprile 20232

Problemi di immagine dell’informatica

21 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

21 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

21 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

21 aprile 20236

Riforma Gelmini Informatica soltanto nel Liceo scientifico,

opzione scienze applicate Impostazione tecnologica del programma

Scarso appeal della matematica

21 aprile 20237

Materia difficile Scarso stimolo concettuale per gli studenti Non sembra avere applicazioni

immediatamente significative

Test PISA, TIMSS, INVALSI

21 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?

21 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?

21 aprile 202310

Maggiore attenzione all’utilizzo di metodi e concetti Modellazione matematica Computazione Risoluzione di problemi

Pensare in modo computazionale

Come valorizzare l’informatica?

21 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

21 aprile 202312

CS = programmazione CS = alfabetizzazione informatica (es.

ECDL) CS = strumento per lo studio di altre

discipline CS = non disciplina scientifica CS = per maschi


21 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


21 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)


21 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

21 aprile 202316

Informazione, codifica e organizzazione Algoritmi e loro implementazione Astrazioni concettuali Correttezza di una procedura Efficienza

Ruolo dei docenti

21 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?

21 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

21 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

21 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

21 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

21 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?

21 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

21 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

21 aprile 202325

soluzione efficiente di problemi mediante procedure generali

rappresentazione efficiente dell’informazione

Algoritmi

21 aprile 202326

Sequenze di istruzioni elementari (modello di calcolo) di composizione

Modelli di calcolo istruzioni possibili loro significato in termini di esecuzione

Algoritmi

21 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

21 aprile 202328

Problema: Insieme input ammissibili Output definito da funzione dell’input

Soluzione algoritmica

Input ammissibile

Output richiesto

Algoritmo

Tipi di problemi

21 aprile 202329

P1 input, J,K interi output J^2+3K problema aritmetico, esecuzione di durata

costante (sotto qualche ipotesi)

Tipi di problemi

21 aprile 202330

P2 input K intero output somma dei primi K interi aritmetico, la durata dell’esecuzione dipende

dall’input

Tipi di problemi

21 aprile 202331

P3 input K intero output “Y” se K è primo, “N” se composto problema di decisione, output non numerico

Tipi di problemi

21 aprile 202332

P4 Insieme di N parole Le N parole in ordine alfabetico non numerico

Tipi di problemi

21 aprile 202333

P5 input due testi output parole comuni non numerico

Tipi di problemi

21 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

21 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

21 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

21 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

21 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à

21 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

21 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

21 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

21 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

21 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

21 aprile 202344

Modello di calcolo particolarmente semplice Nastro di memoria Testina di lettura/scrittura Stato interno Funzione di transizione

La macchina di Turing

21 aprile 202345

Esempio: un algoritmo di copia

La tesi di Church-Turing

21 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”

21 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

21 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


21 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

21 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)


21 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)


21 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:


21 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

21 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


21 aprile 202355

La tecnologia aiuta poco

Aumenti della velocità di ordini di grandezza fanno diventaretrattabili istanze poco più grandi


21 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

21 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

21 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

21 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

21 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

21 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

21 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

21 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

21 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

21 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

21 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?

21 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

21 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?

21 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

21 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

21 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

21 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

21 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

Giorgio Gambosi

Documents

Transcript of Giorgio Gambosi