Informatica II

Algoritmi

Algoritmo = procedura computazionale ben definita che, dato un input, produce un output attraverso una serie finita di azioni.

L'algoritmo e i dati sono strettamente legati.

L'algoritmo deve dare in tempo limitato un risultato certo, unico e ripetibile, quindi deve essere non ambiguo, finito e le azioni devono essere eseguibili e descritte con un livello di dettaglio che dipende dal esecutore (es. linguaggio di programmazione universale tradotto da un compilatore in codice macchina).

• Linguaggi per la descrizione di algoritmi
• Grafi di flusso (flow-charts)

È uno pseudolinguaggio che utilizza simboli grafici per descrivere istruzioni e ordine di esecuzione tra esse, che riprendendo le schede perforate su cui negli anni '60 era scritto il programma.

Istruzioni

• Nome - istruzione di lettura (leggere un unico dato, un numero intero) e assegnarlo il suo valore a una variabile "nome"
• Nome - istruzione di scrittura (scrivere in uscita il valore della variabile denominata "nome")
• Nome := arith - istruzione di assegnazione (calcola il valore della espr. aritm. e assegna il valore risultante alla variabile "nome")
• Se condizione - istruzione di test (calcola il valore della espr. booleana, se la risposta è vera segui il ramo V, altrimenti il ramo F)
• Stop - istruzione di stop (fermare)

La lettura e l'assegnazione sono variabili di istruzione e di azione, le altre sono di controllo poiché definiscono solo l'ordine.

Ci sono 3 strutture di controllo:

• Sequenza: definisce ordine sequenziale
• Selezione: scelta tra 2 alternative

Iterazione

Il loop è una sequenza ciclica di istruzioni contenente almeno una istruzione che modifica la condizione del ciclo, necessaria per evitare un loop infinito.

Pseudocodifica

È un linguaggio naturale e più formale che utilizza uno pseudocodice cioè un linguaggio di programmazione fittizio per rappresentare l'algoritmo senza scendere in dettaglio su un particolare linguaggio di programmazione.

temp <- a (il contenuto di a è assegnato a temp) unica istruzione operativa

Sequenza

beginend

Selezione

if condizione then istruzione1 (blocco)else (blocco)istruzione2 (blocco)

Iterazione

While condizione do (istruzione) (blocco)

for ind <- inf to sup do (istruzione) (blocco)

Foreach elemento insieme do (istruzione) (blocco)

Problema

Dato A insieme di n elementi, generare un nuovo insieme A con elementi originali divisi dal massimo di A.

Algoritmo

1. Cerca il massimo di A
2. Costruisci il nuovo insieme A

Per rendere l'algoritmo maggiormente eseguibile lo scorporo in moduli (sottoprogrammi)

3) ITERAZIONE

SE I_1 è complessa devo spezzare una sequenza

• WHILE expr bool ⟹ ⟹
• REPEAT I_2 UNTIL expr bool ⟹⟹
• FOR tecnico variabile contatore expr inizio ⟹ expr fine ⟹

MODULI

• Moduli sono programmi a sé che svolgono una particolare istruzione. Possono essere riusati nello stesso programma o in programmi diversi e sono più troccoli.
• FUNCTION è un modulo che restituisce un singolo valore semplice.

PROPRIETÀ FORMALI

• (valore dei parametri nel codice del modulo)

ESEMPLO: traduci in Pascal l'algoritmo

1. Leggi l'insieme delle osservazioni.
2. Calcola la somma (risolto con il modulo peso intorno alla foglia)
3. Calcola la somma (risolto con il seguente FUNCTION SOMMA)

INFORMAZIONE DI

Variabili Dinamiche

Una variabile si definisce statica quando è dichiarata in una "var" ed è indicata tramite identificatore.

Var indica un insieme di record si intende, si crea un indirizzo di memoria fisso (record) durante tutto il programma per poi essere utilizzato. Le variabili possono essere sparce o smalturate. A questo utente si riservano indirizzi di memoria contigui che rappresentano la memoria stack dell'area/record.

Dyn

Una variabile si definisce dinamica se è di tipo puntatore (p) ovvero se contiene indirizzi di memoria di celle dove possono essere immagazzinati dati o tipi associati (t) allo specifico tipo della variabile.

1. New indica un indirizzo di memoria
2. L'indirizzo viene dato in C++ (allocazione) new (carico di ciò che si fa)
3. Ced -> Modificazione indiretta
4. Accesso al primo indiretto -> Indirizzamento indiretto

Le variabili dinamiche (da) hanno un nome proprio ma è legato al suo puntatore, qualunque tipo di tributo che da il suo utente che non conosce l’indirizzo di da

La quantità di memoria usata non viene direttamente copolazione alla quantità in funzione d'una allocazione a quel punto (assegn' memoria * variabili punt)

Quando a non riesci al chiam la funzione dispos 1- Rilascia un'indirizzo all'interno o a torimno il recupero 2- Insura il valido dipendente nell'indirizzo di Quindi il tempo di via o di varia dinamica e di da -> chiamata new -> chiamata disposa.

OSS

NB: Si associa normalmente dal momento a b finché non ce il valore di a = b.

a,b sono puntatori; da1, da2 sono le variabili dinamiche, quindi a=b ≠ a=da [fatto]

Considero come dato astratto l'insieme su V= [S, F, I, C]

• S= insiemi booleani
• F= test insieme vuoto, insieme cardinalità, test appartenenza
• C= insieme vuoto

Specifica sintattica

TIPO I su V, boolean

Operazioni:

• Test insieme vuoto ins → boolean
• Insieme ins x V → ins
• Cancella ins x V → ins
• Test appartenenza ins x V → boolean

Costanti: insieme vuoto, cioè insieme in cui I = {elementi}

Specifica semantica

I insieme rel

Test insieme vuoto ( I ) =

• true, se I non ha elementi
• false, altrimenti

• I ⊆ S e I ⊆ T
• I union {a}, se a ∉ I
• I \ {a}, se a ∈ I

Implementazione

1. In Pascal: la primitiva set (vedi) una chiave visibile, non presenta relazioni espressive, ma nasconde, per cui si utilizza un'altra realizzazione.
2. Si può utilizzare il vettore caratteristico: quando un insieme in corrispondenza di conquartino...

In Pascal:

Type: insieme = array[1..5] of boolean

Function test insieme vuoto (vector:: insieme) :boolean;

Procedure inserisci (val pos vector: insieme);

Procedure cancella (val pos vector: insieme);

Function test appartenenza;

Osserviamo che:

• Se devo cancellare l'ultimo elemento basta modificare il valore di "lunghezza".
• La lista vuota es il valore del campo "primo" = 0.
• "La prima" operazione è difficile applicare C.A.S.
• Non vi sono punti rigidi quindi all'interno dell'array posso fare di tutto.

La rappresentazione contiene:

• n + 1 componenti (n = array > lunghezza della lista).

La rappresentazione è efficiente se cancellazioni o inserimenti non vengono in posizione ovvi dal primo, in quanto è necessario spostare il contenuto dell'array.

• Considerando le lunghezze si possono avere spazi notevoli poiché la dimensione dell'array è fissa ovvero indipendente dalla lunghezza della lista.

C. Rappresentazione collegata

In questa rappresentazione gli elementi dell'array sono memorizzati associando ad ognuno un riferimento alla posizione dell'elemento seguente.

• Mediante puntatori

Ogni elemento di una lista è rappresentato da un record con un campo X e i riferimenti a X, in questo un altro puntatore è effetto, mediante una variabile di tipo puntatore.

Type Lista = record (elemento: Integer; next: Lista; end;)

Voglio collegare S all'ultimo elemento della lista cosa devo fare?

1. Creo la mia struttura minima inizializzando la lista.
2. Applico l'operatore cons(X, L) più volte creando la lista voluta con, in fondo, la mia sentinella S.