Appunti di Programmazione + Lab

Programmazione + Lab.

Prof.ssa A. Lanza

Appunti di Programmazione su: principali paradigmi di

programmazione, rappresentazione di algoritmi, strutture dati

principali, cenni di programmazione strutturata, problem

solving e grammatiche. Inoltre sono presenti gli algoritmi

fondamentali di ordinamento e di ricerca.

Alessandro Corcelli

A.A. 2011/2012

Indice

Programmazione ________________________________________________________________ 5

Paradigma di Programmazione ________________________________________________________ 5

Modello della computazione ___________________________________________________________ 5

Paradigmi __________________________________________________________________________ 5

Linguaggio Imperativo ______________________________________________________________________ 5

Paradigma procedurale ______________________________________________________________________ 6

Paradigma ad oggetti ________________________________________________________________________ 6

–

Information Hiding Incapsulamento ___________________________________________________ 6

Ereditarietà _________________________________________________________________________ 6

Paradigmi non procedurali (EUCIP) ____________________________________________________ 7

Problem Solvying ____________________________________________________________________ 7

Problema _________________________________________________________________________________ 7

Problem-Solver ____________________________________________________________________________ 7

Dal problema all’algoritmo (COSA) ____________________________________________________________ 8

Algoritmo ________________________________________________________________________________ 8

Rappresentazione dell’algoritmo ___________________________________________________ 9

Diagramma di flusso (flow-chart) _______________________________________________________ 9

Vantaggi ________________________________________________________________________________ 10

Svantaggi ________________________________________________________________________________ 10

Linguaggio testuale _________________________________________________________________ 10

Teorema di Boehm-Jacopini __________________________________________________________ 11

Programmazione Strutturata _____________________________________________________ 11

Modalità di approccio a problemi complessi _____________________________________________ 12

Spaghetti Programming ______________________________________________________________ 12

Programma ________________________________________________________________________ 12

Dall’algoritmo al programma ________________________________________________________________ 12

Albero di decomposizione ___________________________________________________________________ 12

Dati _________________________________________________________________________ 13

Variabile __________________________________________________________________________ 14

Costante ___________________________________________________________________________ 14

Utilità di dichiarazione di tipo ________________________________________________________________ 14

Tipo T __________________________________________________________________________________ 14

Conversioni numeriche ______________________________________________________________ 14

Conversioni tra stringhe e numeri _____________________________________________________ 15

Tipo dei reali _______________________________________________________________________ 15

Tipo definito dall’utente _____________________________________________________________ 15

Classi Involucro ____________________________________________________________________ 15

Auto-Boxing _____________________________________________________________________________ 16

Traduzione ____________________________________________________________________ 16

Tipi di Istruzione ___________________________________________________________________ 16

Traduttore _________________________________________________________________________ 16

Caricamento _______________________________________________________________________ 17

Compilatori ________________________________________________________________________ 17

Fasi di compilazione _________________________________________________________________ 17

Grammatiche e linguaggi ________________________________________________________ 17

Grammatica _______________________________________________________________________ 17

Alfabeto dei simboli terminali ________________________________________________________________ 18

Alfabeto di simboli non terminali _____________________________________________________________ 18

Regole sintattiche _________________________________________________________________________ 18

Simbolo iniziale __________________________________________________________________________ 18

BNF (Backus Naur Form) ____________________________________________________________ 18

Carte sintattiche ____________________________________________________________________ 19

Algoritmi elementari ____________________________________________________________ 20

Algoritmo di scambio ________________________________________________________________ 20

Media fra due valori _________________________________________________________________ 21

Minimo fra due valori _______________________________________________________________ 21

Minimo fra tre valori ________________________________________________________________ 21

Valore assoluto _____________________________________________________________________ 21

Somma di n valori __________________________________________________________________ 21

Algoritmi di conteggio _______________________________________________________________ 22

Minimo e massimo fra n numeri _______________________________________________________ 22

Inversione di cifre ___________________________________________________________________ 22

Ordinamento fra 3 stringhe ___________________________________________________________ 22

Istruzioni di controllo della esecuzione _____________________________________________ 22

Enunciati-Statement-Istruzioni________________________________________________________ 23

Selezione binaria: costrutto if-esle _____________________________________________________ 23

Selezione Multipla: costrutto switch ____________________________________________________ 23

Istruzioni iterative __________________________________________________________________ 23

Leading Decision: _________________________________________________________________________ 23

Trailing Decision __________________________________________________________________________ 24

Interruzione del flusso _______________________________________________________________ 24

Gli array ______________________________________________________________________ 24

Tipi di dati strutturati _______________________________________________________________ 24

Meccanismi/Modalità di strutturazione _________________________________________________ 25

Trasformazione finita _______________________________________________________________ 25

Caratteristiche degli array ___________________________________________________________ 25

Sconfinamento (Out of Bound) ________________________________________________________ 25

Matrici ____________________________________________________________________________ 25

Array paralleli _____________________________________________________________________ 26

Accesso generale agli array (For each) __________________________________________________ 26

Copiare un array ___________________________________________________________________ 26

Aggiunta di un elemento centrale _____________________________________________________________ 27

Eliminazione di un elemento centrale __________________________________________________________ 27

Ingrandire un array ________________________________________________________________________ 27

Algoritmi su Array _____________________________________________________________ 27

Algoritmi di base ___________________________________________________________________ 27

Inversione _______________________________________________________________________________ 27

Rimozione dei Duplicati ____________________________________________________________________ 28

Algoritmi di supporto _______________________________________________________________ 28

Ordinamento _____________________________________________________________________________ 28

Ordinamento interno ________________________________________________________________ 29

Per selezione (Selection-Sort) ________________________________________________________________ 29

Per scambio (Bubble-Sort) __________________________________________________________________ 30

Bubble Sort per Sedimentazione ______________________________________________________________ 30

Per Inserzione (carte da gioco) _______________________________________________________________ 30

Ordinamento Esterno _______________________________________________________________ 31

Quick Sort (Partizionamento) ________________________________________________________________ 31

Merge Sort _______________________________________________________________________________ 32

Ordinamento per fusioni successive ___________________________________________________________ 32

Merge __________________________________________________________________________________ 33

Ricerca (Search) ____________________________________________________________________ 34

Ricerca sequenziale ________________________________________________________________________ 34

Ricerca Binaria ___________________________________________________________________________ 34

Ricorsione ____________________________________________________________________ 35

Ricorsione Lineare __________________________________________________________________ 35

Ricorsione Mutua ___________________________________________________________________ 36

Ricorsione non Lineare ______________________________________________________________ 36

Astrazioni funzionali ____________________________________________________________ 36

Sottoprogramma ___________________________________________________________________ 37

Nidificazione di sottoprogrammi _____________________________________________________________ 37

Chiamata del sottoprogramma _______________________________________________________________ 37

Parametri _________________________________________________________________________ 37

In genere un sottoprogramma prevede dei parametri di input. Distinguiamo: _________________ 38

 Parametri attuali _______________________________________________________________ 38

 Parametri formali ______________________________________________________________ 38

Parametri attuali __________________________________________________________________________ 38

Parametri formali _________________________________________________________________________ 38

Passaggio dei parametri _____________________________________________________________________ 38

Visibilità ______________________________________________________________________ 38

Tipo di variabili accessibili ___________________________________________________________ 38

Regole di visibilità __________________________________________________________________ 38

Shadowing-Occlusione _______________________________________________________________ 39

Spazi di immagazzinamento ______________________________________________________ 39

Stack _____________________________________________________________________________ 39

Heap ______________________________________________________________________________ 40

Spazio di immagazzinamento statico ___________________________________________________ 40

Spazio di immagazzinamento costante __________________________________________________ 40

Immagazzinamento non in RAM ______________________________________________________ 40

Modello di esecuzione ___________________________________________________________ 40

Esecuzione dei metodi _______________________________________________________________ 40

Catena statica ______________________________________________________________________ 41

Catena dinamica ____________________________________________________________________ 41

Gestione degli oggetti ________________________________________________________________ 41

Programmazione

Il programmatore è un codificatore, cioè è in grado di trasformare l’esigenza di

un problema in un programma. Programmatore

Astrazione

Dominare la complessità

concentrandosi su un

aspetto/problema senza dettagli

Oggetti (dati)

Azioni (Istruzioni) –

Operazioni di controllo

Paradigma di Programmazione

Un paradigma di programmazione è un modello concettuale che struttura il

pensiero nel formare programmi validi. E’ uno stile di programmazione, ovvero

l’insieme degli strumenti concettuali forniti da un linguaggio per la stesura di

programmi, e definisce il modo in cui il programmatore concepisce e

percepisce il programma.

Modello della computazione

Il modello della computazione prevede flussi di istruzioni eseguite con logica

sequenziale, tranne laddove l’ordine di esecuzione sia esplicitamente dichiarato

(ad. es. nelle istruzioni di salto).

Paradigmi

Esistono numerosi paradigmi di programmazione:

 Imperativo

 Ad oggetti

 Procedurali

 Non procedurali

Linguaggio Imperativo

Un programma viene inteso come un insieme di istruzioni (direttive o

comandi), ciascuna delle quali può essere pensata come un "ordine" che viene

impartito alla macchina virtuale del linguaggio di programmazione utilizzato.

Da un punto di vista sintattico, i costrutti di un linguaggio imperativo sono

spesso identificati da verbi all'imperativo.

 Si ritrovano le caratteristiche essenziali dell’architettura di Von Neumann,

che consiste in due parti: la memoria (passiva) e il processore (attiva).

 La principale attività del processore è assegnare valori a celle di

memoria.

 Le variabili vengono viste come astrazioni di celle di memoria che

vengono modificate con delle istruzioni di assegnamento.

 I programmi sono realizzati sia attraverso interpretazione che

compilazione.

 Nati più per la manipolazione numerica che simbolica.

Esempi di linguaggi imperativi (strutturati e non): Basic, Fortran, PL/1,

Modula2 ecc...

Paradigma procedurale

La programmazione procedurale è un paradigma di programmazione che

consiste nel creare dei blocchi di codice, identificati da un nome e racchiusi da

dei delimitatori, che variano a seconda del linguaggio di programmazione;

questi sono detti anche sottoprogrammi (in inglese subroutine). Questi blocchi

possono assumere i nomi di procedure o funzioni, a seconda del linguaggio e

dei loro ruoli all'interno del linguaggio stesso.

Paradigma ad oggetti

La programmazione orientata agli oggetti (OOP) è un paradigma di

programmazione che permette di definire oggetti software (entità) in grado di

interagire gli uni con gli altri attraverso lo scambio di messaggi. È

particolarmente adatta nei contesti in cui si possono definire delle relazioni di

interdipendenza tra i concetti da modellare (contenimento, uso,

specializzazione).

I dati sono le entità su cui operano i metodi, cioè le operazioni da eseguire.

Information Hiding – Incapsulamento

L’incapsulamento è la tecnica di nascondere il funzionamento interno - deciso

in fase di progetto - di una parte di un programma, in modo da proteggere le

altre parti del programma dai cambiamenti che si produrrebbero in esse nel

caso che questo funzionamento fosse difettoso, oppure si decidesse di

implementarlo in modo diverso.

Ereditarietà

L’ereditarietà consiste in un legame che il linguaggio di programmazione, o il

programmatore stesso, stabilisce tra due tipi. Se la classe B eredita dalla

classe A, si dice che B è una sottoclasse di A e che A è una superclasse di B.

Procedurale Object Oriented

Si cerca una procedura che svolga il Si cerca un oggetto in una classe

compito di interesse e la si invoca. che include la funzione di interesse.

Se non esiste tale procedura, il Se non esiste tale classe, bisogna

programmatore deve scriverla. crearla.

Paradigmi non procedurali (EUCIP)

Caratteristiche:

 Manipolazione di simboli, non di numeri.

 La programmazione è esplorativa ed incrementale (prototipi veloci)

 Il linguaggio deve essere ad altissimo livello: utilizzabile anche da non-

programmatori.

Classificazione:

 Relazionali: l'algebra relazionale, in quanto linguaggio procedurale, può

necessitare di più passaggi per arrivare a un risultato; il linguaggio SQL,

non procedurale permette, con un singolo comando, di ottenere il

risultato atteso.

 Logici:

De