Appunti di
Corso 2021/2022 Fondamenti di
Programmazione
Francesco De Lucchini
1. Introduzione alla programmazione
L’informatica è lo studio sistematico degli algoritmi che descrivono e trasformano l’informazione,
la loro teoria e analisi, il loro progetto e la loro efficienza, realizzazione e applicazione.
Algoritmo
Sequenza precisa e finita di operazioni che portano alla realizzazione di un compito, implementata da
programmi scritti in un opportuno linguaggio e perciò eseguibili da un calcolatore.
Le operazioni utilizzate si distinguono in tre tipologie:
- operazioni sequenziali realizzano una singola azione
- operazioni condizionali in base al valore della condizione selezionano l’operazione
successiva da eseguire
- operazioni iterative ripetono un blocco di operazioni finché non è verificata una
determinata condizione
Le caratteristiche principali di un algoritmo sono:
- Eseguibilità ogni istruzione deve essere eseguibile in un tempo finito
- Non-ambiguità ogni istruzione deve essere univocamente interpretabile
- Finitezza ha un numero totale di istruzioni da eseguire finito
- Correttezza svolge correttamente il compito per cui è stato realizzato
- Efficienza termina correttamente nel modo più veloce possibile
Due algoritmi si dicono equivalenti quando hanno lo stesso dominio di ingresso (ad esempio i numeri
interi), lo stesso dominio di uscita e in corrispondenza degli stessi input producono gli stessi output.
Ogni algoritmo è rappresentabile graficamente tramite il diagramma di flusso o flow chart, il quale
tramite parallelepipedi simula ingresso e uscita, tramite rombi simula le condizioni e tramite
rettangoli simula le istruzioni.
Linguaggio di programmazione
Il linguaggio naturale non si presta a descrivere processi computazionali automatizzabili e non evita
le ambiguità, è dunque necessario utilizzare una notazione formale ossia un linguaggio di
programmazione, ne esistono diversi e sono tutti caratterizzati da:
- Sintassi insieme di regole formali per costruire frasi corrette nel linguaggio
- Semantica insieme dei significati da attribuire alle frasi costruite nel linguaggio
Grammatica BNF (Backus-Naur Form)
Tip: questo argomento non viene mai chiesto agli esami, serve solo a capire alcuni concetti!
Dato un alfabeto V (insieme di simboli), l’universo linguistico V* (v-star) è l’insieme di tutte le
sequenze finite di elementi (frasi) di V possibili; di conseguenza un linguaggio LG su alfabeto V è
un sottoinsieme di V* composto da frasi (elementi di V*) che soddisfano la sintassi espressa da una
grammatica formale G <V, VN, P, S> dove:
- V è l’insieme finito di simboli terminali
- VN è l’insieme finito di simboli non terminali
- P è l’insieme finito di regole di produzione
- S è un simbolo non terminale detto simbolo iniziale
In altre parole si dice linguaggio LG l’insieme di frasi di V derivabili da S applicando le regole di
produzione P, e le frasi di un linguaggio di programmazione vengono dette programmi di tale
linguaggio.
La grammatica BNF è una grammatica le cui regole di produzione sono della forma:
X (simbolo non terminale)
A , … , A (simbolo terminale o non)
n
1
Il metalinguaggio è un linguaggio secondario, in genere alcune parole del linguaggio naturale, usato
per descrivere sintattica e semantica del principale, e le sue “frasi” sono dette costrutti.
one of è un costrutto del metalinguaggio, il quale indica che X assume solo uno tra i vari A
i
A può essere seguito dal costrutto del metalinguaggio |opt che ne indica l’opzionalità
i
A-seq è un costrutto del metalinguaggio che indica una sequenza di termini A
i
Esempio di grammatica per i numeri interi: (derivazione left-most)
V = {-, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} simboli terminali
VN = {cifra, cifra-seq, intero} simboli non terminali
S = intero simbolo iniziale
Regole di produzione P:
cifra one of
0 1 2 3 4 5 6 7 8 9
cifra-seq (modo ricorsivo di indicare una sequenza)
cifra cifra-seq|opt
intero -|opt cifra-seq
2. Rappresentazione dell’informazione
L’informazione è qualcosa di astratto e per poterla manipolare bisogna rappresentarla; in un
calcolatore si rappresenta tramite i BIT (Binary digIT, cifra binaria), che possono assumere solamente
i valori 0 o 1; una sequenza di n bit può dunque contenere “informazioni”.
2
Una qualsiasi sequenza di 8 bit è detta Byte ed è l’unità di misura dell’informazione, altre ricorrenti
10 20
unità di misura della quantità di informazione sono i Kilobit (2 bit), Megabit (2 e Gigabit
)
30
(2 (e i corrispettivi in Byte).
)
Rappresentazione dei caratteri
La rappresentazione dei caratteri può avvenire tramite varie codifiche, tra cui:
7
- ASCII Standard (su 7 bit) converte 128 caratteri (2 )
8
- ASCII Estesa (su 8 bit) converte 256 caratteri (2 )
Nota: Il linguaggio C++ supporta solamente la codifica ASCII Estesa
Rappresentazione dei numeri naturali
I numeri naturali utilizzano la cosiddetta rappresentazione posizionale dove, data una sequenza di bit,
quello più a sinistra è il più significativo e quello più a destra il meno.
Teorema fondamentale della rappresentazione dei numeri naturali:
Data una base B (maggiore o uguale a due) ogni numero naturale n (compreso lo 0) minore di B è
associato ad un simbolo elementare detto cifra, la cui sequenza rappresenta in modo univoco i numeri
naturali maggiori o uguali a B.
Basi del linguaggio di programmazione C++
3.
Sintassi
Un programma in C++ è costituito da sequenze di parole dette token, costituiti da sequenze di:
- Digit one of 0 1 2 3 4 …
- Letter one of _ a b … z A B … Z
- Special one of ! % ^ …
Queste vengono delimitate da whitespaces (spazio, tabulazione, ritorno carrello e nuova riga), e da
comments (sequenze di parole e whitespaces comprese tra /* e */ oppure tra // e la nuova riga).
Il C++ è case sensitive e i token vengono divisi in categorie sintattiche elementari:
- Identifier i nomi assegnati a variabili, funzioni, classi… (sempre diversi dalle keyword)
- Keyword le parole chiave del linguaggio come: and while for…
- Literal denotano i valori assegnati alle variabili in fase di scrittura del codice
- Operator necessari per il calcolo delle espressioni, come: + - / …
Un operatore è caratterizzato da quattro proprietà:
▪ Posizione prefisso, postfisso o infisso (in mezzo: a + b)
▪ Arietà numero di argomenti (unario, binario o ternario)
▪ Priorità ordine di precedenza
▪ Associatività ordine di esecuzione
- Separator terminano le istruzioni, separano e raggruppano, comprendono: ; () {} …
Tipi
Si dividono in:
- Tipi fondamentali (o tipi aritmetici)
Tipi predefiniti
o ▪ Intero e naturale parte dei tipi numerici
→
▪ Reale parte dei tipi numerici
→
▪ Booleano
▪ Carattere
Tipi di enumerazione
o Costituiti da insiemi di costanti intere servono a rappresentare informazioni
non numeriche (ad esempio i colori di un semaforo).
- Tipi derivati
Si ottengono a partire dai tipi predefiniti e consentono di creare strutture dati più
complesse (reference, pointer, struct, union, array, class…)
Per eseguie certe operazioni è necessario convertire il tipo di uno o più argomenti, questo spesso
avviene in modo implicito: il compilatore decide la conversione adatta in modo da perdere la minor
quantità di dati possibili, la scelta si basa solo in base al tipo degli argomenti dell’operazione e non
considera il tipo della variabile su cui andrà il risultato.
Osservazioni:
- nella conversione tra intero e reale talvolta si può verificare una perdita di precisione perché
gli interi sono rappresentati in forma esatta e i reali in forma approssimata
- in caso di argomenti dello stesso tipo ma di lunghezza diversa, quello con lunghezza minore
viene convertito a quello di lunghezza maggiore (esempio: short int int)
→
Oggetti
Un oggetto è un gruppo di celle consecutive in memoria a cui viene attribuito un nome (identifier) e
che vengono considerate dal programmatore come un'unica cella informativa.
Ogni oggetto ha:
- Attributi ossia valore (contenuto di tutte le celle) e indirizzo della prima cella
- Tipo cioè un insieme di tutti i possibili valori che può assumere, un insieme di
operazioni consentite, e la dimensione che occupa in memoria (sizeof).
Ogni oggetto viene: Tipi derivati (esempio struct) Tipi fondamentali (esempio int)
- Dichiarato struct name; int idenftier;
- Definito struct name {field1, fiel2 …}; (inclusa nella dichiarazione)
- Inizializzato name identifier = {1, 2, 3}; identifier = 5;
Osservazioni:
- Una stessa variabile può essere dichiarata più volte nello stesso scope, ma definita una sola
volta all’interno di esso (one-definition-rule)
- Per le funzioni la dichiarazione corrisponde alla firma e al definizione al corpo, mentre
l’inizializzazione non ha senso, la cosa più logicamente vicina all’inizializzaione è la
chiamata a tale funzione, la quale ne crea un istanza inizializzata con i parametri scelti.
- Una variabile non inizializzata prende il valore che era in precedenza in memoria nelle celle
che occupa, dunque è un valore “sporco” e imprevedibile.
Stream
Detti anche flussi, necessari per la comunicazione tra l’esterno e il programma, gli stream sono una
struttura logica costituita da una sequenza di celle (byte) potenzialmente illimitata la quale termina
con una marca di fine stream. Uno stream è dotato di una variabile streamstate, un intero senza segno
su 8 bit, la quale tramite il valore dei suoi primi tre bit esprime lo stato dello stream:
- 1° - Bad bit segnala un errore non recuperabile se 1
- 2° - Eof bit segnale il raggiungimento della marca di fine stream se 1
- 3° - Fail bit segnala un errore recuperabile se 1
Lo stato di un flusso viene controllato da una serie di funzioni membro:
- fail() restituisce true se almeno uno tra fail e bad è a 1
- bad() restituisce true se il bad bit è a 1
- eof() restituisce treu se l’eof bit è a 1
- good() restituisce true se tutti i bit sono a 0
Uno stream può essere posto in una condizione, in tal caso viene chiamata la funzione fail e ne viene
restituito il complemento, dunque ponendo uno stream in una condizione questa risulta vera se non
ha errori e falsa in caso contrario. In questo caso lo stream non accetterà più operazioni fino a quando
non verrà chiamata la funzione clear(int=0) la quale riceve in argomento un intero senza segno che
rappresenta il nuovo valore dello streamstate (viene fatto or logico e assegnamento). Da tastiera non
esistono errori non recuperabili, mentre un esempio di errore recuperabile è mettere un char su un int.
Character INput (cin) è un’istanza predefinita della classe istream ed è l’unica collegata allo stream
d’ingresso, che interagisce con la tastiera (diventando effettivo solo dopo aver letto il carattere di
ritorno al carrello) o, se ridiretto in fase di compilazione, con il file specificato.
Se usato con l’operatore di traslazione a destra si ferma in caso di spazio bianco (saltando però quelli
in testa) o in caso di errore di assegnamento, mentre se usato tramite la funzione membro
cin.get(identifier) scrive sulla variabile carattere identifier anche spazi bianchi. Ci sono altre due
funzioni membro utili della classe istream: get(buf, dim, delim) che legge caratteri dallo stream e li
memorizza nel vettore buf fino ad arrivare al carattere delim o al numero di caratteri dim; e read(s,n)
che legge n byte dal flusso e li memorizza a partire dall’indirizzo contenuto in s.
Character OUTput (cout) è un istanza predefinita della classe ostream ed è l’unica collegata allo
stream di uscita, si usa con l’operatore di traslazione a sinistra e converte l’espressione argomento
dell’operatore in una sequenza di caratteri che vengono trasferiti nelle varie celle dello stream a partire
dalla prima; anche questo stream può essere ridiretto su un file. Alcune funzioni membro utili della
classe ostream sono put(c) che trasferisce il carattere c sullo stream di uscita e la funzione write(s,n)
che trasferisce la sequenza di n caratteri contenuti in s sullo stream di uscita.
La manipolazione dei file avviene tramite file-stream, gestiti dalla libreria <fstream>, associati ad
un file di percorso string (ed estensione facoltativa) tramite la funzione membro open(string, mod),
applicata ad un identifier di tipo fstream, dove mod è la modalità d’accesso e può essere:
- ios::in per la lettura, segue le regole di cin, il file deve essere già presente.
- ios::out per la scrittura (da zero), segue le regole di cout, il file se non presente
viene creato, se già presente ne sovrascrive i dati.
- ios::out | ios::app per la scrittura (in aggiunta), segue le regole di cout, il file se non presente
viene creato, se già presente non ne sovrascrive i dati ma riparte dalla
marca di fine stream precedente.
In alternativa è possibile includere solamente la libreria per la lettura <ifstream> e dunque eseguire
ifstream identifier(string) per aprire in lettura, oppure includere <ofstream> ed eseguire ofstream
identifier(string) o ofstream identifier(string, ios::app). La funzione membro che chiude lo stream
aperto e libera il file per altri processi è fstream_identifier.close(), uno stream chiuso può essere
riaperto in qualsiasi modalità ed in ogni caso tutti gli st
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.