|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.TettyRiassunto History
Hide minor edits - Show changes to output
Changed line 33 from:
* L'insieme di tutte le funzioni f: A → ha cardinalità ║B║'^║A║^' to:
* L'insieme di tutte le funzioni f: A → B ha cardinalità ║B║'^║A║^'
Changed line 33 from:
* L'insieme di tutte le funzioni f: A → ha cardinalità B║B║'^║A║^' to:
* L'insieme di tutte le funzioni f: A → ha cardinalità ║B║'^║A║^' Changed line 124 from:
Divide et Impera: consiste nello scomporre un problema in sottoproblemi dello stesso tipo più semplici da risolvere. \\ to:
Divide et Impera: consiste nello scomporre un problema in sottoproblemi dello stesso tipo più semplici da risolvere. Porta alla scrittura di programmi ricorsivi. \\ Changed line 207 from:
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. to:
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.
Changed lines 37-38 from:
Nella logica dei predicati del prim'ordine i quantificatori si applicano solo alle variabili libere di una formula. to:
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. Changed lines 175-176 from:
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.
In generale esecuzione in sequenza e costrutto while sono sufficienti per realizzare qualsiasi algoritmo. to:
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. Added line 222:
Dato astratto corrisponde al concetto di interfaccia nella programmazione orientata agli oggetti. \\
Changed lines 21-22 from:
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. L'assegnamento dei valori di verità ad ogni proposizione atomica si chiama interpretazione. to:
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. \\ Added line 101:
Se uso lo stack devo dedicare uno dei registri indice a puntatore alla cima dello stack. \\
Changed lines 100-101 from:
Le istruzioni vengono tradotte in linguaggio macchina, le direttive no. to:
Le istruzioni vengono tradotte in linguaggio macchina, le direttive no. \\
L'asterisco rappresenta il valore corrente del contatore di locazione. Added line 120:
Passo della ricorsione: definizione di un'entità come combinazione di parti più semplici. \\ Changed lines 170-171 from:
L'idea è di trasformare un programma con salti in un unico ciclo while contentente tanti if. to:
L'idea è di trasformare un programma con salti in un unico ciclo while contentente tanti if. \\
Questo teorema è una giustificazione matematica della programmazione strutturata. \\
Changed line 104 from:
CON: copia nella locazione di memoria corrente il risultato di un'espressione data. \\ to:
CON: copia nella locazione di memoria corrente il risultato di un'espressione data. (serve a specificare il contenuto di una locazione di memoria) \\ Added line 114:
Il modo più intuitivo per realizzare una tabella a d dimensioni è pensarla come una tabella unidimensionale di tabelle a d-1 dimensioni. \\
Changed line 187 from:
to:
Added lines 98-99:
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 *. \\
Added line 115:
Base della ricorsione: definizione di un caso elementare. \\
Added lines 96-98:
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.\\
Le istruzioni vengono tradotte in linguaggio macchina, le direttive no.
Added line 97:
ORIG: specifica la locazione di memoria a partire dalla quale l'assemblatore deve cominciare ad inserire le istruzioni macchina in memoria. \\ Added lines 100-101:
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.
Added lines 96-99:
!!!! Direttive
EQU: definisce un simbolo e gli assegna un valore numerico. \\
CON: copia nella locazione di memoria corrente il risultato di un'espressione data. \\
%warning% '''Fine Mixal'''
Added lines 102-107:
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. \\
Divide et Impera: consiste nello scomporre un problema in sottoproblemi dello stesso tipo più semplici da risolvere. \\
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.
Changed line 96 from:
La mappa della memoria è \\\
to:
Mappa della memoria: assegnamento di un'area di memoria a ciascun dato. \\
Changed lines 95-101 from:
to:
%warning% '''Mixal'''
La mappa della memoria è \\\
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).\\
Changed line 95 from:
to:
Added lines 87-95:
Per rappresentare un intero ''n'' sono necessarie log'_2_'(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.
%warnig% Mixal
Changed line 86 from:
to:
Quattro cifre binarie contengono 4 bit di informazione.
Changed lines 85-86 from:
Per distinguere tra ''n'' alternative è necessaria una quantità di informazione pari a log'_2_' '''n''' bit. to:
Per distinguere tra ''n'' alternative è necessaria una quantità di informazione pari a log'_2_' ''n'' bit.
Added lines 83-85:
!!!! 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'_2_' '''n''' bit.
Changed lines 241-244 from:
* Interfaccia utente a carattere
** guidata
** libera
* Interfaccia grafica to:
* 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)
Added lines 235-244:
!!!! 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
** guidata
** libera
* Interfaccia grafica
Changed lines 231-234 from:
* Overloading:
* Coercion:
* Parametrico:
* [[#polimorfismo]] Per inclusione: to:
* 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)
* [[#polimorfismo]] Per inclusione: un metodo può essere applicato a tutti gli oggetti inclusi nella classe che lo ammette (alla base della programmazione orientata agli oggetti)
Changed line 225 from:
2. Compatibilità fra tipi con lo scopo di consentire il [[#polimorfismo | polimorfismo per inclusione.]] \\ to:
2. Compatibilità fra tipi con lo scopo di consentire il [[#polimorfismo | polimorfismo per inclusione]]. \\ Added lines 228-234:
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:
* Coercion:
* Parametrico:
* [[#polimorfismo]] Per inclusione:
Changed lines 225-227 from:
2. Compatibilità fra tipi con lo scopo di consentire il [[#polimorfismo | [polimorfismo per inclusione.]]] to:
2. Compatibilità fra tipi con lo scopo di consentire il [[#polimorfismo | polimorfismo per inclusione.]] \\
Quando una classe ha più di una classe genitrice si parla di ereditarietà multipla.
!!!! Polimorfismo
Changed line 208 from:
Aspetti: punti di vista cge caratterizzano un programma, ad esempio: to:
Aspetti: punti di vista che caratterizzano un programma, ad esempio: Added lines 215-225:
!!!! 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à:
# ereditarietà di interfaccia
# 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 | [polimorfismo per inclusione.]]]
Added lines 207-215:
!!!! Programmazione orientata agli aspetti
Aspetti: punti di vista cge 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.
\\
Changed lines 193-198 from:
# Librerie di componenti riusabili
# Schemi trasformazionali a spettro ristretto
# Schemi trasformazionali ad ampio spettro
1. 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.
2. & 3.
to:
* 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:
# Nome
# Descrizione del problema
# Soluzione
# 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.
Added lines 191-197:
!!!! Riuso del software
Tre metodi fondamentali:
# Librerie di componenti riusabili
# Schemi trasformazionali a spettro ristretto
# Schemi trasformazionali ad ampio spettro
1. 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.
2. & 3.
Changed lines 180-182 from:
to:
* 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'''.
Added lines 175-183:
!!!! Tipi di dati astratti
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:
* TOP:
* DROP:
Added lines 171-174:
!!!! 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.
Changed line 159 from:
%warning% completare la parte sulla logica di hoare to:
%warning% completare la parte sulla logica di hoare
Changed line 164 from:
to:
Changed lines 149-166 from:
to:
!!!! 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.
%warning% 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.
Changed lines 133-134 from:
Una struttura dati è un modo sistematico di organizzare i dati utilizzati da un algoritmo e di accedere ad essi. to:
Una struttura dati è un modo sistematico di organizzare i dati utilizzati da un algoritmo e di accedere ad essi.\\\
Changed lines 138-147 from:
(:cellnr:) assegnamento
(:cell:) tipo elementare
(:cellnr:) sequenza
(:cell:) record
(:cellnr:) selezione
(:cell:) record con variante
(:cellnr:) iterazione
(:cell:) vettore
(:cellnr:) ricorsione
(:cell:) struttura dati dinamica to:
(:cellnr align=center:) assegnamento
(:cell align=center:) tipo elementare
(:cellnr align=center:) sequenza
(:cell align=center:) record
(:cellnr align=center:) selezione
(:cell align=center:) record con variante
(:cellnr align=center:) iterazione
(:cell align=center:) vettore
(:cellnr align=center:) ricorsione
(:cell align=center:) struttura dati dinamica
Changed line 133 from:
Una struttura dati è un modo sistematico di organizzare i dati utilizzati da un algoritmo e di accedere ad essi. \\\ to:
Una struttura dati è un modo sistematico di organizzare i dati utilizzati da un algoritmo e di accedere ad essi. Changed lines 135-136 from:
(:head:) Costrutto algoritmico
(:head:) Struttura dati to:
(:head align=center:) Costrutto algoritmico
(:head align=center:) Struttura dati
Changed lines 135-136 from:
(:head align=center:) Costrutto algoritmico
(:head align=center:) Struttura dati to:
(:head:) Costrutto algoritmico
(:head:) Struttura dati
Changed lines 136-137 from:
(:head:) Struttura dati
(:cellnr align=center:) assegnamento to:
(:head align=center:) Struttura dati
(:cellnr:) assegnamento Changed line 139 from:
(:cellnr align=center:) sequenza to:
Changed line 141 from:
(:cellnr align=center:) selezione to:
Changed line 143 from:
(:cellnr align=center:) iterazione to:
Changed line 145 from:
(:cellnr align=center:) ricorsione to:
Changed line 136 from:
(:head align=center:) Struttura dati to:
Changed line 138 from:
(:cell align=center:) tipo elementare to:
Changed line 140 from:
(:cell align=center:) record to:
Changed line 142 from:
(:cell align=center:) record con variante to:
(:cell:) record con variante Changed line 144 from:
(:cell align=center:) vettore to:
Changed line 146 from:
(:cell align=center:) struttura dati dinamica to:
(:cell:) struttura dati dinamica
Changed lines 133-146 from:
Una struttura dati è un modo sistematico di organizzare i dati utilizzati da un algoritmo e di accedere ad essi.
(:table border=1 cellpadding=5 cellspacing=0:)
(:head:) Costrutto algoritmico
(:head:) Struttura dati
(:cellnr:) assegnamento
(:cell:) tipo elementare
(:cellnr:) sequenza
(:cell:) record
(:cellnr:) selezione
(:cell:) record con variante
(:cellnr:) iterazione
(:cell:) vettore
(:cellnr:) ricorsione
(:cell:) struttura dati dinamica to:
Una struttura dati è un modo sistematico di organizzare i dati utilizzati da un algoritmo e di accedere ad essi. \\\
(:table border=1 cellpadding=5 cellspacing=0 align=center:)
(:head align=center:) Costrutto algoritmico
(:head align=center:) Struttura dati
(:cellnr align=center:) assegnamento
(:cell align=center:) tipo elementare
(:cellnr align=center:) sequenza
(:cell align=center:) record
(:cellnr align=center:) selezione
(:cell align=center:) record con variante
(:cellnr align=center:) iterazione
(:cell align=center:) vettore
(:cellnr align=center:) ricorsione
(:cell align=center:) struttura dati dinamica
Added lines 139-146:
(:cellnr:) sequenza
(:cell:) record
(:cellnr:) selezione
(:cell:) record con variante
(:cellnr:) iterazione
(:cell:) vettore
(:cellnr:) ricorsione
(:cell:) struttura dati dinamica
Changed line 137 from:
to:
Changed lines 137-139 from:
to:
(:cell:) assegnamento
(:cell:) tipo elementare
(:tableend:)
Changed lines 134-140 from:
||border="1" bordercolordark="black"
bordercolorlight="black"
style="border-collapse:collapse"
cellpadding="5" width=66%
||!Header || !Header|| '''Header'''||
||cells || with || padding||
|| || || ||
to:
(:table border=1 cellpadding=5 cellspacing=0:)
(:head:) Costrutto algoritmico
(:head:) Struttura dati
Added lines 133-141:
Una struttura dati è un modo sistematico di organizzare i dati utilizzati da un algoritmo e di accedere ad essi.
||border="1" bordercolordark="black"
bordercolorlight="black"
style="border-collapse:collapse"
cellpadding="5" width=66%
||!Header || !Header|| '''Header'''||
||cells || with || padding||
|| || || ||
Added line 129:
L'idea è di trasformare un programma con salti in un unico ciclo while contentente tanti if. Added line 131:
In generale esecuzione in sequenza e costrutto while sono sufficienti per realizzare qualsiasi algoritmo.
Changed lines 117-130 from:
to:
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.
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.
!!!! Strutture dati
Added lines 113-117:
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
Changed lines 94-112 from:
to:
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
Deleted line 9:
Changed lines 82-98 from:
to:
!!! Capitolo 2
[[#top|[-'''Torna su'''-]]]
[[#c2]]
!!! 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
[[#top|[-'''Torna su'''-]]]
[[#c3]]
!!! Capitolo 4
[[#top|[-'''Torna su'''-]]]
Added line 2:
Changed lines 80-81 from:
** manuale di riferimento: per i programmatori che potrebbero usare il programma come compente di un sistema software più grande. \\\ to:
** manuale di riferimento: per i programmatori che potrebbero usare il programma come compente di un sistema software più grande.
[[#top|[-'''Torna su'''-]]]
Deleted lines 3-4:
%warning% Lavori in corso
Added lines 5-17:
----
[[<<]]
>>left bgcolor=#f5f9fc width=215px border='2px solid #cccccc' padding=5px<<
%center%'''Indice'''
# [[#c0|Capitolo 1]]
# [[#c1|Capitolo 2]]
# [[#c2|Capitolo 3]]
# [[#c3|Capitolo 4]]
>><<
----
[[#c0]] Added line 80:
Changed lines 59-69 from:
Progettazione ad oggetti: analizza il problema per identificare tutti gli elementi rilevanti che compaiono nella definizione. to:
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. \\\
!!! Capitolo 2
Changed lines 52-55 from:
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: to:
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: \\
Changed lines 56-59 from:
I due approcci antitetici della progettazione sono l'analisi top-down e bottom-up to:
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.
Changed lines 42-56 from:
* n log n e 6n log n sono equivalenti to:
* 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
Changed lines 3-5 from:
to:
%warning% Lavori in corso Changed lines 29-42 from:
La complessità computazionale di un algoritmo è la quantità di risorse necessaria per la sua esecuzione. to:
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'^2^'
* n log n e 6n log n sono equivalenti
Changed lines 4-5 from:
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.
!! Capitolo 1 to:
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 -> Uni.ProgrammazioneElaboratori]]. In ogni caso tutto quello che c'è da sapere in unica pagina)
!!! Capitolo 1
!!!! FBF Changed line 12 from:
to:
Added line 17:
Changed lines 20-27 from:
* L'insieme di tutti i sottoinsiemi di A ha cardinalità 2'^║A║^' to:
* 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'_1_',...,t'_n_' sono termini anche f(t'_1_',...,t'_n_') è un termine) \\
Nella logica dei predicati del prim'ordine i quantificatori si applicano solo alle variabili libere di una formula.
!!!! 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.
Changed lines 16-18 from:
*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 → ha cardinalità B║B║'^║A║^'\\
*L'insieme di tutti i sottoinsiemi di A ha cardinalità 2'^║A║^'\\ to:
* 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 → ha cardinalità B║B║'^║A║^'
* L'insieme di tutti i sottoinsiemi di A ha cardinalità 2'^║A║^' \\
Changed lines 10-18 from:
* soddisfacibile: se e solo se esiste almeno un'interpretazione per cui è essa è vera to:
* 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.
*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 → ha cardinalità B║B║'^║A║^'\\
*L'insieme di tutti i sottoinsiemi di A ha cardinalità 2'^║A║^'\\
Changed lines 2-3 from:
%titolo%''':: Riassunto Dispense ::'''
!! Capitolo 1 to:
%titolo%''':: 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.
!! Capitolo 1
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. L'assegnamento dei valori di verità ad ogni proposizione atomica si chiama interpretazione.
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
Changed lines 2-3 from:
%titolo% :: Riassunto Dispense :: to:
%titolo%''':: Riassunto Dispense ::'''
!! Capitolo 1
Changed line 2 from:
to:
%titolo% :: Riassunto Dispense ::
Changed line 1 from:
to:
(:title Riassunto Dispense:)
Added lines 1-2:
(:Riassunto Dispense:)
::Riassunto Dispense::
|
|
