Parte 1 - dmi.unipg.it · Problema della fattorizzazione ... dei numeri interi o reali ... in...
Transcript of Parte 1 - dmi.unipg.it · Problema della fattorizzazione ... dei numeri interi o reali ... in...
Parte 1
Introduzione alla programmazionee 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● grafica tridimensionale● video giochi
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
programmi
Fasi della programmazione
Requisiti (descrizione del
compito
Algoritmo
Programma
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● può svolgere operazioni non elementari eseguendo
programmi
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
● OUTPUT: elenco dei risultati e descrizione della relazione con i dati
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 chiamati problemi decisionali
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 fattorizzazione, so anche se n è primo
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 non matematico
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 introduce troppi dettagli che sono inutili per la comprensione dell'algoritmo
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 divisore di a e b”
Diagrammi di flusso
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● rombo, che ne ha due, una con “Sì”, una con “No”
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
● Si termina quando si arriva a FINE
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● l'algoritmo termina perché a=b e restituisce 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 inglese, ecc.
Esempio di pseudo-codice
Inizio
Leggi a,b
Mentre a ≠ b
Ripeti
Se a>b Allora
a ← a-b
Altrimenti
b ← b-a
Fine-se
Fine-Ripeti
Scrivi a
Fine
Esempio di pseudo-codice in inglese
Begin
Read a,b
While a ≠ b
Repeat
If a>b Then
a ← a-b
Else
b ← b-a
End-If
End-Repeat
Write a
End
Istruzioni dello pseudo-codice
● Inizio e Fine● Leggi e Scrivi● Operazioni elementari (assegnamento), …● Se … Allora … Altrimenti … Fine-se● Mentre...Ripeti...Fine-ripeti
Istruzione Se● L'istruzione Se ha la forma
Se C Allora S1Altrimenti S2Fine-se
● in cui C è una condizione e S1,S2 sono sequenze di istruzioni
● Se la condizione C è vera, esegui S1; se è falsa esegui S2
Istruzione Se
● L'istruzione Se è equivalente al seguente diagramma di flusso
Istruzione Mentre
● Ha la formaMentre CRipeti SFine-ripeti
● C è una condizione e S una sequenza di istruzioni
● Esegui S ripetutamente fino a che C non diventa falsa
Istruzione Mentre● L'istruzione Mentre è equivalente al seguente
diagramma di flusso
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 varie parti
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 dobegin if a>b then a:=a-b else
b:=b-a end; writeln('il MCD e'' ',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#) il GOTO non esiste
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
possibile riscrivere un diagramma di flusso in modo da rispettare queste condizioni
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 flusso strutturati
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 dei dati in ingresso
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
a sarà uguale a b
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● spazio occupato in memoria
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 in ingresso e maggiore sia la quantità di R utilizzata
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 pesare in modo diverso
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 caso peggiore (worst-case analysis)
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 al numero n di elementi di S
Esempio● Analizziamo il seguente algoritmo
InizioLeggi Smax←estrai(S)Mentre ancora(S)Ripeti
elem←estrai(S)Se elem>max Allora
max←elemFine-se
Fine-ripetiScrivi max
Fine
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à l'elemento più grande di S
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 log2n+15 n,
l'ordine di infinito è O(n2)
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
(registri, ALU, ecc.)
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
● E' difficile ragionare in modo astratto se si deve lavorare così a basso livello
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 rilevanza nell'ambito dell'informatica
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 agli oggetti (C++, Java, C#, ecc.)
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 è compilato e interpretato insieme
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 processore senza far più ricorso al sorgente
Compilazione
sorgente Compilatore eseguibile
input Processore
output
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 Fetch-Decode-Execute
Interpretazione
sorgente
input
Interprete output
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
molto tempo● I linguaggi compilati di solito sono molto “rigidi”, almeno
sulla gestione dei tipi di dato, ad esempio le variabili devono essere dichiarate e hanno un tipo fissato
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
esecuzione
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● assegnamento
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, allocazione, visibilità) saranno viste in seguito
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 }● s3= { a=11, b=11, c=11 }● s4= { a=11, b=11, c=10 }
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 ed in genere dipende dallo stato corrente
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 }
● nello stato s2= { a=2, b=1, c=0 } l'esecuzione produce lo stato s4= { a=1, b=1, c=0 }