Riassunto Dispense

 :: Riassunto Dispense ::

Un riassunto delle dispense con solo le risposte alle domande che ho trovato fin'ora negli svariati tentativi di superare l'esame e/o nel simulatore. (Forse più, forse meno, forse uguale a quanto scritto in rosso nei vari capitoli delle dispense presenti qui. In ogni caso tutto quello che c'è da sapere in unica pagina)

---

---

Capitolo 1

FBF

Una proposizione è una frase di senso compiuto che può essere vera o falsa. Il valore di verità di una fbf (formula ben formata),che può essere calcolato utilizzando le tabelle di verità, dipende dai valori di verità delle proposizioni che la compongono.
Interpretazione nella logica proposizionale: assegnamento dei valori di verità ad ogni proposizione atomica.
Una fbf può essere:

• valida: se e solo se è vera per qualsiasi interpretazione (tautologia)
• soddisfacibile: se e solo se esiste almeno un'interpretazione per cui è essa è vera

Leggi di De Morgan:

non(P e Q) = non P o non Q
non(P o Q) = non P e non Q
In generale, una formula Q segue logicamente da una formula P se e solo se ogni interpretazione che soddisfa P soddisfa anche Q. L'attività di concepire e scrivere programmi spesso richiede la dimostrazione di teoremi.

Insiemi

• Il prodotto cartesiano di due insiemi A e B ha per cardinalità il prodotto delle cardinalità, quindi ║A║ · ║B║
• L'insieme di tutte le funzioni f: A → B ha cardinalità ║B║^║A║
• L'insieme di tutti i sottoinsiemi di A ha cardinalità 2^║A║

Logica dei predicati

Un termine può essere un simbolo individuale, una variabile o una funzione. (infatti se f è una funzione n-aria e t₁,...,t_n sono termini anche f(t₁,...,t_n) è un termine)
Nella logica dei predicati del prim'ordine i quantificatori si applicano solo alle variabili libere di una formula.
La logica dei predicati si distingue dalla logica proposizionale per la presenza di variabili, simboli individuali e funzioni.

Algoritmo

Procedura passo per passo grazie alla quale un'operazione può essere svolta senza alcun esercizio di intelligenza e quindi, per esempio, da una macchina.
Deve comportare lo svolgimento in un numero finito di passaggi. Una ricetta di cucina è un esempio legittimo di algoritmo.
La complessità computazionale di un algoritmo è la quantità di risorse necessaria per la sua esecuzione. Per analizzare un algoritmo è necessario disporre di un modello della tecnologia che verrà utilizzata per realizzarlo. In genere si usa la macchina RAM, nel cui modello le istruzioni vengono eseguite una dopo l'altra, senza operazioni concorrenti, ed ogni istruzione ha il suo tempo costante di esecuzione. In generale, le risorse impiegate da un algoritmo aumentano al crescere della dimensione dei dati in ingresso. Il tempo di esecuzione di un algoritmo è dunque la somma dei tempi di esecuzione di tutti i passi eseguiti. Per misurare lo spazio utilizzato da un algoritmo su un dato ingresso, occorre considerare la quantità massima di informazione che deve essere mantenuta istante per istante durante l'esecuzione, compresi i dati d'ingresso e di uscita. La statistica che definisce la complessità di un algoritmo è il caso peggiore; il tempo di esecuzione nel caso peggiore è il più lungo tempo di esecuzione su tutti gli ingressi di dimensione n. Perchè concentrarsi sul caso peggiore?

• le risorse del caso peggiore costituiscono un limite superiore alle risorse che l'esecuzione dell'algoritmo richiederà mai.
• per alcuni algoritmi il caso peggiore si verifica abbastanza spesso.
• spesso il caso medio è tanto cattivo quanto il caso peggiore.

Quello che realmente determina la complessità di un algoritmo non è la quantità precisa di risorse che esso richiede nel caso peggiore, ma il suo tasso di crescita (ordine) al crescere delle dimensioni di ingresso. Un algoritmo è più efficiente di un altro se le risorse richieste da esso nel caso peggiore hanno un ordine più basso. Esempio:

• n log n è più efficiente di n²
• n log n e 6n log n sono equivalenti

Problemi:

• intrattabili: si conoscono solo algoritmi che li risolvono in un tempo esponenziale.
• indecidibili: non possono essere risolti in un tempo finito da alcun algoritmo e quindi da alcun programma. (es: il problema dell'arresto)

Linguaggi di programmazione

Una parola di un alfabeto è una sequenza finita di simboli dell'alfabeto. Un linguaggio è un sottoinseme delle parole costruibili su un alfabeto. Una grammatica è un insieme di regole di produzione per un linguaggio. Un linguaggio è di alto livello se è vicino al modo di ragionare di chi lo utilizza; se invece è più vicino al modo di ragionare della macchina su cui i viene eseguito si dice di basso livello.

Programmazione

Le cinque fasi della programmazione sono: specifica, progettazione, modellazione, codifica, verifica e correzione.
Specifica:
Una specifica è un quadrupla formata da insieme di ingressi, insiemi di uscite, precondizioni e postcondizioni
Progettazione:
I due approcci antitetici della progettazione sono l'analisi top-down e bottom-up.

• top-down: parte dai requisiti che devono essere soddisfatti per risolvere il problema, i quali vengono poi divisi in un numero più piccolo di sottorequisiti e così via fino a che si ottengono solo compiti elementari.
• bottom-up: parte dai compiti elementari che si sanno già risolvere combinandoli per svolgere compiti più complessi, fino a risolvere l'intero problema.

Progettazione ad oggetti: analizza il problema per identificare tutti gli elementi rilevanti che compaiono nella definizione.
Verifica e correzione:
Collaudo empirico, ossia testare il programma con dati di prova e vedere se i risultati sono sempre corretti. La scelta dei dati di prova deve rispettare la massima copertura, ossia cercare di esercitre tutte le istruzioni del programma.

Lo pseudocodice è uno strumento di modellazione della programmazione.

Documentazione

• Documentazione interna: commenti, formattazione e asserzioni
• Documentazione esterna: documenti di progetto che sono separati dal programma. (documenti di specifica, spiegazioni scritte, manuali di riferimento, schemi e diagrammi.
• manuali: corredo del programma dopo la fase di collaudo
  • manauale utente: per chi dovrà usare il programma
  • manuale di riferimento: per i programmatori che potrebbero usare il programma come compente di un sistema software più grande.

Torna su

Capitolo 2

Misura dell'informazione

L'unità di misura dell'informazione è il bit, definito come la quantità di informazione necessaria per decidere tra due alternative equiprobabili.
Per distinguere tra n alternative è necessaria una quantità di informazione pari a log₂ n bit. Quattro cifre binarie contengono 4 bit di informazione. Per rappresentare un intero n sono necessarie log₂(n+1) cifre binarie.
Overflow: il risultato di un operazione è un numero troppo grande per essere rappresentato.
L'IEEE 754 è il formato standard per la rappresentazione dei numeri a virgola mobile; i valori speciali si rappresentano così:

• zero: esponente tutto di zeri e mantissa tutta di zeri
• infinito: esponente tutto di uni e mantissa tutta di zeri
• NaN: espponente tutto di uni e mantissa non tutta di zeri

Codice ASCII: codifica i caratteri della tastiera mediante 7 cifre binarie.
Codice Unicode: codifica i caratteri secondo tre forme UTF-8, UTF-16 e UTF-32.

  Mixal

L'unità base per l'immagazzinamento dell'informazione nella macchina MIX è un byte di 6 bit. Una parola è definita come un insieme di 5 byte più un bit di segno. Specifica di campo: forma (L:R), dove L è l'indice del primo byte ed R quello dell'ultimo. S=8L+R.
Il registro rAX è costituito da 10 byte più un bit di segno.
Per realizzare un sottoprogramma senza usare lo stack: la prima istruzione del sottoprogramma è STJ USCITA, dove USCITA è il punto di uscita, contenente l'istruzione JMP *.
Se uso lo stack devo dedicare uno dei registri indice a puntatore alla cima dello stack.
Le istruzioni vengono tradotte in linguaggio macchina, le direttive no.
L'asterisco rappresenta il valore corrente del contatore di locazione.

Direttive

ORIG: specifica la locazione di memoria a partire dalla quale l'assemblatore deve cominciare ad inserire le istruzioni macchina in memoria.
EQU: definisce un simbolo e gli assegna un valore numerico.
CON: copia nella locazione di memoria corrente il risultato di un'espressione data. (serve a specificare il contenuto di una locazione di memoria)
ALF: prende un operando di 5 caratteri che costituiranno i byte di una parola da scrivere in memoria alla locazione corrente.
END: segnala la fine del programma e prende un operando che specifica la locazione di inizio per l'esecuzione del programma.

  Fine Mixal

Mappa della memoria: assegnamento di un'area di memoria a ciascun dato.
Variabile: nome simbolico di una zona di memoria allocata per contenere un dato di un certo tipo.
Heap: zona di memoria utilizzata per allocare dinamicamente spazio per i dati di un programma. Tabella: organizzazione ripetitiva di dati in memoria.
Se x è l'indirizzo della tabella e il dato base occupa s celle di memoria, l'indirizzo dell'i-esimo elemento sarà: x+ is.
Nel caso di una tabella bidimensionale m x n, l'indirizzo dell'elemento x_ij sarà: x + s(im+j).
Il modo più intuitivo per realizzare una tabella a d dimensioni è pensarla come una tabella unidimensionale di tabelle a d-1 dimensioni.
Sottoprogramma: rende un programma più compatto ma ne rallenta l'esecuzione.
Lo stack è una struttura LIFO (last in, first out); le uniche operazioni che si possono compiere su di esso sono PUSH e POP.
Ricorsione: modo di specificare un'entità in termini di sè stessa ma non in modo circolare. Il concetto di ricorsione è strettamente collegato a quello di induzione in matematica.
Base della ricorsione: definizione di un caso elementare.
Passo della ricorsione: definizione di un'entità come combinazione di parti più semplici.
Divide et Impera: consiste nello scomporre un problema in sottoproblemi dello stesso tipo più semplici da risolvere. Porta alla scrittura di programmi ricorsivi.
Interprete: programma che esegue le istruzioni di un altro programma scritto in un altro linguaggio di programmazione.
Automi: la funzione di transizione di stato dato uno stato ed un simbolo letto dice in quale stato andrà l'automa. Torna su

Capitolo 3

Programmazione strutturata

La programmazione strutturata rappresenta la naturale estensione dell'approccio top-down.
Attività di processo: compito elementare.
Attività di gestione: decisione, selezione o iterazione.
Profondità: un modulo non dovrebbe contenere più di tre livelli di strutture di controllo una dentro l'altra.
Coesione funzionale: essere volto ad ottenere un solo scopo specifico o a realizzare una ben precisa funzionalità.
I costrutti di controllo fondamentali della programmazione strutturata sono 3: esecuzione seriale, iterazione e selezione. Altro principio guida della programmazione strutturata è che ciascun modulo o blocco di codice deve avere esattamente un punto di ingresso e un punto di uscita.

Linguaggi di alto livello

I linguaggi di programmazione di alto livello sono (almeno idealmente) indipendenti dalla macchina, ossia quasi completamente portabile da una macchina all'altra. E' sufficiente ricompilarlo con il compilatore dell'altra macchina oppure farlo interpretare da un interprete del linguaggio della nuova macchina. I linguaggi di alto livello sollevano il programmatore dalla gestione della memoria.

Altri paradigmi di programmazione

• Imperativo: classico, basato su comandi
• Programmazione funzionale: valutazione di espressioni piuttosto che esecuzione di comandi
• Programmazione logica: descrivere la struttura logica piuttosto che come risolverla

Tipo di dato

Ogni entità che viene manipolata deve essere prima di tutto dichiarata

Gestione della memoria

Tutti i linguaggi di alto livello gestiscono in modo automatico l'allocazione in memoria dei dati statici.
I linguaggi di alto livello differiscono per il supporto che offrono alla gestione delle strutture dati dinamiche.

Commenti

In un programma C,C++ o Java i commenti sono delimitati dai simboli /* e */.

Variabili

C,C++ e Java sono linguaggi fortemente tipati, ossia ogni variabile o espressione ha un tipo che può essere identificato leggendo il codice in cui compare; questo serve per aiutare il programmatore ad evitare certi errori comuni. _swappa è un nome legittimo di variabile, anche se inizia con _ (underscore).

Vettori e Array

In C,C++ e Java un vettore di 10 interi si dichiara così: int x[10]. Per le tabelle si usano i vettori di vettori definiti così: int tabella[5][7].

Funzioni

Nella programmazione di alto livello i sottoprogrammi prendono il nome di procedure o funzioni.

• Procedura: sottoprogramma che prende in ingresso zero o più argomenti o parametri, li elabora e non restituisce, almeno esplicitamente, nessun risultato al programma chiamante.
• Funzione: sottoprogramma che prende in ingresso zero o più argomenti e restituisce al programma chiamante un valore che è funzione degli argomenti.

Costrutti di controllo

Un blocco di istruzioni si crea scrivendo le istruzioni una di seguito all'altra e racchiudendole tra parentesi graffe.

• while(<condizione>) <istruzione>: check della condizione, se soddisfatta eseguo l'istruzione e ricomincio.
• do <istruzione> while (<condizione>): eseguo l'istruzione almeno una volta, poi come un while normale.
• for (<set>;<condizione>;<incremento>) <istruzione>: semanticamente equivalente ad un while
• salto controllato:
  • break: interrompe l'esecuzione del ciclo e passa all'istruzione successiva
  • continue: salta alla fine del ciclo e passa all'iterazione successiva

Costrutti di selezione

• if (<condizione>) <istruzione1> else <istruzione2>: sceglie tra due alternative
• switch: sceglie tra n alternative

Eliminazione dei salti

Teorema di Bohm-Jacopini afferma che è possibile realizzare qualsiasi algoritmo senza utilizzare alcuna istruzione di salto disponendo dei tre costrutti di controllo. L'idea è di trasformare un programma con salti in un unico ciclo while contentente tanti if.
Questo teorema è una giustificazione matematica della programmazione strutturata.
Una dimostrazione alternativa di questo teorema è dovuta ad Ashcroft e Manna; si rappresenta il programma con un diagramma di flusso, il quale può essere scomposto gerarchicamente in blocchi. Un blocco è un pezzo di diagramma con esattamente una freccia di entrata ed una freccia di uscita.
Esecuzione in sequenza e costrutto while sono sufficienti per realizzare qualsiasi algoritmo.

Strutture dati

Una struttura dati è un modo sistematico di organizzare i dati utilizzati da un algoritmo e di accedere ad essi.

 

Costrutto algoritmico	Struttura dati
assegnamento	tipo elementare
sequenza	record
selezione	record con variante
iterazione	vettore
ricorsione	struttura dati dinamica

 

Correttezza dei programmi

La verifica è formale, la validazione è empirica. Tra le due quella che da maggiori garanzie è la verifica.
La validazione può solo rivelare la presenza di errori, ma non è mai in grado di garantirne l'assenza!

Validazione

Non si cercano casi di prova che si sa che il programma può superare, ma si tenta di costruire casi di prova capaci di trarre il programma in errore. Buone norme per la validazione sono: esercitare tutto il codice, provare alcuni casi tipici, provare tutti i casi atipici e provare tutti i casi limite. Test di regressione: nuova validazione di un codice in seguito a modifiche. (Solitamente si riutilizzano i casi di prova della prima validazione)

• Correttezza totale: garanzia del soddisfacimento delle specifiche per qualsiasi ingresso in un numero finito di passi.
• Correttezza parziale: garanzia che, per ogni ingresso, il programma o non termina o, se termina, produce un risultato che soddisfa le specifiche.

Lo strumento principale per dimostrare la correttezza parziale di un programma scritto in un linguaggio imperativo è la logica di Hoare.

  completare la parte sulla logica di hoare

Asserzioni

Un'asserzione è un costrutto condizionale che controlla una proprietà invariante e, nel caso in cui questa non sia verificata, produce intenzionalmente un errore di esecuzione.

• C e C++ hanno una macro predefinita: void assert (int <espressione>);
• Java ha il costrutto: assert <invariante> [: <espressione> ];

Modularità

Sistema modulare, cioè suddiviso in unità funzionali separate, chiamate moduli, chiaramente individuate e caratterizzate da un livello di complessità gestibile. Nella programmazione modularità significa identificare dei moduli semplici e ben delimitati in cui il programma può essere scomposto, in modo tale che ogni funzionalità sia confinata in un solo modulo e che le interazioni tra moduli siano il più possibile limitate e governate da convenzioni e regole certe.

Torna su

Capitolo 4

Programmazione orientata agli oggetti

La programmazione orientata agli oggetti concentra l'attenzione sui dati da manipolare piuttosto che sulle procedure.

Astrazione

Distillare un sistema complicato nei suoi costituenti più fondamentali e descrivere questi costituenti in modo semplice ma preciso.

Tipi di dati astratti

Dato astratto corrisponde al concetto di interfaccia nella programmazione orientata agli oggetti.
Un tipo di dato astratto è un modello comprendente un tipo ed un insieme associato di operazioni, definite funzioni del tipo, di cui caratterizzano il comportamento. Possiede un tipo, che è in pratica il nome che lo identifica, e definisce un insieme di operazioni, che costituiscono la sua interfaccia. Il suo dominio di applicazione è definito da assiomi e precondizioni. Un esempio di tipo di dato astratto è lo stack. Ecco un esempio di interfaccia per esso:

• PUSH: precondizione stack non negativo?! (controllare!)
• TOP: precondizione è che lo stack contenga almeno un dato (strettamente positivo)
• DROP: precondizione è che lo stack contenga almeno un dato (strettamente positivo)

Incapsulamento

Processo mediante il quale vengono definiti degli oggetti software individuali. Stretta relazione tra il concetto di incapsulamento e quello di tipo di dato astratto.
L'idea è quella di nascondere i dettagli implementativi.

Classi ed Oggetti

• Classe: automobili
• Oggetto: panda van 4x4 gialla targata AA123BB

Gli oggetti si caratterizzano per i loro attributi (nome, modello, colore, targa) e le classi per le operazioni che possono essere eseguite su di esse (accesa, spenta, ecc). Le operazioni che si possono compiere su un oggetto o su una classe si chiamano metodi.

Riuso del software

Tre metodi fondamentali:

• Librerie di componenti riusabili
• Schemi trasformazionali a spettro ristretto
• Schemi trasformazionali ad ampio spettro

Compilazione ed utilizzo di librerie, cioè repertori di componenti riusabili. Si possono prendere dei componenti presenti in libreria ed usarli così come sono o prendere un componente che si avvicina alle funzionalità richieste e modificarlo per adattarlo allo scopo.
La programmazione orientata agli oggetti è quella che meglio si presta al riuso del software, in particolare quello basato sulle librerie di componenti.

Pattern

Un pattern descrive un problema che si incontra più volte nello scrivere programmi e il nucleo della sua soluzione. In generale è costituito da:

1. Nome
2. Descrizione del problema
3. Soluzione
4. Conseguenze

Componenti

Un componente è un programma capace di svolgere qualche compito, ma che è concepito in modo da poter funzionare in diversi ambienti ed essere agganciato ad altri componenti per creare delle applicazioni complete. I componenti possono essere scritti ciascuno in un linguaggio diverso, magari orientato agli oggetti, e quindi contenere oggetti.

Programmazione orientata agli aspetti

Aspetti: punti di vista che caratterizzano un programma, ad esempio:

• compito svolto dal programma (funzionalità)
• come gestisce le anomalie
• come viene garantita la sicurezza
• come comunica con altri componenti

La programmazione orientata agli aspetti consiste nel programmare ciascuno degli aspetti nella maniera più naturale, utilizzando cioè un apposito linguaggio di descrizione dell'aspetto distinto per ciascun aspetto.
Il vantaggio è che separare i vari aspetti di un sistema produce maggiore chiarezza e aumenta la facilità di intervenire su un solo aspetto senza influenzarne altri, promuovendo così la creazione di componenti riutilizzabili.

Classi, interfacce ed oggetti in Java

Static: il metodo appartiene alla classe ma non ai suoi oggetti. This: i metodi della classe si riferiscono esplicitamente all'oggetto a cui appartengono.

Ereditarietà

L'ereditarietà è la caratteristica di un linguaggio orientato agli oggetti per cui gli oggetti di una classe ereditano tutte le proprietà (attributi, metodi, ecc.) definite per gli oggetti delle classi di livello superiore. Principio di sostituibilità di Liskov: B è un sottotipo di A se e solo se per ogni programma che usa oggetti di classe A posso usare al loro posto oggetti di classe B senza modificare il suo comportamento logico.
Due tipi di ereditarietà:

1. ereditarietà di interfaccia
2. ereditarietà di realizzazione

1. Sostanzialmente riuso del software; si riutilizza il codice definito nelle classi genitrici.
2. Compatibilità fra tipi con lo scopo di consentire il polimorfismo per inclusione.
Quando una classe ha più di una classe genitrice si parla di ereditarietà multipla.

Polimorfismo

Capacità di cose diverse di apparire nella stessa forma in un determinato contesto. (Ad esempio: se scrivo una funzione per calcolare il massimo tra due numeri interi in C, non posso poi usarla per confrontare due numeri decimali; devo scrivere una funzione identica ma con variabili di tipo diverso. Questo perchè C è basato sul concetto che le funzioni, ed i loro argomenti, siano monorfiche.)
I quattro tipi di polimorfismo classificati da Cardelli e Wegner sono:

• Overloading: stessa funzione applicabile a tipi diversi
• Coercion: argomenti di una funzione o di un operatore trasformati implicitamente nel tipo applicabile
• Parametrico: le funzioni sono parametrizzate secondo il tipo a cui possono essere applicati (alla base della programmazione generica)
• Per inclusione: un metodo può essere applicato a tutti gli oggetti inclusi nella classe che lo ammette (alla base della programmazione orientata agli oggetti)

Errori ed eccezioni

Un'eccezione è un'anomalia di funzionamento, una condizione imprevista dureante l'esecuzione di un programma. (Es: divisione per zero, aprire file non esistente, ecc.)
Java gestisce le anomalie di esecuzione con la classe predefinta Throwable e le sottoclassi Error ed Exception.
Un'eccezione può essere intercettata mediante il costrutto di controllo try ... catch.

Interfacce utente

Qualsiasi cosa permetta ad un programma di interagire con l'utente.

• Interfaccia utente a carattere (dialogo tramite il terminale)
  • guidata: menu o richieste di inserimento dati; l'utente sceglie tra un numero limitato di opzioni
  • libera: il programma espone un prompt che segnala all'utente di essere in attesa di comandi (più complicata ma molto più potente)
• Interfaccia grafica: si parla di programmazione guidata dagli eventi poichè la successione delle operazioni svolte dal programma non è predeterminata, ma dipende dalla particolare successioni degli eventi sia causati dall'utente che da altre applicazioni)

Torna su