Informatica - Programma completo

ESEMPIO

D = (rosso, verde, blu, bianco, nero)

S = (a, b, c) ab, il nome di verde c, a blu aa …

Possiamo immaginare che il nome attribuito a rosso possa essere

Le codifiche si distinguono in base alla loro lunghezza (del nome)

- Nella codifica a lunghezza fissa tutti i nomi associati agli elementi del dominio hanno la stessa

lunghezza, è la preferita perché le celle di memoria hanno una capacità fissa, ogni cella ha la

può rappresentare un’oggetto del dominio

stessa lunghezza, perciò indipendentemente da

quale.

- Nella codifica a lunghezza variabile, usata nel mondo della telecomunicazione, si accorcia il

numero di simboli da affidare agli oggetti, perciò a parità di frase si minimizza il tempo di

trasmissione. (Usa + simboli per gli oggetti meno usati, meno simboli per quelli più usati).

 n

F: D S con n = lunghezza della codifica.

- La codifica completa si ha quando si esaurisce il codominio, cioè non solo dà un nome ad

ogni oggetto del dominio, quindi per ogni oggetto del dominio esiste un nome nel codominio,

ma vengono usati tutte le possibili configurazioni di simboli del codominio.

- La codifica incompleta si ha quando esiste almeno un nome di simboli per il quale non riesco

ad associare un oggetto del dominio. 2

Se la codifica è fatta da un solo simbolo do al dominio solo un simbolo (p=1), se ho 2 simboli ho p

3

configurazioni, se ne ho 3 ho p possibili configurazioni (numero di nomi che posso costruire e

codifica a lunghezza fisica lunga n). n

Affinché funzioni serve che m sia <= di p .

n

Quando M = p gli oggetti di D sono uguali al numero di nomi possibili, quindi è una codifica

completa.

m è un vincolo di progetto, p è un vincolo tecnologico (il processore è progettato per distinguere 4



diversi tipi di alimentazione 4p), perciò questi non possono essere cambiati.

L’unica variabile è la variabile di progetto dell’informatico, che prende atto della richiesta

n,

progettuale, delle caratteristiche del processore e allora sceglie n per avere abbastanza capienza coi

nomi. n

log m <= log p

p p

n >=log M

p

deve essere l’intero superiore del logaritmo,

n se ti esce 7,6 prendi 8.

n>= n = INTSUP[log M]

1min p

Il codice Macchina, Assembly e di livello 2

Nel codice macchina servono tante istruzioni in codice binario, perciò difficili da maneggiare per

l’uomo, e se fossero da cambiare bisognerebbe ricostruire da capo il codice.

Dopo il codice macchina abbiamo il codice mnemonico o codice assembly, che ha la stessa semantica,

scrive i programmi in maniera interleggibile.

Ha il vantaggio di essere veloce, ma le codifiche sono lunghe (come quello macchina).

Per migliorarlo occorrerebbe spezzettare il file totale in piccoli file.

Arrivano i codici di livello 2, usati per cambiare il codice macchina (binario) in codici più

maneggevoli.

Abbiamo tanti moduli ASM (pezzetti del file totale) che contengono una serie di simboli che indicano

una particolare azione da eseguire.

Gli ASM vengono tradotti dall’Assembler (un software), che li converte il file oggetto (OBJ).

Dopodiché il Linker (un software) prende i file OBJ e li mette uno dietro l’altro sostituendo i

riferimenti simbolici, senza linker gli OBJ non possono essere eseguiti singolarmente perché

possiedono dipendenze incrociate.

In uscita vi è un file detto EXE, che manderemo in esecuzione (in memoria) al doppio click, perciò il

programma diventa un processo, all’interno del quale entrano gli input ed escono gli output.

Nei codici di livello 2 le azioni non sono più indicate con simboli ma sono associate ad indirizzi in

cui vengono caricati i programmi quando vengono avviati.

La compilazione e l’interpretazione

Programmi in modo simile a come ragiona l’uomo (come Python).

È molto complesso ed indipendente dalla macchina o dal sistema operativo in cui agisce, quindi

bisognerebbe cambiarlo se si cambiasse macchina.

1- Compilazione:

Formata da linguaggi compilati, caratterizzata da tanti file sorgente (come i moduli), detti C, che

vengono passati al precompilatore, che traduce ogni sorgente C in altre sorgenti C (minimalizzate).

Tutti i C vanno poi nel compilatore che li traduce e li trasforma in sorgenti ASM (assembly) che poi

si collegano all’assembler… e segue le operazioni di prima.

2- Interpretazione:

I file Python non vengono trasdotti ma vengono passati ad un programma interprete che li prende in

ingresso e li interpreta, l’esecutore li simula. (PYTHON INTERPRETER).

Per quanto riguarda le performance, nei compilati, anche se ci metti tanto a costruirli, sono poi molto

più efficienti ed affidabili, inoltre sono anche più sicuri.

Per quanto riguarda la flessibilità del linguaggio, è migliore quella degli interpretati (in Python ogni

riga viene interpretata, indipendentemente se in esecuzione o meno), inoltre sono più portatili

(capacità ad essere usabile in strutture diverse).

Tuttavia gli interpretati investono troppo tempo non nell’esecuzione del programma.

3- I linguaggi ibridi:

Linguaggi moderni che mettono insieme i pro dei compilati e degli interpretati.

Esempio dei file Java:

Ci sono tanti file Java, uniti poi nel Java Compilator che produce file detti Class simili agli OBJ, ma

sono codici macchina di una macchina virtuale, che non esiste nella realtà.

mandati in esecuzione nell’Interpreter JVM (che riceve gli input ed emana gli

I quali vengono poi

output)

Il java compilator funziona da compilatore e rende la funzione invertibile, mentre il JVM da

interprete, perciò permette di non dover cambiare il linguaggio quando si cambia la macchina.

Teoria della Complessità

Per confrontare due algoritmi e vedere quello che si comporta meglio, ovvero quale è il più semplice

e quale è il più complesso, si introduce la teoria della complessità.

Per farlo essi vengono implementati in 2 programmi, che dovranno girare generando 2 processi, che

prendono in ingresso gli input producendo risultati comportando un consumo di tempo e spazio.

Perciò viene misurato quanto ci mette e quanta memoria occupa (sperimentalmente).

Tuttavia questa tecnica può portare a dei problemi o fraintendimenti, come il linguaggio utilizzato

per implementare l’algoritmo e il livello di esperienza del programmatore.

Inoltre i processi potrebbero girare su 2 macchine diverse, che potrebbero essere più o meno veloci.

la situazione varia a seconda di come si sceglie l’input, ovvero se sono uguali o uno è più

In più

semplice da risolvere dell’altro.

Ogni problema ha un indice n che mi consente di confrontare la difficoltà dei vari casi (indice di

dell’algoritmo diminuisce al diminuire di N.

complessità), la complessità

Quindi, per determinare quale algoritmo è il migliore, si usa il:

1- Teorema dello SpeedUp Lineare

L’effetto della scelta del linguaggio e del programmatore e la differente scelta della macchina

hanno un fattore a moltiplicare costante, a parità di algoritmo implementato.

di bit accrescerà anche N, ovvero l’indice di complessità.

Ad esempio al crescere

Quindi se la macchina 1 è 10 volte più veloce della macchina 2, l’algoritmo sulla macchina 1

si risolve in un tempo 10 volte minore di quello nella macchina 2.

2- Complessità degli Input

Il confronto dei 2 algoritmi è importante quando il problema (input) da risolvere è complesso.

Se ho qualcosa che diventa sempre più difficile devo fare un’analisi al limite, ovvero per n

(indice di complessità) che tende ad infinito.

La scelta dell’algoritmo dipende quindi da N, magari si preferisce un algoritmo per N bassi

ma per N alti (distinti da un N limite) si preferisce l’altro algoritmo.

Perciò devo fare per N che tende all’infinito.

Tuttavia il programma deve essere indipendente dalle scale, ovvero devo ottenere lo stesso risultato

se andassi a dividere le prestazioni (A1 deve battere A2 anche se è in una macchina molto più lenta).

gli andamenti (concavità verso il basso o l’alto).

Ciò significa non confrontare le prestazioni ma

L’algoritmo di definisce quindi:

1- Neutralizzando la scelta del caso particolare, usando per N che va ad infinito

2- Neutralizzando la scelta di linguaggio, programmatore e macchina.

Classi di Complessità

Per caratterizzare un algoritmo uso le classi di complessità, ovvero dei funzionali, ovvero funzioni

che danno in uscita una funzione o un insieme di funzioni.

Chiamo Nnegato dove si intersecano i grafici dei due algoritmi

Il funzionale O …}

 

O {f ,f ,f

f 1 2 3   

g(x) appartiene ad O(f(x)) esistono K>0, Nnegato>0 tale che N>Nnegato g(x) =<Kf(x)

g(x) può fare quello che vuole ma da un certo punto in poi (Nnegato) deve stare sotto a f(x).

O dà in uscita l’insieme di tutte le funzioni che si comportano così.

Si dice che f(x) è un upperbound (limite superiore) per g(x).

Serve quando bisogna lavorare con problemi, non con algoritmi: se per il problema 1 conosco 3

algoritmi che lo risolvono, per il 2 altri 3 e per la prima terna vince uno e per la seconda un altro.

Ma è più facile risolvere l problema 1 o il 2?

Devo vedere quale tra i due vincenti è meno complesso (lineare, quadratico…)

Il funzionale OMEGA   

g(x) appartiene a OMEGA(f(x)) esistono K>0, Nnegato>0 tale che N>Nnegato g(x)=>Kf(x)

g(x) può fare quello che vuole ma da un certo punto in poi (Nnegato) deve stare sopra a f(x).

OMEGA dà l’insieme di tutte le funzioni che si comportano così.

Si dice che f(x) è un lowerbound (limite inferiore) per g(x).

dell’altro, l’altro

Se uno è il upperbound è il lowerbound del primo

Il funzionale TETA  

g(x) appartiene a TETA(f(x)) esistono K >0, K >0, Nnegato>0 tale che N>Nnegato

1 2

 K f(x) =< g(x) =< K f(x)

1 2

Può fare quello che vuole fino ad un certo punto (Nnegato), dove g(x) poi non può più uscire dai due

K. è l’andamento

Si dice che f(x) asintotico (o esatto) di g(x).

Esempi:

T = g(x) appartiene a TETA(N), da un certo punto in poi il tempo deve stare nello spicchio delle 2

rette K *N e K *N

1 2 2 2

T = g(x) appartiene a TETA(N ), da un certo punto in poi il tempo deve stare nelle 2 parabole K *N

1

2

e K *N

2

TETA(1) da un certo punto poi devo stare tra due rette K *1 e K *1, quindi due rette orizzontali.

1 2

Conosciamo quindi vari tipi di complessità, che cresce al crescere della loro velocit&agra