Elementi di Programamzione

appuntiDiIngegneria

Elementi di

Programmazione

Sommario

1.0. Elementi di Programmazione ........................................................................................................... 3

1.1. Introduzione all’Informatica ............................................................................................................. 3

1.2. Codifica e Rappresentazione delle Informazioni ............................................................................... 5

1.2.1. Codifica Binaria............................................................................................................................. 8

1.2.2. Conversioni di Base .....................................................................................................................10

1.2.3. Rappresentazione di Interi Negativi .............................................................................................11

1.2.4. Somma Binaria ............................................................................................................................11

1.2.5. Rappresentazione di Numeri Reali ...............................................................................................12

1.3. Macchina di Turing ..........................................................................................................................13

1.4. Algoritmi .........................................................................................................................................14

1.5. Compilatori ed Interpreti .................................................................................................................19

1.6. Paradigmi e Linguaggi di Programmazione ......................................................................................23

1

1.7. Fondamenti della Programmazione .................................................................................................28

1.7.1. Variabili e Tipi di Dati ...................................................................................................................28

1.7.2. Strutture di Codice ......................................................................................................................32

1.7.3. Funzioni.......................................................................................................................................35

1.7.4. Puntatori .....................................................................................................................................41

1.7.5. Allocazione Dinamica ...................................................................................................................43

1.7.6. Array ...........................................................................................................................................45

1.7.7. Algoritmi di Ordinamento di un Array ..........................................................................................47

1.7.8. Algoritmi di Ricerca in un Array....................................................................................................52

1.8. Strutture Dati ..................................................................................................................................54

1.8.1. Lista.............................................................................................................................................54

1.8.2. Stack ...........................................................................................................................................56

1.8.3. Coda ............................................................................................................................................58

1.8.4. Grafo ...........................................................................................................................................60

1.8.5. Albero .........................................................................................................................................65

2

1.0. Elementi di Programmazione

1.1. Introduzione all’Informatica

L’informatica riveste un ruolo essenziale nella vita di tutti i giorni diventando uno degli strumenti

principali nell’analisi e nella manipolazione del mondo contemporaneo. La vita di ognuno è ormai

permeata in tutte le sue forme dalla presenza del calcolatore: non esiste nessun aspetto in cui il

calcolatore non abbia fatto sentire il suo peso cambiando non solo il modo in cui i prodotti ed i

servizi sono realizzati ed offerti, ma anche l’interazione tra l’uomo e gli oggetti stessi. Basti

pensare ad ambiti quali il divertimento (cinema, videogiochi, intrattenimento, ...) oppure le

comunicazioni (Internet, telefonia mobile e fissa, email, etc) fino ad arrivare a settori vitali come la

medicina con la presenza di dispositivi come i pacemaker. Questo fenomeno è ormai così

irreversibile che l’immagine stessa di alcuni prodotti e servizi è totalmente cambiata da quando il

calcolatore è entrato in essi. L’informatica ed i calcolatori sono ormai diventati essenziali anche

nello studio delle scienze. Intuitivamente le scienze di tipo sperimentale traggono grande

giovamento dalla presenza del calcolatore: il computer è diventato ormai il centro di tutti i

laboratori poiché unisce alla possibilità di ricreare i più disparati ambienti attraverso simulazioni

software, la capacità di calcolare funzioni estremamente complesse con grande precisione ed

affidabilità. Inoltre la sua grande velocità lo rende strumento indispensabile nell’acquisizione,

memorizzazione ed analisi di grandi quantità di dati, al centro di ogni esperimento di scienza

applicata (fisica sperimentale, biologia, ...).

Più formalmente l’informatica è la scienza della rappresentazione e dell’elaborazione

dell’informazione in maniera automatica, ovvero lo studio degli algoritmi (sequenze precise di

operazioni comprensibili e perciò eseguibili da uno strumento automatico) che descrivono e

trasformano l’informazione. Il termine informatica nasce dall’unione di due parole:

 Informazione: ogni forma espressiva (scritta o grafica) o comunicazione (orale, con dati,

etc.) comprensibile ed elaborabile dall’uomo. È un qualcosa che si può comunicare,

conservare, e sulla quale è possibile operare delle scelte.

 Automatica: elaborazione/trasformazione delle informazioni e dei dati per giungere ad un

risultato senza l’intervento esterno dell’uomo.

L’informazione deve essere rappresentata (dati), per fare ciò è necessario trascriverla e registrarla

su supporti materiali secondo una opportuna codifica; occorre rappresentare anche

l’elaborazione (algoritmo), ed infine applicare l’elaborazione all’informazione (esecutore).

L’informatica comprende numerosissime discipline, ad esempio: Teoria dei Codici, Architettura dei

Calcolatori, Sistemi Informativi, Basi di Dati, Sistemi Operativi, Reti di Calcolatori, Teoria

dell’Informazione, etc. 3

È importante precisare che la stessa informazione può essere rappresentata in maniera differente:

L’informazione esiste a prescindere dalla sua rappresentazione, ad esempio il numero 10 esiste

come idea platonica a prescindere dal fatto che lo si possa rappresentare in qualche modo,

tuttavia se non lo si rappresenta non è possibile elaborarlo, memorizzarlo oppure comunicarlo.

L’informazione deve essere rappresentata su dei supporti materiali, che devono:

 Raccogliere impressionati quantità di dati;

 Rendere disponibili questi dati in modo istantaneo e con prospettive diverse a utenti

diversi e in parti diverse del mondo;

 elaborare automaticamente la rappresentazione dei dati in modo da presentarli in modo

diverso a diversi soggetti, prendere delle decisioni in base alle proprietà degli oggetti

rappresentati, e produrre nuovi dati esempi.

Tali supporti materiali prendono il nome di Calcolatori (o Elaboratori elettronici, o Computer), che

sono dei sistemi digitali a programma registrabile che consentono l’elaborazione automatica

dell’informazione, costituito da molte parti che interagiscono tra loro per eseguire algoritmi:

Più formalmente, un Calcolatore è caratterizzato dall’espressione Y = F(X), dove X è l’insieme

discreto degli ingressi, Y è l’insieme discreto delle uscite, ed F è una funzione che esegue in

maniera automatica la corrispondenza fra X ed Y, ottenendo dei dati di output a partire da dei dati

di ingresso. Le componenti di tali sistemi possono suddividersi a livello marco in due tipologie:

 Hardware: componenti fisici del sistema, tutto ciò che si può toccare con mano, ad

esempio Processori e le Periferiche. Le operazioni (chiamate istruzioni) che l’HW sa

4

eseguire direttamente costituiscono il linguaggio macchina del calcolatore; le istruzioni del

linguaggio macchina sono molto semplici, ma il calcolatore può eseguirle in modo molto

efficiente (un’operazione seguita in HW è molto più efficiente rispetto alla stessa eseguita

in SW).

 Software: programmi eseguiti dal sistema. Si distingue il Software di base, che è il SW

dedicato alla gestione dell’elaboratore che opera direttamente al di sopra di HW e del

firmware (ad esempio il Sistema operativo, i DBMS, i Protocolli di comunicazione di Rete),

dal Software Applicativo, il quale è dedicato alla realizzazione di specifiche esigenze

applicative, utilizza linguaggi di alto livello, opera al di sopra del SW di base e non risente

delle caratteristiche architetturali del sistema informatico (quindi è trasportabile). In

generale, il SW di base ha lo scopo di mostrare ai suoi utenti il calcolatore come una

macchina virtuale (non esistente fisicamente) più semplice da usare rispetto all’hardware

sottostante.

Il confine tra HW e SW è piuttosto sfumato se si pensa che le stesse funzioni possono essere svolte

a seconda dei casi da circuiti e dispositivi HW o da particolari microprogrammi (firmware) definiti

dal costruttore del calcolatore.

Programmare significa scrivere un programma che adatti la logica funzionale della macchina alle

esigenze operative di un certo problema, secondo uno svolgimento sequenziale. Le esigenze

operative del problema scaturiscono dalla logica risolutiva idonea al conseguimento dei risultati

voluti. La logica funzionale di macchina è l'insieme di operazioni elementari che questa è in grado

di svolgere. Per svolgimento sequenziale si intende la successione nel tempo delle operazioni

elementari. L’output della Programmazione è un file di testo chiamato Programma Sorgente, il

quale descrive in termini di istruzioni note alla macchina, la soluzione del problema in oggetto. In

generale non esiste una sola soluzione ad un certo problema, le soluzioni potrebbero essere

numerose, la programmazione consiste proprio nel trovare la strada più efficiente che conduce

alla soluzione del problema in oggetto. Per risolvere un dato problema. I calcolatori vengono

programmati mediante algoritmi, che sono una sorta di “ricette”, ovvero dei procedimenti

composti da una sequenza di istruzioni elementari, che consente di risolvere un determinato

problema. Un Programma non é altro che un algoritmo scritto in un linguaggio non ambiguo e

direttamente comprensibile dal computer.

1.2. Codifica e Rappresentazione delle Informazioni

È stato già accennato che le informazioni, affinché possano essere gestite dai sistemi di

elaborazione, devono essere opportunamente codificate, quindi per informazione si intende tutto

ciò che può essere rappresentato tramite opportune sequenze di simboli in un alfabeto prefissato.

Un Codice C è un insieme di parole composte da simboli di un Alfabeto Σ che viene chiamato

anche alfabeto supporto di C. Invece la Codifica (o Rappresentazione) di un insieme di

informazioni I in un dato codice C è una funzione f:IC, ossia è una legge che associa ad ogni

5

informazione che si intende rappresentare una opportuna parola del codice C. In modo analogo la

Decodifica è una funzione g:CI. Un alfabeto di simboli deve generare parola dotate di:

 Una Sintassi: la configurazione di simboli deve essere ammissibile per poter dare un

qualche tipo di informazione, cioè deve rispettare determinate regole di composizione.

 Una Semantica: la parola generata deve avere un senso compiuto per poter dare un

qualche tipo di informazione.

Un esempio di Codifica molto utilizzata nel mondo dell’informatica è il Codice ASCII (American

Standard Code for Information Interchange), che è una codifica comune a livello globale costruita

in maniera tale da far comunicare tutti i calcolatori. Esso è composto da parole di lunghezza fissa a

7

2 =

7 bit (per un totale di 128 combinazioni), ciascuna del quale rappresenta in binario i simboli

non numerici usati nella scrittura (alfabeto, punteggiatura, parentesi, etc.) ed anche comandi

standard provenienti componenti di I/O (tastiera, stampante, etc.).

Dato che i dati vengono trasmessi in byte l’ottavo bit viene utilizzato per verificare la correttezza

del dato inviato (controllo di parità). Dato che il formato ASCII non viene più utilizzato come

protocollo di trasmissione, l’ottavo bit viene normalmente utilizzato per codificare caratteri non

standard. Anche utilizzando 256 configurazioni non è possibile modellare tutti i simboli utilizzati

nel mondo per comunicare (200.000), per tale motivo nel tempo sono nate diverse estensioni: la

prima estensione all’ASCII è stato il Latin-1 che utilizza un codice a 8 bit per modellare anche

lettere latine con accenti e segni diacritici (segni supplementari per precisare particolarità della

pronuncia). L’evoluzione attuale dell’Ascii è L’UNICODE, nella quale ogni carattere utilizza 16 bit,

6

per cui sono possibili ben possibili 65.536 configurazioni chiamate code point. Le code point che

vanno da 0 a 255 corrispondono al Latin-1; non tutte le configurazioni sono assegnate, per cui il

consorzio UNIOCDE vaglia continuamente nuove proposte. Per rappresentare i caratteri UNICODE

possono essere utilizzate diverse codifiche, tra cui la UTF-8 (Unicode Transformation Format, 8

bit), che negli ultimi anni è diventata la codifica principale di Unicode per internet secondo il W3C.

Anche i suoni devono essere rappresentati in un Calcolatore: un suono fisicamente è

rappresentato come un'onda (onda sonora) che descrive la variazione della pressione dell'aria nel

tempo, e si tratta di un segnale analogico. Per codificarlo occorre prima digitalizzarlo, scegliendo

opportunamente come parametri della codifica una frequenza di campionamento ed un numero

di bit da utilizzare per la quantizzazione di ciascun campione:

Il campionamento ad elevata frequenza e la quantizzazione con numero elevato di bit per

campione garantiscono una rappresentazione accurata. Le immagini invece vengono

rappresentate tramite una griglia o matrice di pixel (PIcture ELement) di ognuno dei quali è

memorizzata l’intensità luminosa (e/o il colore). I parametri importanti per la digitalizzazione di

immagini sono: la Dimensione (risoluzione), la Profondità, ed il Formato di rappresentazione

(Grayscale, RGB, Palette).

Un tipo molto importante di informazione è quella che specifica il valore di un numero naturale,

ma per rappresentare essi esistono diversi tipi di rappresentazione, che vengono suddivise in due

grandi classi: codifiche come quella romana, o italiana sono esempi di Codifiche Non Posizionali,

mentre invece quella decimale, binaria, ottale ed esadecimale sono esempi di Codifiche

Posizionali. L’attenzione si pone adesso sulle rappresentazioni posizionali pesate, le quali

associano alle cifre un diverso valore in base alla posizione che occupano nella stringa che

compone il numero. Esse sono definite dalla coppia (A, B) dove B > 1 è un intero chiamato Base

del Sistema, ed A è l’insieme dei simboli distinti dell’alfabeto, e devono essere tali che |A| = B. Gli

esempi tipici sono:

o Binario: B = 2, A = {0,1}

o Ottale: B = 8, A = {0,1,2,3,4,5,6,7}

o Decimale: B = 10, A = {0,1,2,3,4,5,6,7,8,9}

o Esadecimale: B = 16, A = {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F} 7

Ogni cifra rappresenta un numero distinto compreso fra 0 e B -1, ad esempio nel caso della

codifica esadecimale 1 = uno, 2 = due, A = dieci, F = quindici. Un valore numerico è rappresentato

=−

∑ × 10 …

da una sequenza di cifre appartenenti ad A: , dove è la parte intera

−1 2 1 0

…

mentre è la parte decimale. L’indice associato alla cifra denota la posizione della

−1 −2 −

cifra, la quale esprime il peso di essa. Ad esempio dato un sistema decimale: ()

Per evidenziare la base B del sistema di numerazione si usa la seguente notazione , in genere

se la B è omessa essa vale 10. La cifra più a sinistra è chiamata cifra più significativa, che nel caso



binario B = 2 prende il nome di MSB Most Significant Bit; la cifra più a destra invece è chiamata



cifra meno significativa, che nel caso binario prende il nome di LSB Less Significant Bit.

Un calcolatore elettronico dispone di uno spazio finito per memorizzare le cifre che esprimono un

valore numerico, esistono infatti almeno tre grandi cause di perdite di informazioni:

 Overflow: il risultato è maggiore del valore massimo rappresentabile, ad esempio se si ha a

disposizione 3 cifre decimali, l’insieme di rappresentabilità è S = {0,..,999}, nel caso di 600 +

600 = 1200 si ha una perdita di informazioni per eccesso.

 Underflow: il risultato è minore del valore minimo rappresentabile, nel caso precedente

l’esempio è 3-5 = -2.

 Non Appartenenza all’Insieme: si verifica quando il risultato dell’operazione, pur non

essendo troppo grande o troppo piccolo, non appartiene all’insieme dei valori

rappresentabili S.

1.2.1. Codifica Binaria

Tutti i sistemi informatici utilizzano la Codifica Binaria, che si basa sulla definizio