Enrico Vicario

Fondamenti di ProgrammazioneLinguaggio c, strutture dati e algoritmi elementari, c++

Indice

Introduzione 1

1 Rappresentazione 3

1.1 Il linguaggio c . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.1.1 Sintesi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 Strutture dati e algoritmi elementari 9

3 Estensione dal c al c++ 11

Testi di approfondimento 11

3

Introduzione

Questo libro e pensato come introduzione alla programmazione di un calcolatore.E organizzato in due parti e un’appendice.

Nella prima parte viene trattato il modo in cui un algoritmo puo essere rap-presentato ed eseguito su un calcolatore. L’elemento centrale e il linguaggio c,di cui la trattazione mira a fornire una padronanza avanzata basata sulla com-prensione analitica e la razionalizzazione di un insieme di regole anziche sullaenumerazione di esempi. La trattazione fa leva su due opposte premesse: da unlato una descrizione operativa e analitica del processo con cui un programma cpuo essere compilato in un linguaggio assembler, codificato in forma numerica eeseguito su un processore; dall’altro l’introduzione di concetti teorici elementariche permettono di esprimere in modo compatto e non-ambiguo le regole sintat-tiche e semantiche di un linguaggio. In Appendice la trattazione del c e estesa alc++, con l’intento di abilitare l’accesso ad un testo di progettazione dove l’ap-prendimento del linguaggio sia sostenuto da adeguati strumenti di astrazione emetodologia.

Nella seconda parte, vengono introdotti i concetti di struttura dati e di algorit-mo facendo riferimento alla rappresentazione di liste e alberi binari e ai problemidella ricerca e dell’ordinamento. La trattazione fornisce l’opportunita di introdurreconcretamente concetti fondamentali quali: la separazione tra logica e implemen-tazione di una struttura dati; gli schemi di implementazione ricorsiva e iterativa;la valutazione della complessita di un algoritmo e di un problema; la verifica dellacorrettezza; il riuso di schemi e soluzioni nella implementazione di un algoritmo.Anche, fornisce un contesto logico ben definito per un uso avanzato dei concettidi programmazione c introdotti nella prima parte del testo.

Nel testo sono anche riportati gli svolgimenti di prove di esame che permettonodi esercitare e verificare l’apprendimento.

Il testo riflette da vicino i contenuti del corso di Fondamenti di Informatica chetengo da diversi anni presso la facolta di Ingegneria di Firenze, e che molto risentedella mia provenienza dall’area dell’ingegneria del software piu che da quella deglialgoritmi.

1

Negli anni mi e capitato di tenere il corso in diversi formati. Attualmente lopresento in un corso di 80-90 ore per 9 Crediti Formativi Universitari (CFU) alprimo semestre del primo anno.

Il nucleo caratterizzante e costituito dalle sezioni ?? dove si fornisce un’intro-duzione intuitiva al linguaggio, ?? dove si introducono gli elementi di grammaticache servono ad una trattazione compatta, 1.1 dove si descrive in modo quasi com-pleto il linguaggio c, e ?? dove se ne dimostra un uso avanzato in riferimento allarappresentazione delle liste e dove si introducono vari concetti tra cui dato astrat-to e rappresentazione, iterazione e ricorsione. Tutto questo richiede tipicamente3+3+18+9 ore di lezione a cui convenientemente se ne aggiungono altre 6-12 diesercitazione teorica e pratica con cui si arriva a un totale di 4-5 CFU.

La parte sugli algoritmi nelle sezioni ??, ??, ?? e ?? consolida in qualchemisura l’uso del linguaggio ma soprattutto introduce in modo concreto elementiessenziali in un corso di Fondamenti di Informatica, tra cui in particolare i concettidi problema, algoritmo, complessita, correttezza. Tipicamente questo richiedealtre 3+3+15+3 ore a cui se ne aggiungono bene altre 3-6 di esercitazione e sene sottraggono bene 6 rimandando a un corso successivo lo HeapSort e il costomedio del QuickSort. Complessivamente il tutto corrisponde a 2-3 CFU.

La sezioni iniziali ?? e ??, sulla rappresentazione dei dati e sulla rappresen-tazione e esecuzione di istruzioni su un calcolatore, servono a creare una base chemotivi limiti e caratteristiche del linguaggio. In un corso al primo semestre delprimo anno servono anche a dare un’intuizione concreta sul principio di funziona-mento di un calcolatore. Complessivamente richiedono circa 18 ore che corrispon-dono ad ulteriori 2 CFU, ma sarebbe tranquillamente possibile saltare questa partee partire direttamente dalla trattazione del linguaggio c.

Le sezioni ?? sugli alberi e 3 sulla transizione dal c al c++ da diversi anni horinunciato a farle. Complessivamente richiederebbero almeno altre 9+9 ore peraltri 2CFU. La parte sugli alberi non e in effetti essenziale per un primo corso diInformatica e trova posto piu adeguatamente in un successivo corso su StruttureDati e Algoritmi. Ho qualche maggiore rimpianto per la transizione da c a c++,che peraltro nel nostro corso di laurea e sviluppata con maggiore ampiezza eprofondita, e con ottimi risultati, in un modulo di laboratorio immediatamentesuccessivo.

2

Capitolo 1

Rappresentazione

Il problema della rappresentazione consiste nel dare ad un algoritmo una formache possa essere eseguita su un elaboratore. In questo assume un ruolo centralel’uso di un linguaggio di programmazione.

In questo testo affrontiamo il problema facendo riferimento al caso del linguag-gio c. Questo ha un rilievo preminente in una ampia varieta di contesti applicativi,e costituisce comunque la base di c++ e java.

Dopo una prima breve descrizione di un frammento del c orientata a fornireun’intuizione circa le caratteristiche del linguaggio, la trattazione e ampliata in duedirezioni opposte. Da un lato sono descritti i principi del processo che permettedi tradurre un programma c in una sequenza numerica che possa essere caricatanella memoria di un elaboratore ed eseguita da un processore. Questo permette diintuire aspetti del processo di compilazione che determinano larga parte delle regoledel linguaggio. Dall’altro sono introdotti alcuni elementi teorici che permettono didescrivere il linguaggio attraverso un nucleo di regole generali, capaci di coglierein maniera compatta e univoca l’organizzazione sintattica e i contenuti semanticidel linguaggio.

Facendo leva sui due diversi strumenti di concretezza e astrazione, viene final-mente affrontato in maniera dettagliata la descrizione di sintassi e semantica dellinguaggio c.

3

1.1 Il linguaggio c

In questo capitolo viene definito il linguaggio c.La trattazione fa leva congiuntamente sui capitoli precedenti, con diversi gradi

di dipendenza: la descrizione informale del frammento di linguaggio c nel capitolo?? aiuta la comprensione fornendo una visione di insieme, ma e completamentecoperta da quanto viene ora esposto; la trattazione dei capitoli ?? e ?? circail modo in cui un programma c puo essere compilato in assembler, tradotto inlinguaggio macchina ed eseguito su un processore mostra un razionale per alcunecaratteristiche del linguaggio, ma puo essere anche omessa; gli elementi di teoriadei linguaggi forniti nel capitolo ?? sono invece usati diffusamente e risultanostrettamente necessari per la comprensione.

4

1.1.1 Sintesi

Ricapitoliamo in questa sezione la sintassi e la semantica generale delle categorieintrodotte nella descrizione del linguaggio c.

Tipi

<type> ::= char|[unsigned][short|long]int|float|double|void

<type expr> ::= <type>|struct<identifier>*|<type expr>*

<type decl> ::= <type>|struct<identifier>

<struct def> ::= struct<identifier>{ { <declaration> } };

Vincoli contestuali: in <type expr> e <type decl>, il nome <identifier> devecomparire in una <struct def> visibile.

La semantica di un tipo <type> consiste di un insieme di valori rappresentati eun insieme di operazioni sui valori. La stessa semantica si applica a <type expr>

e <type decl>, che costituiscono estensioni diverse strumentali a catturare lelimitazioni imposte sul tipo del valore restituito da un’espressione.

Dichiarazioni

<declaration> ::= <type decl><decl>;

<decl> ::= <identifier>|*<decl>|<decl>[<const>]|

(<decl>)|<decl>(<formal parameter list>)

<formal parameter list> ::= void|<type decl><decl>{,<type><decl>}

Vincoli contestuali: il tipo di una funzione deve appartenere a <type expr>.

La semantica di una dichiarazione <declaration> consiste nell’associare un nomee un tipo a un’entita referenziabile, che puo essere una variabile, un’array, unafunzione.

Riferimenti a variabile

<var>::=<identifier>|(<var>)|*<expr addr>|<expr addr>[<expr int>]|

<var s>.<identifier field>|<expr s>-><identifier field>

Vincoli contestuali: <identifier> deve essere il nome identificato in una<declaration> visibile; <expr addr> deve restituire un indirizzo; <expr int>

deve restituire un intero; <var s> deve essere un riferimento a variabile di tipostrutturato; <expr s> deve restituire l’indirizzo di una variabile di tipo strutturato;<identifier field> deve essere il nome identificato in una <declaration>

contenuta in una <struct def> visibile.

La semantica di un riferimento a variabile <var> consiste nell’identificare unavariabile, ovvero una locazione di memoria e un tipo.

5

Espressioni

<expr> ::= <const>|<var>|

<var a>=<expr a>|<var a><op2>=<expr a>|

++<var int>|--<var int>|<var int>++|<var int>--|

<expr1><op2><expr2>|<op1><expr>|

(<expr>)|<expr1>,<expr2>|<expr1>?<expr2>:<expr3>|

(<expr type>)<expr1>|&<var>|

<expr func>(<actual parameter list>)

<op2> ::= + | - | * | / | % |

< | <= | == | != | >= | > |

&& | || |

& | | | >> | <<

<op1> ::= ! | ∼

actual parameter list ::= [<expr>{,<expr>}]

Vincoli contestuali: il tipo di <var> deve appartenere a type expr; il tipo di<expr a> deve essere lo stesso di <var a>; il tipo di var int deve essere[unsigned][long|short]int; l’espressione <expr func> deve restituire un in-dirizzo di funzione.

La semantica di un’espressione <expr> consiste in un valore restituito (in un tipo)e una sequenza di side-effects.

Istruzioni

<statement> ::= <expr>;|

<statement1><statement2>|{<statement1>}|if(<expr>)<statement1> [else<statement2>]|for(<expr init>;<expr guard>;<expr inc>)

<statement>|

while(<expr guard>)<statement>|

do<statement>while(<expr guard>);|

return[<expr>];|goto<label>;|break;|continue;|switch(<expr>)

{ {case <const>:<statement>}[default:<statement>]

}

La semantica di un’istruzione <statement> consiste nell’identificare una sequenzadi espressioni eseguite e uno statement successivo a cui trasferire il controllo.

6

Programma

Un programma e costituito da una sequenza di direttive, di definizioni di strutturee di tipi, di dichiarazioni di funzioni o variabili, e di definizioni di funzione ciascunacostituita da una sequenza di dichiarazioni e statements.<program> ::= { <directive>|

typedef <type> <identifier>;|

<declaration>|

<function definition>

}<function definition> ::= <type><decl>(<formal parameter list>)

{ {declaration}<statement>

}

<directive>::=#include<filename.h>|#define<identifier><any>|...

7

8

Capitolo 2

Strutture dati e algoritmi

elementari

Introduciamo in questo capitolo i concetti di struttura dati e di algoritmo trattandoprima le liste e gli alberi binari e poi i problemi della ricerca e dell’ordinamento.

La trattazione fornisce l’opportunita per applicare in modo anche raffinatoi costrutti del c gia introdotti nella prima parte del testo. Permette anche diintrodurre in maniera concreta alcuni concetti fondamentali della programmazione:la separazione tra logica e implementazione di una struttura dati; i concetti diricorsione e iterazione; la valutazione della complessita di un algoritmo e di unproblema; la verifica della correttezza; la disciplina nella programmazione e ilriuso di schemi e soluzioni.

9

10

Capitolo 3

Estensione dal c al c++

11

12

Testi di approfondimentoArchitettura dei calcolatori:

• D.A.Patterson, J.L.Hennessy, “Struttura e progetto dei calcolatori,” Zanichel-li, Bologna, 1995.

• G.Bucci, “Architettura e organizzazione dei calcolatori elettronici - fonda-menti ,” McGraw-Hill Italia, Milano, 2001.

Linguaggio c:

• H.Schildt, “c, the complete reference,” McGraw-Hill, 2000.

• E.Yourdon, L.Constantine, “Structured design: fundamentals of a disciplineof Computer programming and system design,” Prentice Hall, 1986.

Linguaggio c++:

• E.Gamma, R.Helm, R.Johnson, J.Vlissides, “Design Patterns: elements ofreusable object oriented software,” Addison Wesley, 1995.

• M.Fowler, “UML distilled,” Addison Wesley, 2000.

• H.Schildt, “c++, the complete reference,” McGraw-Hill, 2002.

• J.Arlow, I.Neustadt, “UML e Unified Process,” McGraw Hill, 2003.

• K.Beck, “Embracing change with eXtreme Programming,” IEEE Computer,Vol.32, No.10, 1999.

Strutture dati, complessita e algoritmi:

• T.H.Cormen, C.E.Leiserson, R.L.Rivest, “Introduction to Algorithms,” MITPress, 1990.

• R.Sedgewick, “Algorithms in C” Addison Wesley, 1990.

• R.Sedgewick, “Algorithms in C++, parts 1-4” Addison Wesley, 1998.

• C.Batini, L.Carlucci Aiello, M.Lenzerini, A.Marchetti Spaccamela, A.Miola,“Fondamenti di Programmazione dei Calcolatori Elettronici,” Franco AngeliEditore Milano, 1993.

13