Che materia stai cercando?

Riassunto esame Fondamenti di informatica, prof. Vittorini, libro consigliato Fondamenti di Informatica, Fadini Savy

Riassunto per l'esame di Fondamenti di Informatica [/b, basato su appunti personali e studio autonomo del testo consigliato dal docente Fondamenti di Informatica, Fadini Savy .
Sintesi fondamentale per comprendere i vari approcci teorici e pratici all'informatica, il calcolo automatico e l'elaborazione elettronica in cui si prendono in considerazione... Vedi di più

Esame di Fondamenti di informatica docente Prof. V. Vittorini

Anteprima

ESTRATTO DOCUMENTO

preciso modello di Specifica scritto in un certo Linguaggio con cui confrontarlo: ma qui sorgerebbero, iterativamente,

problemi di verifica della Correttezza della descrizione della Specifica, non portando quindi a nulla di produttivo.

Dunque, prescindendo dalle effettive difficoltà di ordine pratico per la sua dimostrazione, e in relazione alla definizione

generale di Specifica (come data nella parte II, Cap. IV, par.1), la Correttezza può essere così definita:<<un programma

P è "parzialmente corretto" se realizza la funzione U=F(I) con I appartenente alle Precondizioni sui dati iniziali e U alle

Postcondizioni sui dati finali; P è inoltre "totalmente corretto" se è possibile dimostrare che è "parzialmente corretto" e

che Termina>>.

Capitolo ottavo = La complessità computazionale

1. Problemi, algoritmi e programmi

La questione della Complessità dei problemi e dell'Efficienza di algoritmi e programmi (Complessità Computazionale)

va esaminata considerando i seguenti aspetti:

- ogni problema X per il quale si scrive un programma ha una sua Complessità Intrinseca (dove per Complessità

indicheremo un indice del numero di operazioni elementari che lo compongono).

- ogni algoritmo A con il quale si tenta di risolvere X è caratterizzato da una propria Efficienza (dipendente dalla bontà

del procedimento usato e dalle risorse effettivamente messe a disposizione dalla piattaforma dove esso sarà compilato

come Programma).

- ogni programma P derivato dall'algoritmo A ha, al pari di quest'ultimo, una propria Efficienza (dipendente da fattori

come l'ambiente di esecuzione e dalle risorse disponibili in quel momento sulla Macchina in uso).

E' comunque scontato che una Maggiore Compessità di X implica parimenti una maggiore Complessità di sviluppo di

A e P, ma senza dubbio se A ha una buona Efficacia anche P la eredita ed è più efficace di un programma analogo basato

su un algoritmo più rudimentale.

2. Efficienza dei programmi

L'Efficienza di un programma va definita sulla base di:

- spazio S di Memoria occupato dal programma e dai dati.

- il tempo T necessario all'esecuzione del programma.

E in generale dipende da fattori come:

- la Mole dei Dati in Ingresso.

- efficienza del Traduttore e Tempo di Esecuzione di ogni Istruzione.

- efficienza del Software di Sistema.

La molteplicità di questi fattori non consente di definire in assoluto l'Efficienza di un Programma, ma solo l'Efficienza

Relativa di questo rispetto ad altri programmi che girano sulla stessa Macchina nelle stesse condizioni: l'Efficienza è

dunque funzione di S e di T, laddove - si noti - per programmi funzionalmente equivalenti all'aumentare di S diminuisce T

e viceversa (cioè le due variabili sono in un certo senso interdipendenti).

Si può definire "costo" del programma la sommatoria dei tempi di esecuzione delle sue istruzioni (opportunamente

n

radunate per classe, in base alla complessità) dipendenti ovviamente dalla dimensione dei dati passati al programma in

Input.

3. Ordine di una funzione

n O(f(n))

Un funzione "t(n)" con intero positivo si scrive come e si dice che ha ordine "f(n)" se e solo si ha:

ν

|t(n)| a|f(n)| n> a

per ogni fissato ed costante

Ω (f(n))

Si dice poi che la funzione è se si ha: ν

|t(n)| c|f(n)| n> c

per ogni fissato ed costante

Nel primo caso quindi si individua una delimitazione superiore della funzione, nel secondo una delimitazione inferiore,

n

per avere chiaro entro quale serie di valori (massimi e minimi al variare di "che tende a + ") la funzione

"t(n)"considerata si muove.

4. Costo di un algoritmo e complessità asintotica

Per valutare la Complessità di un algoritmo bisogna individuare, anche con approssimazione, la "funzione costo"

chiamata "t(n)": per esempio si può assegnare ad ogni istruzione semplice (Assegnazione, Confronto, Calcolo) un "costo

unitario" ignorando, per semplicità, altre istruzioni come la Chiamata di funzione, anche se Ricorsiva.

Se si arriva a verificare che: ν

=

|t(n)| c|f(n)| n> c

per ogni fissato ed costante

allora "f(n)" viene detta "funzione di complessità" ed indica una stima del tempo necessario ed effettivo di esecuzione per

n abbastanza grande, diciamo tendente a + : per questo la funzione costo "t(n)" è chiamata anche "complessità

asintotica" dell'algoritmo.

Per valutare il costo come descritto, occorre procedere, anche sommariamente, al conteggio delle istruzioni necessarie

per elaborare un numero standard di dati, e a questo scopo si opererà come segue:

- se l'algoritmo è decomponibile in una sequenza di parti ciascuna con una sua complessità, quella dell'algoritmo è la

massima tra queste.

- se l'algoritmo prevede più cicli innestati la complessità è definita dal numero di istruzioni del ciclo più interno, detta

"istruzione dominante".

Ovviamente, e anche questo va considerato, esistono delle "configurazioni" dei dati di ingresso che possono

n

determinare, a parità di , un costo diverso dell'algoritmo: distingueremo il Caso Peggiore (per esempio, in una funzione

di ordinamento, una lista controordinata), il Caso Migliore (una lista già ordinata) e il Caso Medio (in termini di

probabilità, la media aritmetica di tutti gli altri casi possibili).

5. Delimitazione superiore della complessità di un algoritmo

O(f(n)) t(n)

Si dice che un algoritmo ha "complessità asintotica" se nel Caso Peggiore la funzione costo ha ordine

O(f(n)) f(n)

(naturalmente siamo interessati a trovare, tra le tante funzioni che verificano questa proprietà quella

"minima").

6. Delimitazione inferiore della complessità di un problema Ω (g(n)) t(n)

Un problema ha una "delimitazione inferiore" della complessità se la funzione costo di un qualsiasi

Ω (g(n)),

algoritmo che lo risolva è cioè definisce la "complessità intrinseca" del problema (naturalmente siamo

g(n)

interessati a trovare, tra le tante funzioni che verificano questa proprietà quella "massima").

O(f(n))

Si deduce quindi che: un algoritmo è "ottimale" per un problema se la sua complessità è pari alla "complessità

Ω (g(n))

intrinseca" del problema.

7. Funzioni di complessità

Le funzioni di complessità alle quali si perviene prendendo in esame gli algoritmi più comuni sono:

logn nlogn

- funzioni logaritmiche, nella forma oppure .

n

- funzioni polinomiali, nella forma ^k con k intera e positiva.

n

.

- funzioni esponenziali, nella forma k^ n

E' inutile dire che tra queste le funzioni esponenziali, al crescere di , determinano tempi di esecuzione proibitivi, e al

diminuire del tempo di esecuzione delle istruzioni (magari per l'uso di processori più potenti) producono un aumento

dell'efficienza molto modesto rispetto alle altre: per questo - anche se ciò è arbitrario - esse vengono definite "non

trattabili" in contrapposizione alle altre dette invece "trattabili".

PARTE SECONDA = FONDAMENTI DI PROGRAMMAZIONE

Capitolo primo = Introduzione alla programmazione ed ai linguaggi.

1. Elaborazione dei dati e calcolatori numerici

Prima di tutto si danno le seguenti definizioni fondamentali:

- Procedura di elaborazione = qualsiasi procedimento che, a partire dalle informazioni di partenza e dal metodo per

trasformarle in qualcos'altro, attraverso operazioni più o meno note al processore, produce informazioni finali.

- Programmazione = consiste nell'identificare il procedimento per ottenere dalle informazioni di partenza X, le in

formazioni finali volute Y.

- Programma = descrizione, attraverso istruzioni, della Procedura di elaborazione.

- Istruzione = descrizione formale di un'operazione elementare.

- Processore = l'ente che esegue la Procedura di elaborazione.

- Processo = l'insieme delle attività svolte dal Processore durante l'esecuzione del Programma.

In generale comunque, anche se l'esecutore non è un mezzo automatico, si può dire che quanto più chiara e dettagliata

è la Procedura di elaborazione e quanto più elementari sono le Istruzioni, tanto più il Processore può essere poco

"specializzato nel problema da risolvere".

2. Campi di impiego degli elaboratori

Indipendentemente dalla potenza di un Processore (si intende ora un Calcolatore Elettronico), la sua efficienza e la sua

versatilità, dipendono dalla possibilità di trasformare ogni Procedura di elaborazione in un numero Finito di istruzioni

adeguatamente semplici: cioè, perchè il Processore si renda utile in un certo campo, è sufficiente sviluppare un

Programma adatto allo scopo; e i campi di applicazione sono svariati:

- Settore Amministrativo-Gestionale

- Settore Tecnico-Scientifico

- Settore dell'Automazione d'ufficio

- Settore dell'Automazione della fabbrica

- Settore dell'Information Retrieval

- Applicazioni Ipertestuali e Multimediali

- Simulazione di Sistemi

- Progettazione tecnica assistita dall'elaboratore (CAD)

- Grafica computerizzata

- Editoria elettronica

- Didattica

4. Linguaggi simbolici

La programmazione vera e propria, al suo gradino elementare, avviene nel cosiddetto Linguaggio Macchina, tuttavia

non poche sono le difficoltà che un programmatore incontra quando si cimenta con tale strumento: la necessità di

pianificare in anticipo l'uso di tutto le risorse del Processore, dalla memoria, alle operazioni consentite; il formalismo

specifico della macchina; il numero proibitivo di istruzioni che bisogna usare per descrivere anche le operazioni più

semplici; il rischio altissimo, in tutto questo, di commettere numerosi errori.

Esistono, in alternativa, i Linguaggio Simbolici, i quali, pur mantenendo un certa complessità, risultano più sintetici e

adoperano strutture, anche sintattiche, il cui uso risulta più semplice ed intuitivo per il programmatore: solo

successivamente ala stesura di un Programma Origine in tali termini semplificati, sopraggiunge ad opera di un

Programma Traduttore la Traduzione in un Programma Oggetto (simile a quello sviluppato in Linguaggio Macchina), il

Collegamento tra i vari moduli e parti del programma, il Caricamento del Codice e la sua Esecuzione.

Vari sono i tipi di Linguaggi Simbolici, raggruppabili in due categorie:

- Linguaggi orientati alla macchina = che si propongono di semplificare la programmazione del singolo calcolatore, a

partire dal relativo linguaggio macchina.

- Linguaggi orientati ai problemi = che si propongono di realizzare la migliore forma espressiva per programmare una

classe specifica di problemi, indipendentemente dal calcolatore su cui il Programma finale sarà eseguito.

Tra i primi, assumono importanza i cosiddetti Linguaggi Assemblativi, che rappresentano il primo passo verso la

semplificazione della programmazione: essi, in generale, eseguono per ogni istruzione del linguaggio un'istruzione del

Processore (Programmazione a passo 1), e comunque, nei casi in cui tale istruzione elementare corrispondente non sia

implementata direttamente dal Processore, forniscono Macrocodici appositi. Ebbene, tali linguaggi, uniscono la

accresciuta semplicità del Linguaggio Macchina con la sua efficienza, e permettono di elaborare Programmi anche molto

potenti ma strutturalmente semplici.

Riguardo ai secondi, si può aggiungere che quanto più risulta semplice la sintassi offerta dal Linguaggio, e quanto più

sono complesse le strutture che esso permette di elaborare, tanto più complesso sarà il corrispondente Programma

Traduttore, che dovrà associare all'occorrenza ad ogni istruzione del Programma Origine molte istruzioni del Linguaggio

Macchina, e che dovrà ridurre le strutture complesse in quelle primitive offerte dal Processore, il tutto "Compilando" di

fatto un Programma Oggetto totalmente differente da quello di partenza.

Linguaggi interessanti sono: FORTRAN, ALGOL (algebrici), COBOL, PL1 (commerciali), Basic, Pascal, C, ADA, C+

+ (generali), SIMULA, GPSS (simulazione), etc..

Inoltre, tra i cosiddetti Linguaggi di IV Generazione (utilizzati in specifici ambienti software) ci sono: Word-Processor,

Spreedshet, DBMS, programmi di Grafica, linguaggi per sviluppare Ipertesti (HTML), ambienti per il calcolo simbolico e

numerico (Mathematica), ambienti per il calcolo matriciale (MathLab), etc..

Per questi ultimi, il programmatore dispone di costrutti per definire "cosa" ottenere e non "come" ottenerlo, a differenza

dei comuni linguaggi imperativi.

6. Hardware e software

Definiamo:

- Hardware = l'insieme delle parti meccaniche, elettroniche e circuitali che costituiscono un Elaboratore.

- Software = l'insieme dei Programmi operanti sull'Elaboratore.

- Operazioni realizzate in Hardware = quelle previste appositamente dai costruttori dell'Hardware ed implementate da

un'unica istruzione del Linguaggio Macchina.

- Operazioni realizzate in Software = quelle implementate da più istruzioni del Linguaggio Macchina e che prevedono

dunque a monte una sequenza definita di Istruzioni più elementari riconosciute dall'Elaboratore.

Possiamo considerare che, in sostanza, il Calcolatore è un'apparecchiatura che, anche se molto complessa

strutturalmente, in realtà molto semplice nelle funzioni elementari che offre, talmente elementari che ad una prima

occhiata, ogni operazione di "ordinaria" difficoltà richiede per essere eseguita di istruzioni di gran lunga più banali dettate

al Calcolatore: in generale quindi, insieme all'Elaboratore, vengono forniti una serie di programmi Software che ne

costituiscono il cosiddetto Software di Base o di Sistema, che interfacciano la macchina con l'utente, e che fanno apparire

la prima al secondo molto più sofisticata di quanto non lo sia.

In generale tale corredo software prevede:

- Sottoprogrammi che implementano operazioni non previste dal Calcolatore (Operazioni Floating-point - laddove non ci

sian già -, funzioni trigonometriche, radice quadrata, ...).

- Sottoprogrammi per l'esecuzione delle operazioni di Input e Output.

- Traduttori di linguaggio.

- Programmi Applicativi svariati.

- Moduli software per la gestione del sistema (Sistema Operativo).

7. Sistemi operativi

I Sistemi Operativi, atti alla gestione del sistema, diventano giorno dopo giorno sempre più sofisticati, così come le

macchine che devono gestire. Tra le tecniche di gestione che usano c'è la cosiddetta Multiprogrammazione, che permette

di sfruttare i tempi morti dell'elaboratore (causati dalla differenza di velocità con le Periferiche o con i terminali remoti)

tramite tecniche note come Time-Sharing e Real-Time: tramite la prima, il tempo totale di elaborazione viene suddiviso in

piccole parti, ciascuna ciclicamente associata all'intervento di una "parte" o di un "programma" del sistema, il che

permette quindi, per esempio, a più programmi di venire eseguiti quasi "simultaneamente", senza lunghe code derivate

dalle differenze di velocità di esecuzione tra ciascuno di essi e gli altri; in tali condizioni, se la risposta dell'elaboratore, a

ciascuno di essi (o a un terminale remoto) risulta "sufficientemente rapida", si parla di applicazioni eseguite in Real-Time,

cioè in tempo utile per chi le usa.

I Sistemi operativi sono in genere divisi in più sezioni, ma una di esse, detta Supervisore, è residente stabilmente in

memoria e governa e gestisce tutte le altre, richiamandole dalla memoria di massa a tempo opportuno, allo scopo di

effettuare operazioni necessarie al corretto funzionamento della Macchina (gestione delle fila di Programmi in

esecuzione, allocazione della memoria per i Programmi Utente, richiamo dei Programmi Traduttori, gestione delle

Memorie di Massa e delle periferiche Input-Output, segnalazione degli Errori, ...).

Risulta evidente che uno degli sforzi irrinunciabili per rendere una Macchina efficiente sia quello di dotarla di un

altrettanto efficiente Sistema Operativo.

Capitolo secondo = I tipi semplici

1. I tipi: introduzione

Il concetto di Informazione, associato alla Scelta, è caratterizzato da 3 parametri:

- Tipo T = insieme degli elementi tra i quali viene eseguita la scelta del valore.

- Attributo A = significato dell'informazione.

- Valore V = particolare elemento scelto nel tipo T.

Il Dato, rappresentato dalla tripla {T,V,A}, è poi associato ad uno dei Registri di Memoria, in generale numerabili, per

cui si ha la seguente corrispondenza:

- Tipo T => insieme dei valori rappresentabili nel registro R.

- Attributo A => nome N della variabile => indirizzo I del registro R.

- Valore V => dato memorizzato nel registro R.

Un Tipo è caratterizzato da:

- le Operazioni eseguibili su di esso (Interne o Chiuse, ed Esterne o Aperte).

- una finita Cardinalità (in quanto i suoi valori sono memorizzati in Registri di dimensioni limitate).

- un Ordinamento (Parziale o Totale).

- l'essere Semplice (costituito da elementi non scindibili) o Strutturato (scomponibile in tipi più semplici).

La Definizione dei tipi può avvenire per:

- Enumerazione, elencando tutti gli elementi appartenenti: T = ( a, b, c, ... )

- Definizione di una proprietà: T = ( t / P )

2. Variabili e costanti

I dati di un programma hanno forma di Variabili o Costanti e vengono Dichiarati (in quasi tutti i linguaggi) in una

apposita sezione ad inizio programma, chiamata Sezione Dichiarativa. Oltre alla Dichiarazione, importante è

l'Inizializzazione (che avviene con modalità diverse nei vari linguaggi) ad un valore iniziale, anche se poi nel corso del

programma l'Assegnazione, l'Uso e una successiva Assegnazione di un qualsiasi valore diverso alla Variabile, è consentito

praticamente senza limiti.

L'uso di Costanti avviene inserendo nel codice del programma dei valori ben precisi (es.: un numero) usando precise

convenzioni (es.: forma esponenziale) e in tal caso la Dichiarazione del tipo della Costante è Implicita e desunta dalla

notazione usata. Ma esistono anche Costanti con Nome, un po' come variabili il cui contenuto non può essere tuttavia

modificato, ma a cui l'accesso è indubbiamente reso più facile e intuitivo (es.: PI).

3. I tipi nei linguaggi di programmazione

I principali tipi nei linguaggi di programmazione sono:

- Tipi semplici = Intero, Reale, Booleano, Carattere, Enumerativo, Sottocampo.

- Tipi strutturati = Complesso, Stringa di caratteri, Stringa di bit, Array, Record o Struttura, Record con varianti,

Unione, File, Insieme.

- Tipo Puntatore.

In generale, comunque, ogni linguaggio mette a disposizione, per alcuni tipi semplici, diversi tipi in alternativa, laddove

al variare decrescente dello spazio occupato in memoria, diminuisce esponenzialmente la Precisione di Calcolo e il

Range. Inoltre, gran parte dei Linguaggi permette all'utente di crearsi, con più o meno limitazioni, i suoi Tipi Strutturati,

mettendo a sua disposizione un certo numero di Costruttori di vario tipo.

4. Definizioni e notazioni per le operazioni sui tipi

Ogni operazione è matematicamente parlando esprimibile come una Funzione (o Relazione) il cui dominio è l'insieme

degli Argomenti Ingresso (un prodotto cartesiano operato tra gli Insiemi di Partenza) ed il cui Codominio è l'insieme

degli Argomenti Uscita (un sottoinsieme del prodotto cartesiano tra gli insiemi di Uscita):

F : T' x T'' x ... x Tn ---> R' x R'' x ... x Rm

Nei vari linguaggi (almeno in generale) si propongono 4 notazioni principali:

- Notazione con Operatori = che può essere compresa se si pensa che anche l'addizione, identifiata dall'operatore "+",

esprime in realtà una funzione; sono adoperate a questo proposito:

- la forma Infissa (operatori Unari, Binari, Binari estesi).

- la forma Prefissa e Postfissa (Op t',t'' | t',t'' Op).

- Notazione Funzionale = che si usa nel caso di una Funzione che restituisce un unico risultato.

- Notazione Procedurale = che si usa nel caso di una Funzione che restituisce più di un risultato.

- Notazione Funzionale con effetti collaterali = che prevede una Funzione che restituisce dichiaratamente un unico

risultato, ma modifica in maniera non evidente uno o più dei suoi parametri (essa sostituisce, nei linguaggi in cui non è

presente, la Notazione Procedurale).

5. Tipo intero

Il tipo intero è definito come l'insieme dei numeri interi appartenenti ad un certo intervallo [M,m] dove gli estremi sono

comunque molto distanti tra loro (dipende poi dal "tipo di intero" scelto) e la sua Cardinalità è "M-m+1". Esso è

preferibile al tipo Reale, se si svolgono operazioni su interi, perchè le istruzioni nel calcolatore operate su interi risultano

in generale più precise: tuttavia, è necessario usare il tipo Reale quando si trattano dati in virgola o che eccedono la

cardinalità imposta dagli interi, così come sono definiti.

Le operazioni effettuabili sugli interi sono (fatta salva la possibilità di Overflow):

- Divisione intera.

- Divisione con risultato reale.

- Resto intero della divisione.

- Altre funzioni definite da apposite Librerie (valore assoluto, potenza, Trigonometria, ...).

Come gli interi vengono definiti e i loro valori massimi e minimi dipendono dalla Macchina su cui si opera e dal

Compilatore usato (insieme del Processore e del Linguaggio): in generale, per un intero a X bit, l'intervallo ha come

estremi "-2^(X-1)" e "2^(X-1) -1".

6. Tipo reale

Il tipo reale è definito come l'insieme dei numeri reali appartenenti ad un definito intervallo [M,m] tale che scelto un

qualsiasi numero reale astratto "x" compreso tra gli estremi, esiste almeno un "reale concreto" X, tale che si verifichi: |

ε ε

(X-x)/x | < , dove M, m ed sono caratteristici dei singoli sistemi (ovviamente, così definito, per tale insieme non è

definita una Cardinanalità).

L'eguaglianza tra reali non ha senso con l'operatore "=", poichè bisogna tener conto piuttosto del fatto che lo scarto tra

i due numeri considerati sia inferiore ad una quantità prefissata ed opportunamente piccola.

Come per gli interi, anche per i reali ne esistono più tipi: tra i vari tipi (32 bit, 64 bit) quello suggerito dallo standard

IEEE per i reali prevede:

- 80 bit

- mantissa di 64 bit più segno

- esponente di 15 bit

- valori estremi con esponente a +4932 e -4932

7. Tipo carattere

Il tipo carattere è definito come l'insieme dei Simboli Stampabili, Caratteri di Spaziatura e Caratteri di Controllo. La sua

Cardinalità è tipicamente di 256, risulta Parzialmente Ordinato e la tabella codici di riferimento è ASCII. Varie sono le

Funzioni applicabili (Rel, Succ, Pred, Ord, Int, Chr, ...).

8. Tipo enumerativo

E' un tipo definito dall'utente che comprende elementi inseriti da questi. Il suo uso è più che altro interno al codice, per

rendere più leggibile ed autodocumentante il programma. Varie sono le Funzioni applicabili (Rel, Succ, Pred, Ord, ...).

9. Tipo sottocampo

E' un tipo definito dall'utente e si pone come sottoinsieme dei valori di un tipo noto, di cui vanno fissati gli estremi. In

alcuni linguaggi non è definito.

10. Tipo booleano

E' un tipo che comprende i valori "False" e "True". E' usato per problemi inerenti l'Algebra di Boole, per caratterizzare

fatti che esistono oppure no, riferito a predicati per il controllo del flusso del programma: ovviamente gli si possono

applicare le operazioni (Not, Or, And, =, <=, !=). Esistono vari modi per rappresentare il tipo booleano:

- Teoricamente (e solo in tal caso) con 1 bit

- Usando l'ultimo bit di un byte

- Usando tutti i bit di un byte contemporaneamente

- Compattando 8 valori booleani in un byte

- Il C++ in generale non implementa il tipo booleano, ma usa al suo posto il tipo intero (0=False, !=0 True): se si

rappresentano i tipi booleani con più bit, si possono usare non solo le operazioni booleane calssiche ( !, &&, || ) ma anche

quelle bit-a-bit (^, &, | ).

11. Relazioni e predicati

Le Relazioni sono applicabili ad ogni Tipo Ordinato e producono un Valore Booleano: sono quindi casi particolari di

Predicato. Un Predicato è infatti una espressione booleana.

12. Funzioni per la trasformazione di tipo

Esistono, in generale, svariate funzioni di conversione tra Tipi: talvolta, come in C++, esse sono del tutto automatiche,

secondo necessità.

Capitolo terzo = I tipi strutturati fondamentali

1. Tipi strutturati

Un tipo strutturato è caratterizzato da:

- Tipi Componenti, che possono essere a loro volta strutturati.

- Modalità di assemblaggio dei componenti, che può essere per:

- Prodotto Cartesiano, con definizione di una n-pla, con n fissato.

- Sequenza, con definizione di un allineamento di valori omogenei di lunghezza variabile (ricordando che una Sequenza

di Simboli o Bit è detta Stringa, essa può anche essere vuota).

- Funzione di accesso, cioè la notazione e la modalità per accedere ad un componente, il che può avvenire per:

- Nome associato a ciascun componente (per il prodotto Cartesiano).

- Posizione all'interno della struttura (per la Sequenza).

- Costruttore del tipo (struttura sintattica).

- Costruttore dei valori struturati (notazione sintattica).

Per quanto concerne le Operazioni sui tipi strutturati, esse possono essere:

- basate su operazioni elementari attuate sui singoli componenti.

- funzioni specificamente previste per le strutture da apposite Librerie.

- implementate dall'utente con i mezzi messi a disposizione dal linguaggio (Classi per il C++)

2. Array

L'Array può essere definito in senso astratto come il Prodotto Cartesiano tra n insiemi omogenei, cioè come una n-pla

di valori omogenei, ciascuno dei quali è singolarmente accessibile e modificabile, tramite riferimento ad un indice

calcolato in base alla posizione nella struttura. Un array può essere Monodimensionale (Vettore), Bidimensionale (Array

di Array o Matrice) o Multidimensionale.

Il tipo Array è implementato diversamente nei vari linguaggi, anche se le funzioni di accesso fanno in generale uso del

nome della struttura indicata e dell'indice del valore accessibile tra parentesi quadre.

Le operazioni sugli Array possono riguardare gli elementi dell'Array (in generale tutte le operazioni eseguibili sul Tipo)

o l'Array in quanto tale (allora, taluni linguaggi specializzati nella trattazione di array, effettuano: somma/prodotto degli

elementi di una matrice, valore minimo/massimo di un array, prodotto di vettori/matrici, ...).

3. Allocazione degli array

Gli Array possono essere allocati in memoria con due diverse tecniche:

- Allocazione statica = si definisce a tempo di compilazione la dimensione massima utilizzata della struttura, e quindi la

memoria che verrà riservata ad essa.

- Allocazione dinamica (disponibile non per tutti i linguaggi) = l'allocazione della memoria necessaria a memorizzare gli

elementi avviene a tempo di esecuzione, così l'Array occupa lo spazio strettamente necessaria, con la sola limitazione

della memoria effettivamente disponibile sulla Macchina.

Ognuna delle due tecniche presenta vantaggi e svantaggi, legati essenzialmente alla maggiore velocità di accesso a

strutture statiche, rispetto a quelle dinamiche, e - per contro - alla possibilità di non sapere in anticipo quanto spazio

occorrerà allocare per strutture di dimensioni grandi e/o variabili.

Ovviamente i singoli elementi di un Array sono soggetti ad un ordinamento totale in memoria, in modo da rendere la

Funzione di Acesso (che si rifà ad un indice) coerente con l'effettiva disposizione in memoria dei singoli valori: tale

ordinamento totale prevede che l'elemento con l'indice più basso sia "precedente" ad uno con un indice più alto, e a parità

di indice (per Array Multidimensionali), conta quello dell'Array più interno, e così via. In generale, il primo byte

dell'elemento X[i][j][..][n] si troverà a "i*j*...*n*sizeof(Tipo)" bytes dalla prima locazione di memoria impegnata dalla

struttura.

4. Gli array nel linguaggio C++

[vedere libro di Programmazione]

5. Il tipo record o struttura

Il tipo Record è una struttura simile all'Array, nel senso che è definibile come Prodotto Cartesiano di più Tipi, ma essi,

a differenza dell'Array, possono non essere omogenei: ogni elemento del Record è identificato non da un indice, ma da un

Nome assegnato alla variabile apposita in fase di dichiarazione, e la Funzione di Accesso è proprio

NomeRecord.NomeVariabile. Le Operazioni che generalmente si possono attuare sono l'Assegnazione a singolo valore o

l'Assegnazione di una serie di valori all'intero Record "NomeRecord = { ..., ..., ...}", e in alcuni linguaggi anche

operazioni di Input, Output e Confronto.

6. Il tipo record in C++. Esempi

[vedere dal libro]

7. Dimensione delle strutture dati in C++

Essenzialmente restituita dalla parola chiave "sizeof NomeVariabile" o "sizeof (NomeTipo)".

9. Il tipo astratto stringa di caratteri

La Sringa di caratteri è un allineamento di caratteri. Se ne viene definita una costante, essa sarà contenuta generalmente

tra virgolette o apici, e poi trattata opportunamente dal compilatore. L'uso che se ne può fare è vario, e quello forse più

intuitivo è legato alla necessità di dare all'utente messaggi in chiaro per guidarlo nel programma.

Le proprietà astratte delle stringhe sono:

- Lunghezza della stringa.

- Stringa vuota.

- Operazione di concatenamento.

La Relazione d'Ordine tra due stringhe segue la regola di ordinamento lessicografico (come nei vocabolari), dove la

maiuscola precede la minuscola, e una parola più corta precede una più lunga.

Le principali Operazioni effettuabili sulle stringhe, e implementate diversamente nei vari linguaggi sono:

- Lettura da Input di una stringa.

- Scrittura in Output della stringa.

- Assegnazione tra stringhe.

- Determinazione della lunghezza di una stringa.

- Relazione tra stringhe (sempre lessicografica).

- Ricerca in una stringa di un carattere o sottostringa.

- Accesso in una stringa all'i-esimo carattere o ad una sottostringa.

- Inserimento o Rimozione in una stringa di caratteri o sottostringhe.

10. La stringa nei linguaggi di programmazione

Nei diversi linguaggi la stringa viene trattata in modo diverso:

- Array di caratteri (PASCAL, C, C++).

- Tipo proprio a lunghezza fissa (FORTRAN, COBOL).

- Liste dinamiche (LISP, SNOBOL).

Solo nel terzo caso la lunghezza della stringa può teoricamente variare senza limiti, negli altri invece, anche se la

memoria viene allocata dinamicamente, c'è sempre una dimensione massima consentita.

Capitolo quarto = Le istruzioni semplici

1. Dati ed istruzioni

Definiamo "Istruzioni Semplici" quelle istruzioni che esprimono azioni elementari del programma, "Istruzioni

Strutturate" quelle composte da più istruzioni semplici in particolari strutture.

Consideriamo vari tipi di Istruzioni (Semplici o Strutturate):

- Istruzioni per l'alterazione di Variabili e per l'attivazione di unità I/O:

- Istruzioni di Ingresso (trasferiscono valori da un'unità Input ad una Variabile).

- Istruzioni di Chiamata di Sottoprogramma (chiamano un Sottoprogramma passando i necessari parametri).

- Istruzioni di Calcolo e Assegnazione (calcolano un valore e lo assegnano ad una Variabile).

- Istruzioni di Uscita (trasferiscono valori dall'interno del calcolatore ad un'unità Output).

- Istruzioni per il Controllo di Sequenza:

- Istruzioni per il Salto Semplice o Condizionato.

- Istruzione Sequenza.

- Istruzioni Condizionali.

- Istruzioni Iterative.

2. Istruzioni di ingresso (o di lettura).

Le Istruzioni di Ingresso in generale specificano:

- l'Unità di Ingresso da cui trasferire i Dati.

- il Formato dei dati in ingresso.

- la Variabile (o Lista di variabili) che assumerà i Valori in ingresso.

Ciascuna operazione di lettura da un Input produce l'inserimento di un "Record di Ingresso"che verrà accodato al

cosiddetto "File sequenziale di Ingresso": da questo, dopo ogni Istruzione di Ingresso, verrà letto il Record successivo

all'ultimo letto in un tempo precedente e appositamente inserito.

Nei Linguaggi di Programmazione sono diffuse Convenzioni Implicite allo scopo di ridurre il numero di parametri che

l'utente deve specificare: è il cosiddetto meccanismo di "Default (mancanza)" che associa un valore prefissato ad un

parametro, qualora esso non venga specificato. Ebbene, in generale, si assume che l'Unità di Ingresso e il Formato dei

dati di Ingresso siano specificati per Default come rispettivamente "l'Unità Standard di Ingresso" e "il Formato

coincidente con il formalismo previsto dalle costanti del Tipo".

Un'Istruzione di Lettura, dunque, assume una forma tipica del tipo: "Read Variabile-Lista".

3. Istruzioni di iscita (o di scrittura)

Le Istruzioni di Uscita in generale specificano:

- l'Unità di Uscita in cui trasferire i Dati.

- il Formato dei dati in uscita.

- il Valore (o Lista di valori) che devono essere trasferiti.

Ciascuna operazione di scrittura su un Output produce la creazione di un "Record di Uscita" che verrà accodato al

cosiddetto "File sequenziale di Uscita": da questo, dopo ogni Istruzione di Uscita, verrà letto il Record successivo

all'ultimo letto in un tempo precedente e appositamente riprodotto.

In generale, si assume che l'Unità di Uscita e il Formato dei dati di Uscita siano specificati per Default come

rispettivamente "l'Unità Standard di Uscita" e "il Formato coincidente con il formalismo previsto dalle costanti del Tipo".

Un'Istruzione di Scrittura, dunque, assume una forma tipica del tipo: "Write Valore", dove per Valore si intendono una

Costante, una Variabile, una generica Espressione.

8. Sottoprogrammi, procedure e funzioni

Un Sottoprogramma è un particolare programma eseguito non autonomamente ma solo su richiesta da un altro

Programma o Sottoprogramma detto "Chiamante", ed è realizzato dall'utente allo scopo di suddividere il Programma

Principale in moduli più semplici, oppure si presenta come parte di un Software di Base o di un Software Applicativo e

viene chiamato solo quando occorre.

L'attivazione di un Sottoprogramma S (che può essere comunque chiamato più di una volta, e da Programmi diversi) è

determinata dalla Istruzione di Chiamata posta nel Programma P: dopo l'esecuzione di S (e, in alcuni linguaggi, dopo

un'apposita Istruzione di Ritorno) il controllo passa nuovamente al Programma Principale e viene eseguita l'istruzione

immediatamente successiva alla chiamata di S in P.

Un Sottoprogramma, in generale, scambia valori col Programma Chiamante, e ciò avviene attraverso la definizione di

"Parametri o Argomenti di Scambio", i quali sono rappresentati nella pratica dai "Parametri o Argomenti Formali"

(definiti nel Prototipo o Intestazione del Sottoprogramma) e dagli "Argomenti Effettivi" (passati da P sotto forma di

Valori-Variabili di Ingresso e Variabili di Uscita, rispettivamente da cui S prenderà i Dati Iniziali, e in cui depositerà i

Dati Finali) tra loro in corrispondenza biunivoca in base all'Ordine con cui sono dichiarati. In che modo S sia organizzato

al suo interno non ha alcuna importanza rispetto all'organizzazione interna di P, giacchè le variabili definite in S vengono

"generate" ad ogni esecuzione di S e "distrutte" col ritorno a P, ed hanno inoltre un valore "locale", cioè non intaccano le

variabili di P neanche se ci sono casi di omonimia. L'unico caso in cui ciò non avviene è quando come mezzo di scambio

dei dati si usano Variabili Globali (regolamentate dai vari linguaggi), definite ed usate senza restrizioni sia da P che da S.

Negli altri casi invece, non c'è comunicazione diretta tra il "corpo" di S e quello di P, a maggior ragione se S effettua, per

esempio, trasferimenti di dati in Standard Input e Standard Output (lo può fare perchè è un programma a tutti gli effetti)

piuttosto che attraverso variabili di scambio.

Diversa è la terminologia che si usa nella classificazione dei Sottoprogrammi da parte dei vari Linguaggi: tra le varie

notazioni, comunque, riconosciamo quella Funzionale, quella Procedurale e quella Funzionale con Effetti collaterali.

La creazione di un Sottoprogramma richiede essenzialmente una Intestazione (nella quale si specificano il Nome usato

per la chiamata, la Lista di Parametri e l'eventuale Valore restituito dalla Funzione) e da un Corpo (delimitato da appositi

Simboli per indicarne l'Inizio e la Fine). In base poi alla notazione con cui tale Sottoprogramma viene creato, differente è

il modo di Chiamata: Istruzione a parte (Chiamata di Procedura) o Chiamata all'interno di una Espressione (Chiamata di

Funzione).

Riguardo ai "Parametri o Argomenti" passati al Sottoprogramma, essi hanno un Nome, un Tipo e un Ruolo (Input,

Output, entrambi): il Ruolo viene specificato con apposite notazioni che indicano a P e ad S, se ciascun parametro è

passato per Valore (in tal caso ne sarà impossibile la modifica) o per Riferimento (in tal caso S avrà diretto accesso alla

Variabile specificata, sia in lettura che in scrittura).

9. I sottoprogrammi nel linguaggio C++

[vedere libro Programmazione]

10. Istruzioni per il controllo di sequenza

Le Istruzioni per il controllo di sequenza consentono che la sequenza di istruzioni dichiarata nell'Algoritmo sia

Dinamica piuttosto che Statica: cioè, magari in risposta ad un Valore in Input, piuttosto che un altro, l'Algoritmo si

comporta diversamente, eseguendo magari una parte delle sue istruzioni invece che altre.

Tra queste istruzioni, quella di Salto Semplice o Condizionato è l'unica Semplice ed è presente soprattutto nei

Linguaggi di basso livello, mentre invece le altre, Strutturate, vengono utilizzate nei Linguaggi ad alto livello.

11. Istruzioni di controllo non strutturate (di salto)

Le Istruzioni di Salto, presenti nei linguaggi macchina e assemblativi, rappresentano gli strumenti elementari per la

realizzazione di costrutti strutturati ad alto livello, e si distinguono in:

- Istruzioni di Salto Incondizionato = definiscono la prossima istruzione (indicata dall'Indirizzo nei Linguaggi a basso

livello, da un'Etichetta o Label nei Linguaggi ad alto livello) da eseguire.

- Istruzioni di confronto e Salto Condizionato = saltano all'Istruzione considerata se una certa Espressione Booleana è

vera.

- Istruzione di Arresto Dinamico = si ottiene con un richiamo infinito di un'Istruzione a se stessa (es.: "A: goto A") e

pone in stallo il Programma fino al sopraggiungere di un Intervento di Break esterno.

- Istruzioni di Arresto = permette, con un'opportuna chiamata al Processore, di interrompere seduta stante il flusso di

istruzioni in corso e di restituire il controllo al Sistema Operativo, il che, d'altronde, avviene automaticamente dopo

l'esecuzione dell'ultima istruzione dell'algoritmo.

Capitolo quinto = Le istruzioni strutturate

1. La programmazione strutturata

La programmazione strutturata permette di utilizzare in luogo di più istruzioni di Salto Condizionato o Incondizionato

una struttura più Sintetica, ma soprattutto aumenta in modo notevole la leggibilità del Programma, permettendo all'utente

o al programmatore stesso di inquadrare agevolmente l'intera struttura dell'Algoritmo a diversi Livelli di Astrazione con

grande chiarezza.

Esiste sempre in ogni linguaggio un insieme finito (più o meno nutrito) di Istruzioni Strutturate o Costrutti: si

dimostrerà che è sufficiente un suo sottoinsieme per scrivere agevolmente un tipo qualsiasi Programma.

2. Il costrutto sequenza

Il costrutto "Sequenza di Istruzioni" o "Istruzione composta" è appunto una sequenza di Istruzioni (Semplici o

Strutturate) che consente, nei Linguaggi ad alto livello, una elevata capacità di nidificazione delle Strutture di Controllo.

In C++ essa si presenta nella forma generale:

{ Istruzione1;

Istruzione2;

...

IstruzioneN; }

3. Costrutti di selezione

Ne esistono di 3 tipi generali, implementati più o meno allo stesso modo nei vari linguaggi:

1) If ... Then ... = condiziona l'esecuzione di una Istruzione.

2) If ... Then ... else ... = usata per la selezione tra 2 Istruzioni.

3) Case: ... = usata per la selezione tra più di 2 Istruzioni.

E' possibile inoltre esprimere il numero (3), tramite una serie di costrutti del tipo (2) concatenati (es.: If A then A1 else

if B then B1 else if ...).

In C++ esse corrispondono ai costrutti:

1) if (condizione) Istruzione;

2) if (condizione) Istruzione1; else Istruzione2;

3) switch (espressione) { case Valore1: Istruzione1; break; default: IstruzioneD; }

5. Costrutti di iterazione

I Costrutti di Iterazione permettono di eseguire una Istruzione o una Sequenza di Istruzioni:

- Ciclicamente salvo il rispetto di una Condizione che può essere verificata Prima o Dopo il ciclo.

- a Ripetizione un Numero prefissato di volte.

Essi sono di 3 tipi fondamentali:

- "While-do" o "while" = ciclo a Condizione Iniziale, eseguito da "0" a "N" volte.

- "Repeat... Until" o "do... while" = ciclo a Condizione Finale, eseguito da "1" a "N" volte.

- "For... to... do" o "for (...)" = ciclo a Conteggio, eseguito da "PrimoEstremo" a "SecondoEstremo" volte.

In C++ per ogni tipo valgono le seconde tra quelle enunciate.

7. Equivalenza dei programmi. Teorema di Bòhm-Jacopini

Mentre appare evidente che le Istruzioni semplici di Salto Condizionato e Incondizionato consentono,

indipendentemente dalla complessità richiesta, di esprimere un qualsiasi Flusso di Controllo, ciò non è altrettanto

evidente per le Istruzioni Strutturate del medesimo tipo.

Consideriamo le seguenti definizioni:

- "Due programmi si dicono Funzionalmente Equivalenti se, a partire da uno stesso insieme di Dati di Ingresso,

terminano allo stesso modo o entrambi non terminano".

- "Un insieme S di Istruzioni Strutturate è Funzionalmente Completo per un linguaggio L se, per ogni programma P in L,

ne esiste uno Funzionalmente Equivalente che usa solo le istruzioni strutturate di S".

- "L'insieme S = {Sequenza, If...Then...else, While} è Funzionalmente completo" (teorema di Bòhm-Jacopini).

L'Equivalenza Funzionale tra due Programmi può essere dimostrata verificando che entrambi evocano la stessa

sequenza di esecuzione, cioè compiono sequenzialmente le stesse istruzioni: partendo da questa osservazione e dal

teorema di Bòhm-Jacopini, si può affermare che (ed è facile verificarlo) un Insieme Funzionalmente Completo è S =

{Sequenza, una Istruzione di Selezione, una Istruzione di Ciclo}.

8. Altri costrutti per il controllo di sequenza

Ulteriori Costrutti per il controllo di sequenza sono così elencati:

- Istruzioni per la Sospensione dei cicli.

- Istruzione di Continuazione di un ciclo.

- Cicli Indefiniti (es.: while (1) ...).

- Istruzione Sequenza e Terminatori dell'Istruzione:

- Terminazione non esplicita (presente nei linguaggi che prevedono l'istruzione composta).

- Terminazione esplicita (con uso di appositi delimitatori finali come "end if ", "end while" o "end do").

- Strettura "else if " con terminazione grazie ad un unico "endif " (per i linguaggi con terminazione esplicita).

9. Modalità di scrittura

Nello scrivere un programma alcuni elementi vanno tenuti in considerazione:

- le Parole Chiave sono generalmente Riservate (tranne in alcuni linguaggi come il Fortran).

- l'uso obbligatorio delle Parentesi nelle istruzioni di controllo (opzionali in alcuni linguaggi come il Pascal).

- l'uso degli Spazi con funzione di Delimitazione (tranne in alcuni linguaggi come il Fortran).

- l'uso di Delimitatori per dividere le Istruzioni ( ";" in C++ e Pascal, "Invio" in Fortran).

- l'uso dei caratteri Minuscoli in generale intercambiabile con quelli Maiuscoli (tranne che in C++).

Capitolo sesto = Programmi con strutture di selezione

1. Caratteristiche dei programmi

Per lo sviluppo dei programmi occorrono essenzialmente:

- definizione del Problema da risolvere espresso col "cosa" si vuole ottenere e non col "come" va prodotto.

- definizione della Specifica del programma con l'individuazione di:

- Insieme dei dati di Ingresso.

- Insieme di Precondizioni sui dati di Ingresso.

- Insieme dei dati di Uscita.

- Insieme di Postcondizioni sui dati di Uscita.

- definizione del Metodo di elaborazione attraverso:

- metodi matematici (Calcolo numerico, Statistica, Ricerca, ...).

- metodi ingegneristici (Fisica, Chimica, Progettazione, ...).

- metodi informatici (Ordinamento, Gestione degli archivi, ...).

- Procedure Tradizionali o Intuitive.

- definizione dell'Algoritmo, cioè il "come" bisogna operare.

Le strutture fondamentali dei programmi sono:

- struttura semplicemente Sequenziale.

- struttura di Selezione.

- struttura Ciclica.

- struttura con Lista definita tramite Array.

- struttura Ricorsiva.

Capitolo ottavo = Programmi con array

1. Introduzione

Gli Array sono forse le strutture più diffuse nei linguaggi di programmazione, utilizzate come sono nel trattamento di

Vettori, Elenchi, Tabelle e così via. Tuttavia le Operazioni già messe a disposizione dai linguaggi per il trattamento degli

Array sono poco efficaci, giacchè, il più delle volte, operazioni Complessive (cioè dedicate alla manipolazione dell'array

nella sua interezza) o di semplice I/O: quindi risulta necessario definire operazioni più complesse sui singoli componenti e

poi estenderle con Cicli a tutta la struttura.

Capitolo nono = La ricorsione

1. Introduzione e ricorsività

La Ricorsività o Ricorsione in Informatica si riconduce all'Induzione in Matematica. Tale "principio di Induzione",

usato largamente per la dimostrazione di teoremi, può essere così enunciato: <<Sia P un predicato sull'insieme dei

naturali N e sia vero P(0); se per ogni "k" da P(k) vero discende la verità di P(k+1), allora P(n) è vero per qualsiasi

"n">>.

Con una certa analogia a quanto visto, una funzione F(x) ricorsiva è una funzione che è calcolabile "al passo i-esimo"

tramite un'espressione che include un richiamo a se stessa in una fase differente (per un "i" maggiore o minore)

dell'Algoritmo, e che è invece direttamente calcolabile per un "i" fissato (in generale "i"=0 o "i"=1) dove restituisce un

valore ottenibile relativamente in modo Semplice o addirittura già Noto. La Definizione Ricorsiva quindi prevede la

definizione di una Base (che è l'obiettivo cui tende nei suoi ciclici richiami a se stessa la funzione) e di un Asserto

Induttivo (sulla base del quale scompone il Valore di Ritorno in una parte Direttamente Calcolabile e in un'altra

rimandata all'analisi di se stessa): dopo "k" Fasi Ascendenti, tramite le quali l'espressione iniziale viene sviluppata "k"

volte in espressioni di semplicità crescente, ci sono "k" Fasi Discendenti, nelle quali i valori calcolati da F(k+1) vengono

reinviati a F(k) fino a raggiungere la prima chiamata della funzione che restituirà il Risultato voluto e definitivo.

2. Schemi di algoritmi ricorsivi

Schema fondamentale di una Funzione ricorsiva in C++ è:

TipoRestituito F ( X ) {

...

if (Condizione su X) return Base;

else return "Espressione contenente un nuovo richiamo ad F"; }

4. Meccanismo interno di ricorsione

Un Programma Ricorsivo è un programma che richiama direttamente o indirettamente se stesso: se P richiama se stesso

direttamente si parlerà di Ricorsione Diretta, se invece P chiama Q che poi a sua volta richiama P (quindi richiama se

stesso indirettamente) allora si parlerà di Ricorsione Indiretta o Mutua.

Il meccanismo di Ricorsione può essere esemplificato tecnicamente ipotizzando di avere più copie del Programma,

ciascuna con le proprie Variabili Locali indipendenti da quelle delle altre copie: la strategia che disciplina la Chiamata e

Ritorno dai sottoprogrammi è del tipo LIFO, quindi le diverse copie del programma saranno gestite tramite un'apposita

Memoria a Pila, e l'ultima ad essere allocata sarà la prima ad essere rimossa.

5. Risoluzione in forma iterativa di un algoritmo ricorsivo

Un problema formulato ricorsivamente può essere tradotto in termini Iterativi attraverso un uso combinato di

Sottoprogrammi appositi e di una Gestione a pila della Memoria (magari riprodotta dal programma utente al suo

interno). Tuttavia se la precedente "Espressione contenente un nuovo richiamo ad F" in realtà è solo un blocco di

Istruzioni S con alla fine il richiamo nudo e crudo ad F, si dice che esiste Ricorsione in Coda, ed in realtà il meccanismo è

facilmente riproducibile con un Ciclo su S.

6. Impiego degli algoritmi ricorsivi

Gli algoritmi ricorsivi sono adatti quando il problema da risolvere sia effettivamente esprimibile solo Ricorsivamente, o

risulti più semplice ed intuitivo creare una Funzione che richiami se stessa. In altri casi, anche a causa della necessità di

allocare molta memoria dinamicamente (memoria non sempre disponibile!) è preferibile, qualora esista un'agevole

alternativa in termini Iterativi, propendere per quest'ultima.

Capitolo undicesimo = Problemi di ordinamento e di ricerca

1. Generalità

[leggere]

2. Ordinamento per selezione

Data una lista L di N elementi, "al passo i-esimo" per "i" che va 2 a N si opera come segue:

- si fanno (N-i ) confronti a partire dalla posizione i-esima tra i vari elementi per selezionare il Minore.

- l'elemento i-esimo scambia di posto col Minore trovato

L'elaborazione richiede (N-1) volte (N-i ) operazioni di confronto, per un totale di "N(N-1) /2" confronti in tutto ed ha

Complessità di ordine "N^2".

3. Ordinamento per scambi (bubble sort)

Data una lista L di N elementi, "al passo i-esimo" per "i" che va da 1 a N-1, a partire dal primo fino all'elemento "(N-

i+1)esimo" incluso, si effettuano scambi tra elementi successivi se quello precedente è maggiore di quello seguente.

Comunque se durante "il passo i-esimo" non si effettuano scambi il ciclo può terminare in anticipo!

L'elaborazione richiede al più (N-1) volte (N-i ) operazioni di confronto, per un totale di "N(N-1) /2" confronti in tutto

ed ha Complessità di ordine "N^2".

4. Ordinamento per inserzione

Data una lista L di N elementi, "al passo i-esimo" per "i" che va da 2 a N, si confronta l'elemento i-esimo con ciascuno

degli elementi appartenenti alla sottolista di estremi "1" ed "i-1" fino a che non si trova un elemento più grande (si sono

operati "k", al più "i-1", confronti): a questo punto se viene trovato tra i primi (i-1) l'elemento maggiorante si spostano

( i-k ) elementi a partire dal maggiorante incluso e l'i-esimo è salvato al suo posto, altrimenti nessuna operazione

supplementare è compiuta.

L'elaborazione richiede costantemente "N(N-1)/2" operazioni in tutto e ha Complessità "N^2".

5. Ordinamento con doppio indice (quick sort)

Data una lista L di N elementi, si presentano i seguenti casi:

*Per N=1 si restituisce l'elemento così com'è.

*Per N=2 se il primo è maggiore del secondo scambiali di posizione.

*Per N>2 si sceglie un elemento qualsiasi X (per esempio quello mediano) e si procede come segue:

1) partendo dalla sinistra estrema della lista si individua il primo elemento S maggiore di X e posto alla sua sinistra.

2) partendo dalla destra estrema della lista si individua il primo elemento D minore di X e posto alla sua destra.

3) si fanno i seguenti opportuni spostamenti, a seconda che:

- esiste sia S che D = essi si invertono di posto.

- esiste S ma non esiste D = tutti gli elementi da quello successivo ad S fino ad X incluso vengono spostati di una

posizione a sinistra, ed S (precedentemente salvato in memoria) va al posto di X.

- esiste D ma non esiste S = tutti gli elementi da X fino quello precedente a D vengono spostati di una posizione a

destra, e D (precedentemente salvato in memoria) va al posto di X.

- non esiste nè S nè D = chiama ricorsivamente la Funzione di ordinamento per le due Sottoliste a sinistra e a destra

dell'elemento X in posizione "x", e concatena i risultati nell'ordine "SottolistaSinistraOrdinata" + X +

"SottolistaDestraOrdinata".

7. Fusione di due array

Siano V1 e V2 array ordinati di valori, di lunghezza rispettivamente L1 ed L2. L'algoritmo che opera la fusione di V1 e

V2 in un'array di lunghezza (L1+L2) opera in questo modo:

1) si crea un array vuoto V3 di tale dimensione (L1+L2).

2) se V1 o V2 è vuoto, salta al punto (4).

3) confronta il primo elemento di V1 col primo di V2, il minore dei due inseriscilo in V3 ed eliminalo dalla lista di

appartenenza facendo affiorare un nuovo elemento e vai al punto (2).

4) svuota tutti gli elementi della lista non vuota in V3.

9. Ordinamento per distribuzione e fusione di un array

Sia F una Funzione di Ordinamento che procede in questo modo:

*Se la Lista ha Cardinalità N=2, ordina per scambio i suoi componenti e restituisci la Lista ordinata.

*Se la Lista ha Cardinalità N>2 allora:

- dividi la lista in due Sottoliste (per esempio nel punto mediano).

- restituisci la Fusione delle due Sottoliste ordinate, ciascuna ovviamente con un richiamo ricorsivo ad F.

11. Metodi di ricerca in una lista

I metodi di Ricerca in una Lista di Cardinalità N sono essenzialmente due:

- Ricerca Lineare = obbligatoria per Liste non ordinate, consiste nello scorrere tutta la Lista alla ricerca dell'elemento

cercato, con al più N confronti e in media N/2 confronti.

- Ricerca Binaria = possibile per Liste ordinate, consiste nell'individuare volta per volta l'elemento mediano di una

Sottolista (al primo tentativo essa coincide con la Lista di partenza) verificando se l'elemento cercato è Minore, Maggiore

o Uguale all'elemento mediano specificato: nei primi due casi l'analisi ricomincerà ristrettamente ad una delle due

sottoliste definite (quella a Sinistra o a Destra del punto medio), nel terzo caso si ha la soluzione della ricerca e la sua

terminazione.

Capitolo tredici = Struttura dei programmi

*Da Ricordare solo i seguenti concetti fondamentali:

- Standard di un linguaggio.

- Linguaggi Traduttori (o Compilatori) e Interpreti.

- Supporto al tempo di esecuzione (Run-time): supporto di Sistema, supporto di Linguaggio.

- Definizione di Modulo.

- Validità o Portata, Visibilità e Tempo di legame.

- Variabili Statiche, Dinamiche implicite, Dinamiche esplicite.

- Allocazione della memoria = memoria a Sola Lettura, memoria Statica, memoria Dinamica o area Heap, memoria o

area Stack.

Capitolo quattordicesimo = Sviluppo dei programmi

*Da Ricordare solo i seguenti concetti fondamentali:

- Fasi di sviluppo del software = Preparazione, Compilazione, Collegamento, Esecuzione e Debugging. (individuazione di

possibili cause di malfunzionamento).

- Documentazione = Motivazioni (ragione e obiettivo di un segmento di programma), Asserzione (posta dopo il

segmento descritto, definisce lo stato di uno o più dati a seguito dell'esecuzione di quel segmento), Commenti relativi alle

dichiarazioni dei dati (definizione dell'attributo e funzione di ogni variabile), Documentazione Esterna (cosa fa e come

usarlo), Documentazione Interna (come lo fa e perchè in quel modo).

- Sviluppo schematico dei programmi = Albero dei raffinamenti dell'algoritmo, Albero di attivazione delle procedure,

Albero di struttura dei moduli e Albero delle relazioni d'uso.

- Errori di programmazione = Definizione del problema, Scelta dell'algoritmo, Mancato controllo (Cicli, casi Limite e

Degeneri), Approssimazione numerica, Errori (Sintattici, Semantici, di Algoritmo, attribuibili al Sistema), Errori segnalati

in fase di Esecuzione (Overflow nella divisione, negli indici degli array, ...), Errori nei risultati (che sono inaspettati!)

9. Il testing

La verifica della correttezza e della bontà di un software può avvenire attraverso due vie:

- Prooving = Dimostrazione di correttezza del programma.

- Testing = prove sistematiche di esecuzione.

In realtà, date le difficoltà determinate dall'applicazione del Proving a programmi di non piccole dimensioni, il Testing è

in generale la formula più usata, allo scopo di sottoporre il programma ad una forma di Collaudo che ne accerti con

"ragionevole certezza" il buon funzionamento. A questo scopo si predispone un insieme I di dati di ingresso ai quali,

passati per il programma, devono corrispondere certi precisi valori di un insieme U di Risultati in uscita (Metodi basati

sulle specifiche del programma) o dei particolari percorsi nella sequenza di istruzioni del programma (Metodi basati sulla

struttura del programma): ovviamente, la "copertura" delle possibilità di utilizzo è limitata ad un certo fissato numero di

casi e dunque c'è solo una "buona probabilità" che il programma, superato il test, sia effettivamente corretto.

Il testing è applicato diversamente, in base anche alle tecniche di sviluppo del software usate:

- nello sviluppo "bottom up", in cui vengono sviluppati prima i moduli più semplici e di basso livello, tali moduli vengono

provati grazie a programmini di "attivazione" specifici per ogni modulo e sviluppati "ad hoc" per il testing.

- nello sviluppo "top down", in cui vengono dapprima realizzati i moduli a più alto livello, sono questi ad essere testati,

predisponendo in anticipo esemplari semplificati (e dal funzionamento guidato dal programmatore) dei moduli non

ancora sviluppati.

Infine, tra gli altri, si citano altri importanti (e meno ovvi ) strumenti per il Testing:

- programmi di Tracing e Debugging.

- inserimento di Asserzioni e relativa verifica.

- creazione di Insiemi di Dati di Test.

- aggiornamento e mantenimento di Versione del prodotto e relativa Documentazione.

Capitolo quindici = La progettazione dei programmi (approssimativo)

*Da Ricordare solo i seguenti concetti fondamentali:

- Classificazione dei programmi in: Applicazioni sequenziali (programmi gestionali e matematici), Applicazioni dipendenti

dal tempo (in tempo reale), Applicazioni Concorrenti (come i Sistemi Operativi); Applicazioni orientate ai dati (sistemi

informativi), Applicazioni orientate alle funzioni (manipolazione di dati), Applicazioni orientate al controllo (controllo e

sincronizzazione di più attività).

- Il ciclo di vita di un software prevede: Studio di fattibilità, Analisi dei requisiti, Definizione delle specifiche, Progetto

dell'Architettura del software, Progetto dei singoli moduli, Codifica e testing dei moduli, Integrazione dei moduli e

collaudo del sistema, Rilascio del sistema, Manutenzione (Correttiva, Additiva o Adattiva alle richieste dell'utente,

Perfettiva).

- I metodi per lo sviluppo di un software sono: Formali, Informali, Semiformali; tra i vari ricordiamo: diagrammi di

flusso, automi a stati finiti, programmazione orientata ad oggetti,...

- per lo Studio di Fattibilità: opportunità di Riuso del software, Compatibilità col software esistente, scelta dell'Ambiente

di Programmazione, Definizione delle specifiche.

- per il Progetto dell'Architettura, bisogna sviluppare moduli che possano godere di (una delle 4): coesione Funzionale,

coesione di Comunicazione, coesione Procedurale, coesione Logica, Accoppiamento intermodulo.

3. Metodologie di progettazione ascendente e discendente

Tra i vari approcci alla programmazione, due sono i fondamentali e tra loro contrapposti:

- Approccio discendente (Top-Down), cioè dal generale al particolare = decomposizione del problema in sottoproblemi

usato per progettare algoritmi orientati alle funzioni; presenta i seguenti svantaggi: non favorisce il riconoscimento di

sottoproblemi comuni a più problemi, non consente un adeguato incapsulamento delle strutture dati, l'approccio

algoritmico risulta anticipato rispetto alla completa definizione del problema.

- Approccio ascendente (Bottom-Up), cioè dal particoare al generale = prevede la realizzazione preliminare dei moduli

atti a svolgere le operazioni sulle strutture dati richieste dal problema, ed il programma viene poi realizzato sulla base

delle funzionalità messe a disposizione dai moduli fondamentali; se da un lato prevede il riuso dei moduli, dall'altro lo

sviluppo anticipato dei moduli può rivelarsi dannoso, qualora le caratteristiche funzionali di questi dovessere rivelarsi

dannose nel corso dello sviluppo del progetto.

C'è poi un approccio alla Programmazione orientata agli oggetti, che è simile alla programmazione Bottom-Up, ma

fondata sui Tipi Astratti di dati: il che permette di costruire moduli con certe precise caratteristiche, interfacciati a

strutture dati incapsulate nel programma e dunque di facile uso, manipolazione, modifica e ampliamento.

4. Metodologia del raffinamento

La progettazione Top-Down si fonda su due concetti fondamentali:

n

- il principio del Divide et Impera, secondo cui problemi più piccoli si dominano meglio di 1 problema più grande: in

questa ottica il programma è pensato come insieme di sottoprogrammi più snelli e semplici.

- il principio dell'Astrazione, secondo il quale un problema viene dapprima studiato nella sua visione complessiva e

soltanto in seguito se ne studiano i particolari.

Per ciascun sottoproblema si applicando iterativamente i seguenti concetti, partendo da un livello di massima

astrazione, fino a far affiorare di volta in volta particolari più o meno importanti: questa è la metodologia del

raffinamento successivo (Step-Wise refinement, progettazione Top-Down).

Tale processo di raffinamento è basato su un processo di astrazione:

- sul Controllo = si adopera nel programma un insieme limitato di istruzioni, cioè Sequenza, Selezione e Iterazione, tutte

ad un ingresso ed un'uscita.

- sulle Azioni = via via nel programma vengono dettagliate le azioni da compiere.

- sui Dati = le strutture vengono dapprima concepite come astratte, e solo in un secondo momento vengono specificate in

concreto.

Inoltre, è prevista la decomposizione in sottoprogrammi a vari scopi:

- mantenere il programma al livello di astrazione richiesto dal programmatore.

- sviluppare un'applicazione con modalità decentrata.

- organizzare biblioteche di sottoprogrammi.

- evitare la riscrittura di programmi identici.

5. La programmazione ad oggetti come esigenza di progetto

Principali caratteristiche della prograamazione ad oggetti:

- Classe, Oggetto e Metodo (evoluzione dei concetti di Tipo, Variabile e Procedura).

- l'oggetto deve favorire il processo di astrazione, permettendo al progettista di lavorare con termini a lui familiari.

- deve essere disponibile un'Interfaccia del modulo, attraverso la quale, senza entrare nei dettagli realizzativi, sia possibile

produrne una Istanziazione e crearne un esemplare da usare.

- la Struttura interna va tenuta nascosta.

- le Operazioni vanno definite in base alla struttura degli oggetti, in modo da non dover abbandonare l'astrazione.

- deve essere fornita la cosiddetta Ereditarietà, derivando moduli da moduli esistenti: gli oggetti di ciascuna classe

derivata ereditano le proprietà della classe origine e su di essi è possibile apportare modifiche sulle operazioni

preesistenti, magari ampliandole e specializzandole.

- Genericità = nel definire un tipo di dato astratto non viene specificato il tipo di alcune variabili, così da poter utilizzare


PAGINE

33

PESO

335.78 KB

PUBBLICATO

+1 anno fa


DESCRIZIONE APPUNTO

Riassunto per l'esame di Fondamenti di Informatica [/b, basato su appunti personali e studio autonomo del testo consigliato dal docente Fondamenti di Informatica, Fadini Savy .
Sintesi fondamentale per comprendere i vari approcci teorici e pratici all'informatica, il calcolo automatico e l'elaborazione elettronica in cui si prendono in considerazione i seguenti argomenti: il concetto di algoritmo, di automa, la macchina di Turing, tesi di Church, Modello di Von Neumann, la macchina astratta generalizzata, hardware e software, algebra di Boole, teorema di De Morgan.


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria informatica
SSD:
A.A.: 1999-2000

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher trick-master di informazioni apprese con la frequenza delle lezioni di Fondamenti di informatica e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Napoli Federico II - Unina o del prof Vittorini Valeria.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Fondamenti di informatica

Fondamenti di informatica - prova scritta A esame 2003
Esercitazione
Fondamenti di informatica - prova scritta B esame 2003
Esercitazione
Fondamenti di informatica - prova scritta C esame 2003
Esercitazione
Fondamenti di informatica - prova scritta D esame 2003
Esercitazione