[857][A.a.2009-2010]Elementi di informatica - Cutolo

[-Manush-]

Spero di no perchè non ci ho capito un'acca! Sarebbe più facile per me imparare l'esperanto!

[fiasketta]

ma tale follia : C < 2N 2 N > log C = M , presente alla pag. 24 della prima lezione bisogna saperla?

basati sulle slide lo disse lui a lezione!

[studiandopsico]

fiasketta non ho capito il senso, scusami...io dalle slides ho letto questa formula magica...che ha detto lui a lezione?

[Winshaw89]

spiegazione di quella formula. Quando dobbiamo codificare da un alfabeto che ha un numero di simboli utilizzati (il numero di simboli utilizzati in un alfabeto è chiamato C. Per l'alfabeto binario C=2, cioè si utilizzano due simboli, che sono 0 e 1) VERSO un alfabeto binario, dobbiamo usare N bit. Come si calcola N?
Conoscendo C, con questa formula.
n>=log(base2)C



Se ad esempio dobbiamo codificare un alfabeto che ha 4 simbolit, ad esempio A B C D, ci servono
(seguendo la prima formula):
log(base2)4 >=n;
il logaritmo in base 2 di 4= 2 , cioè n >= 2. Cioè n (il numero di bit) deve essere ALMENO 2 (maggior uguale). Infatti con due bit possiamo codificare 4 cifre:

00 A
01 B
10 C
11 D

Perfetto. Il valore di log(base2)C è detto M, che indica il numero minimo di bit per la rappresentazione. A volte però vogliamo avere più bit per poter rappresentare cose in più. Cioè possiamo volere più bit di quelli che ci servono per rappresentare l'alfabeto. Possiamo utilizzare questi bit in più (ridondanti) per altri scopi, ad esempio per indicare se il numero è positivo o negativo.
QUINDI se M<N la codifica è ridondante.
(la formula C<=2^n è equivalente a quell'altra con il logaritmo).

Quindi in effetti possiamo utilizzare anche 3 o 4 bit per rappresentare un alfabeto di 4 cifre. L'importante è che siano almeno log(base2)C.

Spero di essere stato chiaro, se sono stato d'aiuto fatemi sapere.

[ilypsicocaserta]

Non la devi imparare a memoria perchè non servirebbe. La devi capire, perchè potrebbe farti la domanda se c=4 quanti bit mi servono per convertire i simboli dell'alfabeto(alfabeto inteso non quello delle lettere, ma come insieme finito di simboli,quindi può essere composto da numeri,lettere) in binario? allora la risposta è:devi fare due conti.
Se c=4 , N=2 perchè c'è scritto che N (numero di bit) deve essere maggiore o uguale al logaritmo in base 2 di C. Se non sai fare il logaritmo (come me tralaltro) fai il procedimento inverso:4 è uguale a 2 alla seconda giusto?...quindi il 2 che sta come potenza è il numero di bit che ti servono per convertire in binario. ad esempio:
Se C=8 quanti bit mi servono?ragiona così: 8=2 alla terza;quindi il numero di bit=3
Qui ad esempio C=8 si può riferire a un'alfabeto A=0,1,2,3,4,5,6,7 e con 3 bit posso rappresentare i numeri decimali da 0 a 7 (e non da 0 a 8 perchè poi sarebbero 9 numeri visto che c'è lo zero).
ad esempio:voglio rappresentare il numero quattro in bit,con C=8 lo posso rappresentare su 3 bit e quindi facendo la conversione in binario è:100 (3 bit)
non so se è chiaro. capisco che è complicato farsi capire attraverso un pc ma il concetto è semplice davvero! ciaooo

[studiandopsico]

ringrazio di vero cuore winshaw e ily che hanno risposto alla mia richiesta di aiuto, spesso mi capita di scrivere i miei problemi, ma sembra che non ci sia nessuno dall'altra parte...allora ho due cose da dirvi _
a winshaw: non riesco a capire il ruolo di m, cioè ho capito che rappresenta il log di base 2 di C, ma non va calcolato, cioè bisogna solo sapere che se è uguale a n la codifica è senza ridondanza se è minore la codifica è ridondante, giusto?
a ily: a parte che una volta li sapevo fare i log (ai tempi del liceo) ma ora non ricordo nemmeno cosa sono, cmq...non ricordavo che per fare un log bastava trarre il numero in questione in termini di potenza (tipo 8 = 2 alla terza) e la potenza indica il risultato del log. poi non ho capito quando hai fatto l'esempio della codifica sel numero 4 con c = 8 sono d'accordo che servono almeno 3 bit, ma come fai a dire 100 in binario?
scusate se insisto sulla cosa, ma voglio capire bene...e sporattutto grazie ad entrambi...

[Winshaw89]

ringrazio di vero cuore winshaw e ily che hanno risposto alla mia richiesta di aiuto, spesso mi capita di scrivere i miei problemi, ma sembra che non ci sia nessuno dall'altra parte...allora ho due cose da dirvi _
a winshaw: non riesco a capire il ruolo di m, cioè ho capito che rappresenta il log di base 2 di C, ma non va calcolato, cioè bisogna solo sapere che se è uguale a n la codifica è senza ridondanza se è minore la codifica è ridondante, giusto?
a ily: a parte che una volta li sapevo fare i log (ai tempi del liceo) ma ora non ricordo nemmeno cosa sono, cmq...non ricordavo che per fare un log bastava trarre il numero in questione in termini di potenza (tipo 8 = 2 alla terza) e la potenza indica il risultato del log. poi non ho capito quando hai fatto l'esempio della codifica sel numero 4 con c = 8 sono d'accordo che servono almeno 3 bit, ma come fai a dire 100 in binario?
scusate se insisto sulla cosa, ma voglio capire bene...e sporattutto grazie ad entrambi...

la conversione in binario, con il metodo lungo, si fa così:
(ad esempio se vogliamo convertire 8)
8: 2 = 4 con il resto di 0
4: 2= 2 con il resto di 0
2:2 = 1 conil resto di 0
1:2 = 0 con il resto di 1.


Prendi i resti dall'ultima divisione alla prima ed esce 1000 (questo è il binario di 8, non 100, che corrisponde a 4 in decimale).
Poi, un'altra cosa:


0
1
10
11
100
101
110
111
1000=8

come vedete ci vogliono 4 bit per rappresentare 8 non 3, perché? Log(base2)8=3, no?
Effettivamente per rappresentare 8 cifre ci vogliono solo 3 bit, se partiamo da 0! da 0 a 7 sono infatti 8 cifre.
-----

M è uguale esattamente a log(base2) C, ed è i lnumero minimo di bit che servono a codificare le cifre dell'alfabeto di partenza. N invece non E' il numero MINIMO, in quanto può essere anche più grande di M (cioè possiamo usare anche più bit di quelli che ci servono realmente per codificare le cifre, ad esempio possiamo usare i bit in più per identificare se il numero è pari o dispari).

Il logaritmo di un numero corrisponde alla potenza alla quale deve essere elevata la base del logaritmo per ottenere il numero del logaritmo.
Ese log(base4)16= 2, cioè devi elvare 4 alla seconda per ottenere 16.

[studiandopsico]

winshaw ti adoro,ma resti sempre disponibile fino al 4 marzo? a parte gli scherzi, già hai dato l'esame?

[Winshaw89]

finché sono cose che so spiegare non c'è problema. Non chiedetemi nulla sull'ultima slide, l'ho imparata molto sommariamente, e non ho invece capito a fondo (cioè abbastanza da poterlo spiegare) quelle cose tipo O grande, Teta grande ecc.
Devo dare l'esame fra pohi giorni :-) Ciao!

[lucastefanello]

ma dalle slide bisogna fare tutto o si deve saltare qualcosa?????

[ilypsicocaserta]

Il fatto del log lo disse il prof! quindi mi fido !allora il numero 4 lo devi convertire in binario con la regola normale: 4/2=2 con resto 0;2/2=1 con resto 0;1/2=0 con resto di 1. Leggi i resti dall'ultimo al primo e hai il numero 100!ciao!

quelle cose teta grande,o grande ecc. devi capire che sono funzioni che descrivono la complessità computazionale dell'algoritmo( cioè il suo tempo di esecuzione). allora O(g(n)) si spiega cosi:
Guarda il grafico sul libro. Ci sono due funzioni f(n) e O(g(n)). La funzione O limita una funzione qualsiasi f superiormente dal punto in cui si incontrano e ci sono i trattini vedi? Da li in poi la nostra funzione f non supererà mai la funzione O perchè è limitata superiormente da questa e si dice che questa funzione f ha una complessità migliore.
omega(g(n)) è completamente opposta. limita la funzione inferiormente dal punto in cui si incontrano ed ha una complessità peggiore.
teta(g(n)) limita una funzione f invece superiormente ed inferiormente sta al centro come puoi vedere nel grafico. Ciò che il prof ha chiesto nella simulazione d'esame è: dire che un algoritmo ha una complessità computazionale pari a omegagn vuol dire che il tempo di esecuzione dell'algoritmo è sempre maggiore di g(n). cioè la definizione sulle slide. Solo quello bisogna imparare,ma te l'ho spiegato per farti capire (credo) che significa! ciao

[vittopsmax]

Ragazzi buongiorno.. c'è qualcuno che deve fare l' esame il 28? A che punto state? A me manca l' ultima lezione che è la più difficile... qualcuno l' ha già imparata?

[Vale the singer]

raga io sto facendo le slides come penso molti!ma quella parte sui logaritmi...con tutte quelle formule è importante??

[studiandopsico]

cari ragazzi...la prima lezione l'ho fatta e capita (grazie a winshaw) poi ho saltato la seconda perchè in quel giorno non se ne scendeva proprio... quindi ho fatto la terza lezione e metà della quarta si, metà perchè mi sono venuti gli scrupoli di coscienza nei confronti della seconda lezione, ma visto che non la capisco..invoco winshaw (o chi si offre volontario) per delucidarmi sulla rappresentazione dei numeri negativi. thanks!

per non parlare dei numeri reali poi...uff...e tra l'altro bisogna ricordare tutti i vero o falso??? sto diventando pazza..

allora ragazzi, ho provato a caprici io qualcosa, se c'è qualcuno che può seguire questo mio ragionamento e ne sa qualcosa in più mi fa piacere che possa aiutarmi... credo che il compito potrebbe comprendere una domanda che dà un numero negativo e chiede di trasformarlo in binario. il procedimento è questo?
es: -7
allora prendiamo il +7 in binario ----> 0111
ogni 0 diventa 1 e ogni 1 diventa 0 ----> 1000
si aggiunge 1 ----> 1001 questo è -7, giusto?


al contrario da -7 ----> 1001
ogni 1 diventa 0 e ogni 0 diventa 1 ----> 0110
si aggiunge 1 ----> 0111 cioè +7

può andare bene così? ho letto un po' su internet e pare che sia questo il procedimento.
ora passando ai numeri decimali, sembra che sulle slides non indica un metodo per codificare un numero con la virgola in decimale, ma dice che servono 32 bit: 1 per il segno 8 per l'esponente e 23 per la mantissa. che ne dite?

infine mi interessava sapere se tutti i vero e falso presenti nella lezione 2 andavano memorizzati.
grazie a chi mi presterà attenzione, ne ho bisogno...

[Winshaw89]

abbiamo 2 tipi di codifica per i numeri negativi.

MODULO E SEGNO -> il bit più significativo indica il segno. 0=pos, 1=neg, ad esempio 1100 è -4.
Il massimo numero rappresentabile in questo caso è [-2^(k-1)-1 , +2^(k-1)-1] (ti è chiara questa formula? Perderei un po' di tempo a spiegartela, quindi se ti è chiara lascio stare, altrimenti te la spiego.)

Il problema di questo metodo è che si hanno due rappresentazioni per lo 0, cioè 1000 e 0000. Non va bene, quindi si utilizza il
COMPLEMENTO A 2
Per ottenere il numero negativo si prende il numero binario positivo, lo si fa in complemento a 1 e si aggiunge uno. Anche in questo caso il numero più significativo (quello più a sx) indica il segno= 1=negativo, 0=positivo.
(complemento a 1= se è 1 diventa 0 e viceversa). Ad esempio 0101 (5)= 1010 + 1 = 1011 (-5).
(quindi se hai un numero negativo, e lo riconosci perché la cifra significativa è 1, e vuoi capire che numero è, devo rieffettuare il complemento a 2. Cioè 1011 = (complemento a 1) 0100 + 1 (aggiungi 1 per fare il "complemento a 2) = 0101 = 5, quindi sai che prima era -5.

Il complemento a 2 è effettivamente più complesso di così (ad esempio devi sapere che devi ignorare l'overflow, e che si basa proprio su l'overflow) e quindi dovrei impiegare un bel po' a spiegare cos'è l'overflow ecc. Però non penso che queste informazioni ti servano per l'esame :-) In ogni caso la pagina di wikipedia è piuttosto chiara: http://it.wikipedia.org/wiki/Complemento_a_due

Che altro c'è nella seconda slide? Rappresentazione di numeri frazionari?


Un numero può essere scritto secondo questa formula:

N= +-M *b^e

dove M è la Mantissa, b è la base e "e" è l'esponente.

2,15
215 è la mantissa
10 è la base
-2 è l'esponente.

(la mantissa può essere anche 21,5 , 0,215 , 0,00215 o quello che volete, basta che poi esprimete adeguatamente la base e le'sponente.)
Cioè 215*10^-2 = 2.15

Tenendo conto di questo, secondo lo standard IEEE (quello utilizzato dalla maggior parte dei computer), utilizziamo per la rappresentazione di numeri frazionari 32 bit.

1 per il segno, 8 per l'esponente, 23 per la mantissa


(come ho scritto sopra, se cambiate l'esponente, la mantissa può essere scritta come volete. Giacché però questo sistema serve per levare i decimali, in genere la si scrive come un intero, cioè non 0,215 o 21,5 ma 215. Inoltre, visto che operiamo su sistemi binari, la base è 2 e non 10 come nell'esempio di sopra).
Serve altro? Le porte logiche sono estremamente semplici, non penso ci sia bisogno di aiuto lì no?

Il fatto del log lo disse il prof! quindi mi fido !allora il numero 4 lo devi convertire in binario con la regola normale: 4/2=2 con resto 0;2/2=1 con resto 0;1/2=0 con resto di 1. Leggi i resti dall'ultimo al primo e hai il numero 100!ciao!

quelle cose teta grande,o grande ecc. devi capire che sono funzioni che descrivono la complessità computazionale dell'algoritmo( cioè il suo tempo di esecuzione). allora O(g(n)) si spiega cosi:
Guarda il grafico sul libro. Ci sono due funzioni f(n) e O(g(n)). La funzione O limita una funzione qualsiasi f superiormente dal punto in cui si incontrano e ci sono i trattini vedi? Da li in poi la nostra funzione f non supererà mai la funzione O perchè è limitata superiormente da questa e si dice che questa funzione f ha una complessità migliore.
omega(g(n)) è completamente opposta. limita la funzione inferiormente dal punto in cui si incontrano ed ha una complessità peggiore.
teta(g(n)) limita una funzione f invece superiormente ed inferiormente sta al centro come puoi vedere nel grafico. Ciò che il prof ha chiesto nella simulazione d'esame è: dire che un algoritmo ha una complessità computazionale pari a omegagn vuol dire che il tempo di esecuzione dell'algoritmo è sempre maggiore di g(n). cioè la definizione sulle slide. Solo quello bisogna imparare,ma te l'ho spiegato per farti capire (credo) che significa! ciao

grazie ily, sarà che le funzioni non le ricordo proprio bene, ma mi sono trovato in difficoltà a vedere quei grafici.
Credo di aver capito in linea generale di cosa tratta :-)