Programmazione

Marco Anisetti

Universita degli Studi di Milano,Dipartimento di Informatica

marco.anisetti@unimi.it

Marco Anisetti - 1 / 30

Obiettivi del corso

◮ Corso introduttivo alla programmazione, ai suoi principi ed alle suetecniche

◮ Nella sua carriera professionale un informatico potrebbe non aver maia che fare direttamente con la programmazione, ma la sua conoscenzae di fondamentale importanza dato che tutti gli strumenti con i qualiinteragira sono di fatto dei software

◮ Costituisce la differenza tra un utilizzatore del computer (seppurprofessionista) e un informatico

Marco Anisetti - 2 / 30

Nozioni di base

◮ Nozione di algoritmo

◮ Fasi della programmazione

◮ Strumenti di modellazione

◮ Linguaggi di programmazione

◮ ...

Marco Anisetti - 3 / 30

Programmazione elementare

◮ Rappresentazione di informazione numerica e simbolica

◮ La macchina MIX e il suo linguaggio assembly MIXAL

◮ Organizzazione dei dati: il concetto di variabile, mappa della memoriae tabelle, strutture dati dinamiche

◮ Alcune tecniche fondamentali di programmazione: sottoprogrammi,ricorsione, interpreti, automi

Marco Anisetti - 4 / 30

Programmazione strutturata

◮ Principi della programmazione strutturata

◮ Linguaggio C: espressioni e assegnamenti, costrutti di controllo, tipipredefiniti, vettori, matrici e stringhe, tipi strutturati, puntatori egestione della memoria, funzioni e passaggio di parametri, main eparametri al main, libreria standard, gestione dei file

◮ Eliminazione dei Salti: teorema di Bohm-Jacopini, trasformazione diAshcroft e Manna

◮ Fondamenti della programmazione ad oggetti: Java

La programmazione strutturata utilizzando il linguaggio C verra affrontata dal prof. Cordone

Marco Anisetti - 5 / 30

Materiale consigliato

◮ U. Moscato, M. Ornaghi. Algoritmi, programmi e linguaggi diprogrammazione. Citta Studi, Milano, 1990.

◮ D. E. Knuth. The Art of Computer Programming, vol. 1:Fundamental algorithms. Addison-Wesley, Reading (MA), 1997.

◮ N. Wirth. Principi di programmazione strutturata. ISEDI, Torino,1995.

◮ H.M. Deitel, P.J. Deitel, Corso completo di programmazione (secondaedizione). Apogeo, 2004

◮ Ravi Sethi. Programming Languages. Addison-Wesley 1996.

G. Pighizzini M. Ferrari. Dai fondamenti agli oggetti Corso di programmazione JAVA. Terza

Edizione Pearson Addison-Wesley Febbraio 2008

Marco Anisetti - 6 / 30

Modalita d’esame

Due prove obbligatorie:

◮ Scritto cartaceo con piu domande a risposta aperta su tutti gliargomenti del programma

◮ Esame di programmazione in linguaggio C che viene effettuato inpiattaforma (prof. Cordone)

Una prova facoltativa (+3 punti):

◮ Progetto di programmazione in linguaggio Java (da inviare 15 giorniprima della discussione)

◮ Orale in cui presentare e discutere il proprio progetto in linguaggioJava

Marco Anisetti - 7 / 30

Prefazione

◮ Due approcci possibili:◮ Idealistico: Presentare la materia gia organizzata alla luce dei moderni

sviluppi (OO, pattern, ecc.)◮ Evoluzionistico: Presentare la materia come evoluzione storica fino ad

arrivare ai suoi recenti sviluppi

◮ Si integra in un piano di studi che comprenda “Algoritmi e StruttureDati”, “Linguaggi di Programmazione” ed “Ingegneria del software”

Marco Anisetti - 8 / 30

Calcolatore e programma

◮ CalcolatoreUn automa il cui comportamento segue delle regole ben precise: e ingrado di “comprendere” un repertorio ristretto di istruzioni elementarie di eseguirle con una enorme rapidita ed elevata precisione

◮ ProgrammaSequenza di istruzioni elementari che un calcolatore e in grado dicomprendere ed eseguire

◮ ProgrammazioneAttivita che consiste nell’organizzare istruzioni elementari,direttamente comprensibili dall’esecutore, in strutture complesse(programmi) al fine di svolgere determinati compiti

Marco Anisetti - 9 / 30

Programmabilita

◮ Una macchina ha come compito sostituirsi o facilitare il lavoro umano

◮ E’ generalmente concepita per svolgere un solo lavoro

◮ Embrione della programmazione: attrezzi regolabili, permettono dicompiere una gamma di azioni maggiori (versatilita)

Marco Anisetti - 10 / 30

Programmazione

◮ Primo approccio: un modello di calcolatore diverso per ciascuno deicalcoli che erano di volta in volta richiesti

◮ C’e un motivo molto valido per cui molto presto si intraprese diprogettare dei calcolatori general purpose

◮ Al crescere della complessita degli elaboratori, il compito diprogrammarli inizio a superare in complessita addirittura il compito diprogettarli

Marco Anisetti - 11 / 30

Algoritmi

Algoritmo

Un algoritmo e sequenza finita di istruzioni che specificano come certeoperazioni elementari debbano susseguirsi nel tempo per risolvere una dataclasse di problemi.

◮ Operazioni elementari: operazioni note all’esecutore

◮ Istruzioni: richieste di azioni rivolte all’esecutore e che da questodevono essere capite ed eseguite

◮ Classe di problemi: una formulazione del problema indipendente daglispecifici dati su cui opera

Marco Anisetti - 12 / 30

Problema e Istanza(1)

[*] Prof. Andrea G. B. Tettamanzi

Marco Anisetti - 13 / 30

Problema e Istanza (2)

[*] Prof. Andrea G. B. Tettamanzi

Marco Anisetti - 14 / 30

Problema e Istanza (3)

[*] Prof. Andrea G. B. Tettamanzi

Marco Anisetti - 15 / 30

Problema Algoritmo Esecutore

Figura : Relazione problema algoritmo esecutore

Marco Anisetti - 16 / 30

Proprieta

◮ Oltre alle proprieta di eseguibilita e non ambiguita di un algoritmo,alcune altre proprieta fondamentali degli algoritmi sono:

◮ Correttezza: l’esecuzione dell’algoritmo porta realmente alla soluzionedel problema dato

◮ Efficienza: quanto “costa” l’esecuzione di un algoritmo in termini dirisorse consumate

◮ Finitezza: normalmente si richiede che l’algoritmo termini in un tempofinito, e cioe che la sequenza di istruzioni che caratterizzano l’algoritmosia una sequenza finita

Marco Anisetti - 17 / 30

L’algoritmo di Euclide

Massimo Comune Divisore fra due numeri x e y

1. Calcola il resto della divisione di x per y

2. Se il resto e diverso da zero, ricomincia dal punto 1 utilizzando come x ilvalore attuale di y , e come y il valore del restoaltrimentiprosegui con il passo successivo

3. Il massimo comune divisore e uguale al valore attuale di y

◮ L’intelligenza necessaria per trovare la soluzione del problema e tuttacodificata nell’algoritmo

◮ Chiunque sappia comprendere ed eseguire le operazioni checostituiscono l’algoritmo di Euclide, puo calcolare l’MCD

Marco Anisetti - 18 / 30

Controesempio

◮ Non tutto cio che sembra un una procedura passo passo e unalgoritmo

Dire se un numero e primo

1. N ← {0, 1}

2. per ogni coppia di interi i > 1 e j > 1, N ← N ∪ {i · j}

3. n e primo se e solo se n /∈ N

Ricordiamo che un numero naturale si dice primo se e divisibile solo per 1 e per se stesso, e che

per definizione 0 e 1 non sono primi

Marco Anisetti - 19 / 30

Algoritmi e programmi

◮ Un programma e l’espressione di un algoritmo in un linguaggio chel’esecutore e in grado di comprendere direttamente.

◮ Un programma e un’espressione concreta dell’algoritmo che ne el’astrazione

◮ A seconda dell’esecutore, lo stesso algoritmo puo essere espresso inlinguaggi differenti

◮ La scrittura del programma e la fase successiva all’individuazionedell’algoritmo per risolvere un determinato problema

Marco Anisetti - 20 / 30

Computabilita e Complessita

◮ Teoria della computabilita: utilizza modelli di calcolo come adesempio automi a stati, macchine di Turing ecc., per dimostrarel’esistenza o meno di algoritmi per una data classe di problemi

◮ Teoria della complessita: ha lo scopo di determinare le risorserichieste dall’esecuzione di un algoritmo per risolvere un datoproblema. Quello che importa realmente non e la quantita precisa dirisorse che esso richiede nel caso peggiore, ma il suo tasso di crescita,il suo ordine (logaritmico, lineare, quadratico, cubico, esponenziale,ecc.), al crescere delle dimensioni dell’ingresso

Marco Anisetti - 21 / 30

Modelli di computazione

◮ Per analizzare un algoritmo serve un modello della tecnologiautilizzata per realizzarlo:

◮ Descrive le risorse utilizzate◮ Descrive il loro costo

◮ Deve essere sufficientemente realistico

◮ Deve astrarre da dettagli di processori specifici

Marco Anisetti - 22 / 30

Modello di Macchina ad accesso casuale (RAM)(1)

◮ Il modello computazionale piu comunemente usato

◮ Modella fedelmente la stragrande maggioranza dei processori

◮ Istruzioni eseguite in sequenza

◮ Ogni istruzione richiede un suo tempo costante per l’esecuzione

Esistono altri modelli come le macchine basate su rete neurale, macchine quantistiche o macchine

chimiche astratte

Marco Anisetti - 23 / 30

Modello di Macchina ad accesso casuale (RAM)(2)

◮ Costituita da 4 componenti:◮ Memoria◮ Programma◮ File di input◮ File di output

◮ La memoria e costituita da una sequenza di locazioni 0, 1, . . . capacedi salvare un unico valore intero alla volta

◮ L’indirizzo e il numero della locazione di memoria

◮ l’intero riferito da un indirizzo di una locazione di memoria e ilcontenuto della locazione stessa

◮ Il programma e dato da una sequenza di istruzioni (assegnamenti,input/output, cicli di controllo)

Marco Anisetti - 24 / 30

Modello di Macchina ad accesso casuale (RAM) (3)

◮ assegnamento Mem[l ] := Mem[j ] +Mem[k]. Mette nella locazione l

la somma dei valori nella locazione j e k

◮ il file di input e una sequenza di valori consumati uno alla volta dauna istruzione di “read”

◮ il file di output e una sequenza di valori prodotti uno alla volta da unaistruzione di “write”

◮ il flusso di controllo del programma va normalmente da una istruzionealla successiva ad eccezione di istruzioni di “goto i” o gotocondizionati tipo if Mem[j ] ≥ 0 then goto i

Marco Anisetti - 25 / 30

Modello di Macchina ad accesso casuale (RAM): esempio(4)

1: Mem[0]:=02: read(Mem[1])3: if Mem[1]≥ 0 then goto 54: goto 75 Mem[3]:=Mem[0]-Mem[1]6: if Mem[3]≥ 0 then goto 167: write(Mem[1])8: read(Mem[2])9: Mem[3]:= Mem[2]-Mem[1]10: if Mem[3]≥ 0 then goto 1211: goto 1412: Mem[3]:=Mem[1]-Mem[2]13: if Mem[3]≥ 0 then goto 814: Mem[1]:=Mem[2] +Mem[0]15: goto 316: halt

Marco Anisetti - 26 / 30

Complessita (1)

◮ Trattata nel dettaglio nel corso di “Algoritmi e Strutture Dati”

◮ Si parla di complessita in termini di spazio e tempo

◮ Suddivisione in classi di complessita

1. Per analizzare un algoritmo serve un modello della tecnologia sullaquale verra realizzato (modelli astratti come la Macchina di Turing e laMacchina di Turing non deterministica o “con oracolo” ecc.)

2. Riduzione di un problema in un altro, o di un algoritmo per risolvere unproblema nell’algoritmo per risolverne un altro

Marco Anisetti - 27 / 30

Complessita (2)

◮ Riducibilita confrontare tra di loro le difficolta di due problemi e averificare se un algoritmo noto per risolverne uno possa esseresfruttato per risolvere anche l’altro (riducibilita polinomiale)

◮ Intrattabilita Problemi “facili” → complessita logaritmica o lineare;problemi considerati “trattabili” → complessita polinomiale, problemi“difficili” o “intrattabili”, la classe dei problemi NP-completi,polinomialmente riducibili a un problema “modello”; quantitaesponenziale di tempo di calcolo

◮ Indecidibilita problemi che non possono essere risolti in un tempofinito da alcun algoritmo, e quindi da alcun programma

Stabilire in modo algoritmico se, dato un programma ed i suoi dati di input, l’esecuzione del

programma con questi dati termina o no in un tempo finito non e calcolabile (cioe non ammette

un algoritmo) problema cosiddetto “dell’arresto” – indecidibilita

Marco Anisetti - 28 / 30

Problema dell’arresto: dimostrazione

◮ Supponiamo per assurdo che sia possibile scrivere un programma Tche accetti in ingresso la coppia < P , x >, formata da un qualsiasiprogramma P e dal suo ingresso x , e restituisca in uscita ⊤ , se P(x)termina in un tempo finito, e ⊥ altrimenti. Consideriamo ilprogramma P∗ che realizza il seguente algoritmo, per ogni ingresso x :

1. Esegui T sull’ingresso < P∗, x >;2. Se T restituisce ⊥, termina;3. Vai al Passo 1.

◮ Dimostriamo l’assurdo (dimostrazione tratta dalle dispense del prof.Tettamanzi) supponendo di eseguire T sull’ingresso < P∗, x >.1. T termina con valore di uscita ⊥; ma allora P∗ termina al Passo 2 e

quindi il risultato restituito da T ‘e scorretto;2. T termina con valore di uscita ⊤; ma allora P∗ non terminerebbe mai

al Passo 2 e continuerebbe a ciclare all’infinito: anche in questo caso ilrisultato restituito da T ‘e scorretto;

3. T non termina: anche in questo caso, ci‘o significherebbe che T nonfunziona come abbiamo supposto.

Marco Anisetti - 29 / 30

Complessita (3)

◮ Cio che importa veramente non e la quantita precisa di risorse, macome questa cresce al crescere della dimensione dell’ingresso

◮ O(logn) < O(n) < O(n2) < O(n3) < · · · < O(2n)

[*] Prof. Andrea G. B. Tettamanzi

Marco Anisetti - 30 / 30