Appunti completi corso Fondamenti di Informatica

Definizione di informatica

L'informatica è la scienza che si occupa della rappresentazione dell'informazione e della sua elaborazione e gestione. Questa definizione non parla di tecnologia o programmi. Bisogna saper modellare, fare le cose in modo astratto e preventivo. La base della programmazione sono l'astrazione (o modellazione) e la creazione di algoritmi, ossia i procedimenti per creare il modello.

Programmare e linguaggi artificiali

Cos'è programmare? Scrivere programmi (sequenze di istruzioni) con un linguaggio artificiale (un linguaggio perfettamente univoco, perché il macchinario capisce solo un significato chiaro ed esplicito, non corregge gli errori con l'intuito che invece l'uomo ha, ma ha un suo vocabolario, sintassi, grammatica...), con i quali implementiamo (realizziamo) gli algoritmi (procedura eseguibile, nome dal persiano al-Khwarizmi).

Capacità del computer

Il computer non è intelligente come un umano ma può:

• Decidere se fare A o B
• Essere programmato in modo da fare azioni diverse (non fa una cosa già costruita, ma può fare tutto, in base a ciò che gli diciamo)

Algoritmi

Il persiano al-Khwarizmi ha inventato l'algoritmo, cioè il procedimento per risolvere un problema: una sequenza finita di operazioni elementari, comprensibili da un esecutore, che portano alla realizzazione di un compito. L'algoritmo quindi non è il codice, ma l'idea, il come risolvere il nostro compito. L'algoritmo ha delle istruzioni, che possono essere più o meno elementari in base al contesto. Inoltre, devono essere non-ambigui! Si considera algoritmo anche una ricetta, le istruzioni di montaggio di un elettrodomestico ecc... L'algoritmo risolve una famiglia di problemi e non una singola istanza (cioè l'esempio). L'istanza ha valori specifici, la famiglia di problemi invece contiene il tipo di problema.

Tipi di algoritmi

• Algoritmi sequenziali: procedimenti realizzati in sequenza una dopo l'altra
• Algoritmi paralleli: procedimenti realizzati contemporaneamente da più esecutori (sono difficili e particolari, si stanno diffondendo ultimamente, per farli devi avere una forma mentis ben diversa da quella sequenziale)

Umano vs. computer

Cose che gli umani fanno e i computer no e il contrario. Per esempio, i sensi umani non sono così potenti nei computer. Noi sappiamo riconoscere un viso umano subito, Facebook riconosce le facce in modo limitato. Per Facebook hanno mostrato un milione di facce e un milione di non-facce, Facebook riconosce i tratti comuni.

In sostanza:

• L'uomo ha l'intuito e capisce
• Il computer calcola e ripete

Componenti di un algoritmo

In un algoritmo ci sono:

• Azioni: cose da fare
• Punti di precedenza: ordine di esecuzione
• Punti di decisione o di controllo: decidere se fare una cosa o un'altra
• Eventualmente ripetizioni (azione derivata)

Errori comuni

• Errore strategico: errore di partenza nel progetto (pensiero strategico)
• Errore tattico: errore nel prevedere i problemi possibili (pensiero tattico)

Stato di un algoritmo

Esempio di gestione della biblioteca: prima delle azioni ci vuole la premessa introduttiva in cui si "descrive" il mondo. Insomma: quando si crea un programma bisogna prima definire i dati di partenza su cui le azioni operano. Beh c'è chi preferisce partire subito con le azioni e poi a mano a mano mette i dati... ma è meglio metterli fin da subito. Qui l'esempio è catalogare i libri con autore, nome, posizione... Ora c'è il problema: prelevare il libro. Il problema viene spezzettato in problemi più piccoli. E spesso va fatto così, perché il calcolatore non può capire un problema per intero se non spezzato in ordini più piccoli. E tra l'altro non funziona tutto al primo colpo: bisogna fare delle prove, e provare dei pezzettini di codice per volta. Questa tecnica si chiama procedimento incrementale (top-down) oppure procedimento per raffinamenti successivi (stepwise refinement). Devi fare così, in modo che se c'è un errore sai già dov'è, altrimenti se qualcosa non va devi leggere tutto il codice e ti fa andare a picco all'esame.

Efficienza ed eleganza degli algoritmi

Un algoritmo deve anche essere elegante o efficiente. L'efficienza si misura guardando il caso che richiede più tempo di risoluzione! La gran parte dei problemi della programmazione sta nel verificare tutti i casi possibili. Saranno importanti la correttezza (fare le cose giuste) e l'efficienza (tempo e memoria usati). Quando si sta per scrivere un programma, prima di tutto bisogna capire cosa bisogna fare, ovvero la richiesta.

Variabili e assegnamenti

Lo stato è la situazione delle variabili dentro il computer. I dati devono essere immagazzinati in una variabile altrimenti non vengono memorizzati e soprattutto le variabili vanno create già con un valore, prima di essere manipolate. L'assegnamento è l'operazione che cambia lo stato del mondo, ed in pratica è l'“=” dei linguaggi di programmazione. È un'istruzione (e non un'espressione che invece si ottiene con il “==” e controlla se qualcosa è vero o meno).

Concetti importanti

• Left value e right value di una variabile: è l'ordine con cui puoi scrivere un comando, a sinistra può ricevere valore e a destra può dare valore, es x = x + 1 ha senso ma non il contrario.
• Sintassi: la concatenazione corretta di un programma (l'ortografia, la grammatica del linguaggio umano).
• Semantica: il significato della frase.
• Robustezza: capacità di un algoritmo di agire correttamente anche in casi non previsti.
• Pseudo codice: la via di mezzo tra linguaggio naturale e linguaggio di programmazione (cioè l'idea generale senza i dettagli sintattici del linguaggio, esempio del MCD).
• Diagramma a blocchi: molto usato ma non mi piace, per spiegare gli algoritmi.

Ciclo di vita del software

• Analisi dei requisiti: capire a cosa serve il programma che viene creato
• Progettazione: come realizzarlo
• Implementazione: esprimere l'idea scrivendo il codice
• Verifica: controllare che il programma funziona come dovrebbe
• Manutenzione: correggere errori e applicare modifiche se necessarie

Linguaggi di alto e basso livello

Compilatori e interpreti:

• I compilatori trasformano il codice in linguaggio macchina, il C++ è un linguaggio compilato
• Gli interpreti non traducono il linguaggio macchina, ma leggono il codice e lo eseguono subito
• Le macchine virtuali sono una via di mezzo: il linguaggio è trasformato in un codice intermedio detto bytecode che poi viene interpretato

Fasi della programmazione in C++

• Videoscrittura: scrittura sull'editor del programma (asm, c, cpp, py...)
• Traduzione o compilazione: si passa dal testo al file eseguibile (obj, o)
• Linking: si collegano tutte le parti di programma per creare l'exe
• Caricamento: il programma viene caricato in memoria
• Esecuzione: il programma viene eseguito

Considerazioni sulla programmazione

Nello svolgimento degli algoritmi bisogna prevedere i casi particolari, perché quelli sono il fulcro della programmazione! Regola aurea: ogni volta che inserisci un maggiore o un minore, chiediti se non devi mettere un maggiore o uguale o un minore o uguale. Il C++ è l’evoluzione del C, quest’ultimo inventato da Ritchie nel 1972 ed è il linguaggio più usato al mondo ed è standardizzato da decenni. Il C++ è stato creato da Stroustrup negli anni '80 e lo standard attuale è del 2011. Solo alla fine del corso vedremo le differenze tra C e C++. In linea generale il C è più vicino alla struttura del calcolatore permettendo di controllare ogni aspetto del sistema, tanto che si usa per la creazione di sistemi operativi! Il C++ invece è più astratto.

Espressione e istruzione

• L'espressione è un oggetto linguistico che interpretato ritorna un valore.
• L'istruzione è un'espressione che termina con punto e virgola.

Significa che se scrivi un'espressione quella torna un valore ma viene buttato via... Gli operatori come <<, >>, = ecc... sono funzioni a tutti gli effetti e possono essere ridefiniti e vengono estratti dalle librerie incorporate nel linguaggio e preprogrammate.

Nomi e scope

I nomi possono essere di due tipi:

• Immutabili: sono pochi, nomi integrati nel linguaggio stesso, per esempio int.
• Mutabili: tutte le variabili o le funzioni, anche operatori come cout e cin, che di fatto si possono ridefinire.

Purtroppo è facile che un nome si possa riferire a più oggetti. Anche a questo servono gli scope {}, ovvero sono aree del programma in cui le variabili hanno un significato definito solo all'interno di essi. Il namespace è uno scope più grande: quel using namespace std; con cui iniziamo tutti i programmi è un modo comodo per dire a C++ che quando scrivi cout ti riferisci in realtà a std::cout.

Variabili e tipi

Le variabili sono oggetti che rappresentano porzioni di memoria atta a memorizzare dati. Sono dotate di un tipo, che definisce cosa ci si può fare con quella variabile. Ora devi stare attento a non confondere tre termini simili ma diversi che ti chiedono all'esame. Tra l'altro ogni prof attribuisce a questi termini significati diversi. Questo è il modello Fraternali:

• Dichiarazione: introdurre la variabile con il suo nome e tipo
• Inizializzazione: assegnare alla variabile il primo valore
• Definizione: dichiarazione con inizializzazione
• Assegnamento: qualsiasi assegnamento successivo al primo

Quest'altro è il modello Catallo:

• Dichiarazione: introdurre la variabile con il suo nome e tipo (senza allocazione di memoria)
• Definizione: dichiarazione con allocazione di memoria
• Inizializzazione: definizione con assegnamento di valore
• Assegnamento: qualsiasi assegnamento successivo alla definizione

Il tipo è molto importante perché il C++ è un linguaggio fortemente tipato. I letterali sono variabili che significano quello che c’è scritto.

Alto e basso livello

Che differenza c'è tra alto e basso livello? Per esempio (a+b)-(c+d) è una banalità in C++ perché sa già l'ordine con cui effettuare l'operazione. La stessa espressione in Assembly ha 21 righe e vedi chiaramente l'ordine con cui fa le operazioni. Ovvero l'alto livello nasconde dei dettagli all'utente, ai quali pensa il compilatore, ed è più sintetico e facile da capire per l'uomo: è un compromesso tra la precisione del linguaggio macchina e l'intuizione umana. Si vede chiaramente che la macchina procede sequenzialmente, mentre una macchina parallela potrebbe calcolare contemporaneamente le due addizioni.

Regole di composizione dei nomi

• Ci sono caratteri non utilizzabili
• I nomi delle variabili non possono iniziare con un numero
• Non si possono usare le parole riservate
• Maiuscolo e minuscolo sono diversi

Se dichiari le variabili in testata (cioè fuori dal main) allora quelle variabili saranno globali (valgono sia nel main che nelle altre funzioni) e non locali (che valgono solo nella funzione inserita), tuttavia si tende ad usarle il meno possibile. È possibile dichiarare tutte le variabili in testa in modo da essere facilmente rintracciabili, oppure si possono inserire nel programma appena prima di essere utilizzate. Fraternali preferisce il primo stile, Catallo invece ritiene questo sistema una cazzata e preferisce il secondo (e a mio parere ha ragione). Nota interessante: una variabile non inizializzata, se globale, viene automaticamente inizializzata con valore 0, ma non succede nulla se è locale.

Istruzioni

L'istruzione semplice è quella che termina in punto e virgola ; (detto terminatore). Senza di esso è solo un'espressione. L'istruzione composta è quella con le parentesi graffe {}. Come abbiamo visto il C++ è un linguaggio fortemente tipizzato. Tuttavia l'assegnazione dei tipi non è rigida: il compilatore può automaticamente cambiare i tipi in alcuni casi, per esempio se sommiamo un intero con un numero in virgola mobile. In questo caso si parla di tipi affini. Vedrai però che il C++ permette di fare tante cose interessanti. I tipi più frequenti sono i seguenti (è una tabella riassuntiva):

Booleano

Ha solo due valori: 0 vale falso. Tutto il resto vale vero. Perciò ritorna solo true o false. Per questo espressioni come bool a = 47 sono permesse, ma non c’è motivo di usarle. Quindi il tipo booleano è affine al tipo intero.

Carattere

Si considera carattere ogni simbolo che appartiene alla codifica ASCII. Ogni carattere è associato ad un numero che li rappresenta, perciò è un insieme ordinato. Il carattere "1" per esempio è assegnato al numero 49. La convenzione sta nella mappatura tra simboli e interi ed è tanto importante che è gestita direttamente dal sistema operativo e non dai singoli programmi. L'ASCII è la prima standardizzazione e contiene 128 caratteri (codifica a 7 bit). È per questo che se riceviamo una mail con lettere strane, allora è perché quei caratteri non sono presenti nello standard utilizzato. Gli occidentali usano l'ISO-8859 con 8 bit (256 caratteri) con tanti sottogruppi (Europa Occidentale, Europa Orientale ecc...). Quello universale è invece lo standard UNICODE che contiene tutti i caratteri del mondo con le due varianti UTF-8 e UTF-16. Ovviamente questi caratteri occupano più spazio, ma sono importanti per applicazioni destinate a funzionare in più lingue.

Interi

È il tipo più intuitivo, ma è anche molto vasto. Esistono vari modi per dichiarare un tipo intero in base alla grandezza del numero che vogliamo rappresentare e alla memoria che abbiamo a disposizione. Si può persino usare un char al posto di un intero in quanto occupa solo 1 byte (e ne consegue che caratteri e interi in C++ sono affini, ed è una caratteristica insolita)! Anche il segno occupa 1 bit di spazio: utilizzandolo dimezzi i numeri positivi che puoi usare, ma puoi usare anche quelli negativi (ed è ciò che succede automaticamente). In 8 bit senza segno vai da 0 a 255 mentre con il segno vai da -128 a +127. Per inizializzare un numero senza segno si antepone unsigned. Bisogna però essere sicurissimi che la variabile non ottenga per qualche motivo un valore negativo, altrimenti si va in overflow (si spiegherà meglio in un'altra lezione che cos'è, in sintesi si ottiene un valore sbagliato).

Float

Contiene i numeri razionali ed anche qui esistono più tipi float in base alla precisione richiesta e alla memoria a disposizione. Abbiamo detto che C++ fa delle conversioni automatiche e permette l’uso di tipi diversi nella stessa espressione. Si parla allora di cast implicito (quando effettuata in automatico dal compilatore) e di cast esplicito (quando esplicitata dall’utente nel codice).

Cast implicito

• In un’espressione con float e intero, l’intero viene promosso a float ed il risultato sarà un float;
• Una divisione tra numeri interi ritorna un numero intero;
• Nell’assegnamento, se rvalue ed lvalue hanno tipi diversi, l’rvalue deve per forza adattarsi e c’è il rischio di una perdita di informazione (esempio int i = 3.14; significa i = 3);
• Se un bool viene convertito a int, questo varrà o 0 o 1 (esempio bool b = 42; int i = b; significa i = 1);
• Non bisogna mischiare tipi signed e unsigned, perché portano al rischio di un valore negativo (e quindi all'overflow).

Cast esplicito

Il cast esplicito si può utilizzare per mezzo delle parentesi tonde: si inserisce tra parentesi tonde il tipo e poi la variabile. Eventualmente, se vogliamo convertire più di una variabile, possiamo inserirle tutte in parentesi tonde. Degli esempi: x = (double)n / m fa sì che una divisione tra interi ritorni un float, mentre float x=3, y=2; cout << (int)(x / y) ritorna un intero da una divisione tra float. Ricordati assolutamente che il cast esplicito cambia il tipo dell'espressione: se dici "della variabile" il prof ti spenna.

Precedenza degli operatori

In una espressione bisogna sapere la precedenza degli operatori e che il tipo finale dell’espressione dipende dai tipi delle variabili utilizzati e dai vari cast impliciti. Ricordati che le variabili hanno un tipo noto a priori che non cambia mai (siamo in C++). Gli operatori possono essere:

• Operatori unari: se agiscono su un singolo operando (esempio - * & ...)
• Operatori binari: se agiscono su almeno due operandi (+ - * / % = == ...)

Sulla precedenza degli operatori bisogna dire che quelli matematici seguono le regole dell’aritmetica (il % ha la stessa precedenza di moltiplicazioni e divisioni).