Schemi teoria Fondamenti di informatica

PROGRAMMAZIONE della memoria ben formate

Spesso la sintassi opera a due livelli:

• Struttura: Ogni linguaggio attribuisce un significato alle frasi costruite
• Traduzione del linguaggio in linguaggio macchina: COMPILATORE

Collegamento con librerie di supporto:

• Lessicale: Libreria inclusa nel file oggetto, eseguibile stand-alone
• Grammaticale: Analisi del linguaggio di alto livello
• Contestuale: Collega i diversi moduli oggetti e il COMPILATORE

ARCHITETTURA DEL COMPILATORE:

• RAPPRESENTAZIONE INTERMEDIA: AST (Annotated Syntax Tree)
• GENERAZIONE CODICE OGGETTO: Il codice oggetto non è ancora eseguibile, un collegamento può essere statico o dinamico
• ESECUZIONE DEI PROGRAMMI: Per i PROGRAMMA COMPILATI i tre passi vengono eseguiti su Linguaggio macchina

complessità di un problema

Un problema ha una delimitazione inferiore Ω alla complessità (g(n)) se e solo se per ogni algoritmo risolutore esiste un'istanza (caso Ω peggiore) per cui il tempo di calcolo t(n) è Ω(g(n))

Il costo di un algoritmo è dato sia dallo spazio di memoria richiesto che dal tempo necessario per l'esecuzione

Una funzione f(n) ha ordine O(g(n)) se e solo se esistono due costanti positive c ed m

Gli elementi maggiori emergono rapidamente tali che:

BUBBLE SORT

Il caso peggiore si ha quando la lista è rovesciata e gli scambi sono: peggiore, però esistono anche complessità del caso medio e del caso migliore

Un algoritmo ha complessità O(g(n)) se e solo se: t(n) ha ordine O(g(n)), t(n) è il tempo di calcolo dell'algoritmo con istanza di

Ad ogni ciclo principale si seleziona il valore

dimensione nminore Sono iterativi e hanno COMPLESSITÀ:Il CASO PEGGIORE si ha quando la lista è SELECTION SORT SEMPLICIrovesciata Il numero di scambi è n-1La prima parte è ordinata, vi si inserisce unelemento alla volta, in questo caso è piùfacile trovare il posto È una ricerca fatta su un array NONIl CASO PEGGIORE si ha quando la lista è INSERTION SORT necessariamente ordinatorovesciata RICERCA LINEARE Nel caso peggiore, ovvero quando unIn media scorre solo 1/2 della prima parte elemento non è presente nella lista, ha unaCOMPLESSITÀ complessità pari a:1. Si sceglie un valore (pivot) COMPUTAZIONALE2. Si divide la lista in due parti: quella minore È una ricerca fatta su un array ordinatodel pivot e quella maggiore (si fanno n-1 PROCEDIMENTO ALGORITMI DI ORDINAMENTO RICERCA BINARIAconfronti e scambi) Nel caso peggiore, vedi sopra, ha unacomplessità pari a:3. Lo stesso algoritmo viene eseguito sulle

CASO MIGLIORE due parti (RICORSIONE)

La complessità nel CASO MIGLIORE E MEDIO è: QUICK SORT

Si ha quando la lista è rovesciata o già ordinata. Tutti gli elementi finiscono dalla stessa parte del pivot.

CASO PEGGIORE

In questo caso la complessità è: Sono ricorsivi e hanno COMPLESSITÀ: DIVIDI ET IMPERA

DIVIDE... Split, sempre a metà della lista, PROCEDIMENTO...ET IMPERA: merge sulle liste ordinate

Ogni livello di merge ha costo proporzionale a n, simile al quick sort, però non si sceglie un MERGE SORT pivot

Il CASO PEGGIORE E IL CASO MEDIO hanno complessità caratteristica di questa classe

Se si attua la FUSIONE la complessità è lineare però è richiesta molta memoria, se si fa IN PLACE è richiesta meno memoria ma aumenta la complessità

Un'immagine raster è suddivisa in una griglia di pixel, la risoluzione è data da punti per pollice (dpi)

Alcuni modelli di colore sono RGB

(RedGreen Blue), altri sono YUV (luminosità,La struttura logica determina il ruolo delle crominanza di R e G)varie parti del testo (titoli, testo, note), IMMAGINI RASTERmentre la struttura grafica assegna una resa BMPgrafica ai ruoli Compressione lossless (algoritmo diDOCUMENTI STRUTTURATIDocumenti strutturati ipertestuali, si possono compressione per cui il colore di ciascuncreare anche con Notepad pixel è mantenuto nella compressione, seavessi una linea di soli pixel bianchi vienePNGFormati di file rasterUn elemento HTML è composto da tre parti: sostituito dicendo che ci sono 20 pixeltag di apertura, contenuto e tag di chiusura bianchi), ho un'occupazione ridotta senzadeterioramentoIMMAGINI Compressione lossy (la compressione èCONTENUTI JPEGQuanti byte servono per ogni istante di maggiore ma viene introdotto del rumore)campionamento? Questo formato non è molto compresso ed è WAV MULTIMEDIALI Un'immagine è composta da un

insieme dimolto simile a quello dei DVD primitive geometriche (linee, poligoni, colori, sfumature). I lati positivi sono la qualità avarie risoluzioni, la compressione dei dati e lagestione delle modifiche

44100 x 2 (due byte sono 16 bit) x 2 (perché Byterate (ovvero quanti byte occupa un IMMAGINI VETTORIALI è stereo, se fosse stato mono avrei messo 1) secondo di audio) Ho un'onda a 44.1 kHz, su stereo a 16 bit.

PDFESEMPIO DI PROBLEMA DI CAMPIONAMENTO CAMPIONAMENTO: nel tempoDevo calcolare44100 x 16 (numero di bit) x 2 Bitrate AUDIO DIGITALE Formati vettoriali CDRQUANTIZZAZIONE: delle ampiezze DXFREGEXSIMBOLO SIGNIFICATO/EFFETTO ESEMPIOBasta mettere un'espressione Goal concatenazione di G oàCONCATENAZIONE regolare dopo l'altra a l| Unione One|two|threeIndica che ci può essere un defin.tely vuol dire cheàcarattere qualsiasi in quella sono accettate tutte quelle. posizione parola che iniziano con defin

Definiscono con tely, quindi anche definxtely. Indica che il simbolo prima goo*al viene accettato sia come gooal, che goal, che un numero da 0 a infinito di volte gooaal.

Indica che il simbolo precedente deve essere + rappresentato un numero di volte che va da 1 a infinito.

Indica che quello che è scritto goo?al o goal o gooal può essere presente o no.

Le parentesi tonde indicano (left right)*halt vuol dire che una sotto-espressione possiamo accettare halt, (left() right)halt, (left right)(leftright)halt, ecc.

Indica un raggruppamento [A-Z] sono tutte le lettere maiuscole, [0-9] sono tutte le cifre, [a-zABC] indica che prendiamo tutte le lettere maiuscole e A, B e C.

Indica un complemento, [^0-9] indica che è accettato tutto tranne le cifre, [^...] tranne quello che è scritto tra parentesi.

\d è equivalente a scrivere [0-9].

Indica tutti gli spazi bianchi, \s quindi è come

scrivere Indica tutti i caratteri che possiamo usare per programmare [0-9a-zA-Z_]. La lettera maiuscola indica il complemento, quindi questo vuol dire che prendiamo tutto tranne le cifre, possiamo fare lo stesso anche con \S, \W, ecc. Si usa quando vogliamo ad esempio \? per cercare un cercare qualcosa che ha punto interrogativo e quindi significato per le regex non per intendere il significato del ? nelle regex. Ha due significati, nelle [] vuol dire "complemento", senza le parentesi vuol dire che quello che stiamo cercando è all'inizio della frase. Vuol dire che quello che stiamo cercando è in fondo alla frase. Possiamo indicare quante \d{2} vuol dire che stiamo ripetere il simbolo prima si deve cercando due cifre.

ANALISI: modello, requisiti, fattibilità

PROGETTO ED IMPLEMENTAZIONE: componenti architetturali, dettaglio classi

CICLO DI VITA A CASCATA

Approccio paradigmatico alle specifiche

PROGETTO COLLAUDO: rispetto requisiti

qualità software

Guida per la programmazione

IMPLEMENTAZIONE RILASCIO E MANUTENZIONE: 40-80% del costo totale

Prevede l'uso di asserzioni in varie fasi di DESIGN BY CONTRACT

Interfacce con informazioni aggiuntive DOCUMENTAZIONE sviluppo:

Il DBC delimita i casi da testare COLLAUDO MANUTENZIONE PERFETTIVA Prestazioni, qualità, funzionalità

Il DBC fa emergere prima gli errori MANUTENZIONE EVOLUZIONE DI UN SOFTWARE MANUTENZIONE CORRETTIVA Anomalie ed errori

MANUTENZIONE ADATTIVA Mutamenti dell'ambiente

Le precondizioni non devono essere più forti SVILUPPO DELLe postcondizioni non devono essere più I contratti della SOTTOCLASSE devono PRINCIPIO DI SOSTITUIBILITÀ Verificabilità Sistema basato su modello formale deboli rispettare i contratti della classe base SOFTWARE Per esempio se le classi usate sono

Gli invarianti di classe non devono più deboli Riusabilità abbastanza generiche per poter essere riusate

Le specifiche sono

qualcosa di formulato, Manutenibilitàscritto, studiato e condiviso Interne: legate a quello che l'utente non vede Il sistema è in grado di interagire con più

InteroperabilitàL'infrazione di un contratto si verifica quando sistemici sono degli errori rispetto alle specifiche,quando viene violato un programma SPECIFICHE Difficoltà di portare un programma anche su

Portabilitàdobbiamo terminare il programma e risolvere Stabiliscono se è possibile chiamare un altre piattaforme