Estratto del documento

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

Anteprima
Vedrai una selezione di 6 pagine su 24
Fondamenti di Informatica, appunti Pag. 1 Fondamenti di Informatica, appunti Pag. 2
Anteprima di 6 pagg. su 24.
Scarica il documento per vederlo tutto.
Fondamenti di Informatica, appunti Pag. 6
Anteprima di 6 pagg. su 24.
Scarica il documento per vederlo tutto.
Fondamenti di Informatica, appunti Pag. 11
Anteprima di 6 pagg. su 24.
Scarica il documento per vederlo tutto.
Fondamenti di Informatica, appunti Pag. 16
Anteprima di 6 pagg. su 24.
Scarica il documento per vederlo tutto.
Fondamenti di Informatica, appunti Pag. 21
1 su 24
D/illustrazione/soddisfatti o rimborsati
Acquista con carta o PayPal
Scarica i documenti tutte le volte che vuoi
Dettagli
SSD
Scienze matematiche e informatiche INF/01 Informatica

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Fggaaaghbsfhyv di informazioni apprese con la frequenza delle lezioni di Fondamenti di Informatica 2 e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Università degli Studi di Pisa o del prof Cococcioni Marco.

Domande e risposte

Hai bisogno di aiuto?
Chiedi alla community