Prima parte degli appunti delle lezioni del corso di Programmazione I con laboratorio (A.A. 2011/12)

Parte 1

Introduzione alla programmazione e all'algoritmica

Programmazione

● La programmazione è la scienza che studia come

si programmano i computer

● La programmazione è importante perché un

computer, opportunamente programmato, può svolgere i compiti più disparati

● gestione di una centrale nucleare ● automazione ufficio

● controllo aereo

Definizione di programma

● Un programma è un procedimento (finito)

descritto in un linguaggio di programmazione mediante il quale un computer è in grado di svolgere un compito complesso

● Un computer

● sa svolgere operazioni elementari ● sa eseguire programmi

● può svolgere operazioni non elementari eseguendo

Fasi della programmazione

Algoritmo

● L'algoritmo è una generalizzazione del concetto

di programma

● Un algoritmo è infatti un procedimento finito che

consente ad un esecutore di svolgere un compito complesso

Esecutore

● Un esecutore può essere ● un essere umano

● un computer ● un robot

● un dispositivo programmabile ● Un esecutore

● sa svolgere operazioni elementari ● sa eseguire dei procedimenti

Esempi di algoritmi

● Algoritmi in senso lato possono essere ● ricette di cucina

● protocolli medici

● istruzioni per l'utilizzo di apparecchiature di vario

tipo

● metodi per lo svolgimento delle operazioni

aritmetiche (ad esempio come si addizionano due numeri interi)

Compito complesso

● I compiti complessi che possono essere svolti

da un computer sono compiti di elaborazione dati (calcolo di risultati a partire da dati)

● Sono chiamati anche problemi computazionali ● Sono descritti da

● INPUT: elenco di tutti i dati disponibili ed utili per il

calcolo

Esempio

● Il primo esempio è il calcolo del massimo

comun divisore

● INPUT a,b numeri naturali

● OUTPUT m numero naturale, il loro M.C.D. ● Ad esempio se

● a=14 e b=77, allora m è 7 ● a=14 e b=16, allora m è 2 ● a=14 e b=15, allora m è 1

Altri esempi

● Problema della primalità ● INPUT n, numero naturale

● OUTPUT

– “vero” se n è un numero primo

– “falso” se n non è un numero primo

● I problemi con output “vero”/”falso” sono

Altri esempi

● Problema della fattorizzazione ● INPUT n, numero naturale

● OUTPUT

– d, numero naturale, diverso da 1 e da n, che è un

divisore di n, oppure

– “fallimento” se n è un numero primo ● Si tratta di un problema di ricerca

● Ha come sotto-problema quello della primalità:

una volta risolto il problema della

Altri esempi

● Problema della ricerca su grafo

● INPUT: elenco di città e lunghezza delle strade di

collegamento tra le varie città due città s e d

● OUTPUT: il percorso più breve che porta da s a d ● Si tratta di un problema di ottimizzazione

Altri esempi

● Problema dell'ordinamento

● INPUT un elenco di n stringhe (ad esempio

cognome e nome)

● OUTPUT lo stesso elenco con gli elementi disposti

in un certo ordine (ad esempio in ordine alfabetico)

● Si tratta di un problema di elaborazione di tipo

Metodi per la descrizione degli

algoritmi

● Gli algoritmi possono essere descritti

● in linguaggio naturale, cioè a parole ● tramite diagrammi di flusso

● tramite lo pseudo-codice

● tramite un linguaggio di programmazione

● Si preferiscono descrizioni formali, anziché

informali (a parole)

● L'uso di un linguaggio di programmazione invece

Diagrammi di flusso

● Nella slide successiva vediamo un esempio di

diagramma di flusso: l'algoritmo di Euclide

● La descrizione a parole è “Dati due numeri

interi a e b, si sottragga il più piccolo al più grande dei due numeri tante volte fino a

quando i due numeri non diventano uguali. Il numero così ottenuto è il massimo comun

Elementi di un diagramma di flusso

● Quattro tipi di nodi

● ellissoidali: INIZIO e FINE

● parallelogrammi: istruzioni di ingresso (Leggi) e di

uscita (Scrivi)

● rettangoli: istruzioni elementari (assegnamento o

altre)

● rombi: punti di scelta, contengono una condizione

(che può essere vera o falsa)

● Ogni nodo ha una sola freccia uscente, tranne

● FINE, che non ne ha

Esecuzione di un diagramma di

flusso

● Si parte da INIZIO

● Si eseguono le operazioni indicate, nell'ordine

in cui si trovano

● Se si arriva ad un nodo rombo, si valuta la

condizione e a seconda del valore (vero/falso) si segue l'arco corrispondente

Esempio di esecuzione

● Se l'utente introduce i numeri 70 e 42 ● al primo passo a=70 e b=42

● al secondo passo a=70-42=28 e b=42 ● al terzo passo a=28 e b=42-28=14 ● al quarto passo a=28-14=14 e b=14

Pseudo-codice

● Si può ottenere uno pseudo-codice tramite una

semplificazione di un linguaggio di

programmazione (Pascal, C, ecc.), togliendo dettagli sintattici

● Anche se all'apparenza non esiste uno

standard conclamato, gli pseudo-codici sono tutti molto simili tra di loro

● Si possono avere pseudo-codici in italiano, in

Esempio di pseudo-codice

Esempio di pseudo-codice in

inglese

Istruzioni dello pseudo-codice

● Inizio e Fine ● Leggi e Scrivi

● Operazioni elementari (assegnamento), … ● Se … Allora … Altrimenti … Fine-se

Istruzione Se

● in cui C è una condizione e S1,S2 sono

sequenze di istruzioni

Istruzione Se

● L'istruzione Se è equivalente al seguente

Istruzione Mentre

● C è una condizione e S una sequenza di

istruzioni

● Esegui S ripetutamente fino a che C non

Istruzione Mentre

● L'istruzione Mentre è equivalente al seguente

Corrispondenza con i diagrammi di

flusso

● E' facile tradurre un algoritmo da

pseudo-codice a diagramma di flusso

● E' infatti sufficiente sostituire tutte le istruzioni

Se e Mentre con i diagrammi di flusso corrispondenti

● Poi è necessario collegare con delle frecce le

Traduzione da pseudo-codice a

programma

● Uno pseudo-codice può essere agevolmente

tradotto in un programma scritto in un linguaggio di programmazione moderno

● Ad esempio in Pascal serve poco più che tradurre

in inglese lo pseudo-codice ... ● Leggi diventa read

● Scrivi diventa write o writeln ● Se diventa if

● Mentre diventa while ● ...

Esempio in Pascal

program Euclide; var a,b: integer; begin write('inserisci a e b '); read(a,b); while a<>b do begin if a>b then a:=a-b else b:=b-a end;

Problemi con i diagrammi di flusso

● Non è altrettanto facile tradurre un diagramma

di flusso in un linguaggio di programmazione moderno

● Infatti in un diagramma di flusso (mal

strutturato) le frecce possono congiungere parti arbitrarie dell'algoritmo e l'istruzione che

permette un simile comportamento in un

programma (istruzione GOTO) non si usa più

● Addirittura nei linguaggi più moderni (Java, C#)

Diagrammi di flusso strutturati

● Un diagramma di flusso può essere tradotto

agevolmente solo se è scritto in modo strutturato

● Si devono solo usare

● sequenza, ovvero nodi collegati in sequenza lineare

● scelta, cioè il diagramma equivalente a “Se”

● iterazione, cioè il diagramma equivalente a “Mentre”

● Non si possono collegare tra di loro istruzioni arbitrarie ● Il Teorema di Jacopini-Bohm ci dice che è sempre

Diagramma di flusso e

pseudo-codice

● In sostanza invitiamo ad usare solo lo

pseudo-codice

● è più leggibile

● è facilmente traducibile in un linguaggio di

programmazione moderno

● è molto diffuso nella letteratura scientifica

● In alternativa si possono usare i diagrammi di

Proprietà degli algoritmi

● Eseguibilità: l'esecutore deve essere in grado

di eseguire l'algoritmo in modo autonomo

● Terminazione (o finitezza): l'algoritmo deve

sempre arrivare al termine

● Correttezza: l'algoritmo deve sempre fornire la

risposta giusta

● “sempre” significa per qualsiasi valore legale

Terminazione dell'algoritmo di

Euclide

● A titolo di esempio analizziamo l'algoritmo di

Euclide

● Termina sempre perché

● ad ogni passo a e b diminuiscono ed anche la loro

differenza diminuisce sempre

● poiché la differenza è comunque un numero intero,

non può diminuire un numero infinito di volte

● quindi prima o poi la differenza diventerà 0, ovvero

Correttezza

● L'algoritmo è corretto perché ad ogni passo a e

b cambiano ma resta invariato il loro MCD

● Questa proprietà può essere dimostrata

matematicamente

● Dato che alla fine a=b, il MCD, sia degli ultimi

valori di a e b, sia di quelli di partenza, è a (oppure b)

Efficienza

● Un'ulteriore proprietà auspicabile per un

algoritmo è l'efficienza

● Un algoritmo dovrebbe utilizzare, durante la

sua esecuzione, la quantità minima possibile di risorse di calcolo

● Le risorse più importanti sono ● tempo di esecuzione

Analisi del costo di un algoritmo

● Data una risorsa R, si studia la quantità di R

consumata dall'algoritmo in funzione della grandezza n di dati in ingresso

● cioè il numero di cifre (in base 2 o altra base) per

dei numeri interi o reali

● ovvero il numero di componenti di vettori, insiemi o

collezioni di vario tipo

● Si presuppone infatti che più sono grandi i dati

Costo temporale

● Per tempo di calcolo non si può intendere il tempo

di esecuzione in secondi

● avrebbe senso solo studiando il comportamento di un

programma in un computer reale

● Invece possiamo contare il numero di istruzioni

eseguite

● unico conteggio (tutte le istruzioni considerati alla pari) ● più conteggi distinti per classi di istruzioni (ad esempio

num. di addizioni e sottrazioni e num. di moltiplicazioni e divisioni)

● unico conteggio in cui però le istruzioni possono

Caso peggiore

● Se il numero di istruzioni eseguite non dipende

solo da n, ma anche dal valore dei dati in ingresso, si adotta una visione pessimistica

● Si contano infatti le istruzioni nel peggior caso

possibile tra tutti quelli che hanno grandezza n

● La funzione così ottenuta si chiama costo nel

Esempio

● Sia data una collezione S di numeri interi,

vogliamo trovare l'elemento più grande di S

● Supponiamo che

● i numeri siano tutti più o meno della stessa

grandezza

● l'esecutore possa usare le seguenti operazioni – estrai(S), estrae da S ogni volta un elemento diverso

– ancora(S), controlla se ci sono in S elementi non ancora

estratti

● Vogliamo studiare il seguente algoritmo rispetto

Esempio

● Analizziamo il seguente algoritmo

Inizio Leggi S max←estrai(S) Mentre ancora(S) Ripeti elem←estrai(S) Se elem>max Allora max←elem Fine-se Fine-ripeti

Correttezza e completezza

● L'algoritmo termina quando tutti gli elementi

sono stati estratti da S

● L'algoritmo è corretto perchè max, sia prima del

ciclo “Mentre”, sia alla fine di ogni sua

iterazione, contiene il valore più alto fino ad allora estratto

● Quindi all'uscita del ciclo “Mentre” conterrà

Conteggi

● Numero di confronti: n-1

● Numero di assegnamenti nel caso peggiore:

1+(n-1)+(n-1)=2n-1

● Numero di esecuzioni di estrai: n-1 ● Numero di esecuzioni di ancora: n-1

Risultato finale

● Sono tutti polinomi di primo grado in n

● Il numero di operazioni è quindi O(n)

● Con O(n) si intende dire, in parole povere (e non

proprio esattamente) che il vero numero di operazioni, quando n tende ad infinito, ha lo stesso comportamento della funzione f(n)=n

● O(n) è l'ordine di infinito del numero delle

operazioni: è l'informazione normalmente riportata per quanto riguarda il costo di un algoritmo

Ordine di infinito

● Per ottenere l'ordine di infinito

● si eliminano tutti gli addendi di grado inferiore,

comprese le costanti

● si eliminano i coefficienti

● Ad esempio se il costo è n2+3n log

2n+15 n,

Programmazione

● E' possibile programmare veramente un

computer solo in linguaggio macchina

● E' l'unico linguaggio conosciuto dal processore ● Le istruzioni di un linguaggio macchina

● sono codificate in forma numerica

● sono stabilite in modo immutabile in sede di

progettazione della CPU

● dipendono fortemente dai dettagli interni della CPU

Difficoltà del linguaggio macchina

● Programmare in linguaggio macchina (L.M.) è

molto difficile

● L'ostacolo maggiore è la la mancanza di

astrazione

● Infatti ogni istruzione, in ogni suo dettaglio,

dipende fortemente dall'organizzazione interna del computer

Mancanza di portabilità

● La forte dipendenza dal hardware rende

impossibile usare un programma scritto in L.M. per un certo processore in un processore

diverso

● Quindi il L.M. non è portabile

● Conviene quasi sempre riscrivere da zero un

programma quando lo si vuole eseguire in un processore diverso

Programmazione ad alto livello

● Per ovviare a questi problemi sono stati ideati i

linguaggi di programmazione ad alto livello

● Per eseguire un programma scritto in un tale

linguaggio c'è bisogno di tradurlo in L.M.

● Esistono un numero impressionante di

linguaggi di programmazione

● Pochi linguaggi però hanno avuto una certa

Linguaggi di programmazione

● Tra i linguaggi di programmazione più famosi

citiamo Fortran, COBOL, Lisp, Algol, PL/I,

Basic, Pascal, C, Prolog, Ada, C++, Java, C#

● Alcuni di questi linguaggi sono orientati ad

alcuni tipi di applicazioni, ad esempio il Fortran per le applicazioni numeriche

● Altri sono invece “general-purpose”, ossia

vanno (più o meno) bene per qualsiasi tipo di applicazione, ad esempio il C

Paradigmi

● I linguaggi possono essere classificati in tre

grandi categorie (paradigmi)

● imperativi, le istruzioni sono comandi da eseguire ● funzionali, le istruzioni sono espressioni da valutare ● logici, le istruzioni sono interrogazioni a cui

rispondere

● Inoltre molti linguaggi moderni sono orientati

Traduzione

● L'esecuzione di un programma scritto in un

linguaggio di programmazione necessita di una traduzione in L.M.

● Esistono due forme base di traduzione:

compilazione e interpretazione

● Molti linguaggi usano un unico modo di

traduzione: ad esempio Python è interpretato, il C è compilato

● Si possono inoltre combinare insieme: il Java è

Compilazione

● Nella compilazione la traduzione è svolta

interamente prima dell'esecuzione

● A partire dal sorgente il compilatore produce un

nuovo programma, detto eseguibile, che

● è equivalente al sorgente ● è scritto in L.M.

● L'eseguibile può essere eseguito dal

Compilazione

sorgente _Compilatore eseguibile

input Processore

Interpretazione

● Nell'interpretazione, traduzione ed esecuzione

sono svolte insieme

● L'interprete traduce ed esegue direttamente le

istruzioni del sorgente una per volta

● Svolge una sorta di ciclo

Interpretazione

sorgente

input

Interpretazione e compilazione

● Le due tecniche sono molto diverse ● Pro della compilazione

● la traduzione è fatta una sola volta, l'eseguibile può essere

eseguito tante volte senza ogni volta compilare il sorgente

● l'eseguibile è scritto in L.M. bene, spesso meglio di come

l'avrebbe scritto un programmatore esperto

● l'esecuzione quindi è molto veloce ed efficiente

● Contro

● Mancanza di immediatezza: la traduzione può richiedere

Interpretazione e compilazione

● Pro dell'interpretazione

● l'esecuzione inizia subito

● si può usare in ambienti interattivi, ad esempio comandi

immediati

● I linguaggi interpretati sono più liberi, ad esempio

spesso non si dichiarano le variabili

● Contro

● L'esecuzione è di gran lunga più lenta, dovendo tenere

conto della traduzione

● Il codice eseguito più volte è (spesso) tradotto più volte ● La maggiore flessibilità si paga con la minore velocità di

Concetti di base della

programmazione imperativa

● Prima di iniziare lo studio di alcuni linguaggi di

programmazione (Python e C) vediamo alcuni dei concetti di base della programmazione

imperativa

● variabile

● espressione ● istruzione

Variabile

● Le variabili sono un concetto cardine nei

linguaggi di programmazione imperativi

● La variabile è contraddistinta da un nome e

possiede un valore che può essere cambiato solo con l'operazione di assegnamento

● Altre caratteristiche delle variabili (tipo,

Stato

● L'insieme di tutte le variabili “utilizzabili” in un

dato momento insieme con i rispettivi valori si chiama stato

● Ad esempio alcuni stati possibili con le variabili

a,b,c sono

● s1= { a=4, b=5, c=-3 } ● s2= { a=2, b=1, c=0 }

Espressione

● Un'espressione è costituita da ● costanti (ad esempio numeri) ● variabili

● operatori (ad esempio +, -, *, ...) ● funzioni (ad esempio log, exp, …)

● Un'espressione denota un valore che deve

essere calcolato (tramite la valutazione dell'espressione)

● Tale valore si chiama risultato dell'espressione

Espressione

● Ad esempio nello stato s1= { a=4, b=5, c=-3 } ● l'espressione a+2 vale 6

● l'espressione a*b-2 vale 18 ● l'espressione a*(b+c) vale 8

● Invece nello stato s2= { a=2, b=1, c=0 } ● l'espressione a+2 vale 4

● l'espressione a*b-2 vale 0 ● l'espressione a*(b+c) vale 2

Istruzione

● Un'istruzione è un'operazione che cambia lo

stato o che interagisce con il mondo esterno

● Esplicitamente non produce un risultato diretto,

come invece è prodotto dalle espressioni

● Si distinguono

● istruzioni elementari

● istruzioni composte, le quali sono formate

componendo tra di loro istruzioni elementari e composte

Assegnamento

● L'istruzione elementare per eccellenza è

l'assegnamento

● Ha la forma variabile←espressione

● Cambia lo stato attribuendo alla variabile il valore che in

quel preciso momento assume l'espressione

● Ad esempio

● nello stato s1= { a=4, b=5, c=-3 } l'esecuzione di

a=b+c produce lo stato s3= { a=2, b=5, c=-3 }