III LEZIONE : INFORMATICA

Questi sono gli appunti del corso di introduzione alla programmazione, ** ma mi raccomando sono sotto la tutela del copyright

LEZIONE III : INTRODUZIONE ALLA PROGRAMMAZIONE : Concetti preliminari.

ALGORITMO: insieme finito di istruzioni comprensibili da un esecutore che descrive in maniera chiara e non ambigua i passi elementari per raggiungere un obiettivo o risultato. Anche un ricettario di cucina altro non è che un insieme di algoritmi. Un algoritmo ha determinate caratteristiche:

1.Insieme finito di istruzioni: finitezza

2.Deve essere realizzabile: L’esecutore deve essere in grado di eseguire le istruzioni che compongono l’algoritmo con un insieme finito di risorse.

3.Deve portare ad una soluzione: Quando viene eseguito deve portare ad un risultato in un tempo finito.

4.Non ambiguo: Le istruzioni devono avere un’unica interpretazione possibile.

LE ISTRUZIONI. Un istruzione è la più piccola operazione che può essere eseguita direttamente da un esecutore. Ogni esecutore ha il suo set di istruzioni che è in grado di eseguire. Quindi a partire da un set di istruzioni che l’esecutore può eseguire si costruisce l’algoritmo. Per esempio un cuoco meno esperto ha un set di istruzioni più elementari di un cuoco più esperto.

Non tutti i problemi si possono risolvere usando gli algoritmi, per es. vincere all’enalotto. Oppure per risolvere 1 solo problema ci possono essere infiniti possibili algoritmi. In tal caso alcuni permetteranno di risolvere il problema in modo più veloce e facile. Uno dei compiti della scienza dell’informazione è mostrare che un problema può essere risolto con un algoritmo più veloce o che tale algoritmo non esiste.

ALGORITMI FORMALI: Algoritmi scritti con un linguaggio formale (linguaggio di programmazione) ed eseguibili da un sistema artificiale (calcolatore). In tale contesto l’algoritmo prende anche il nome di programma. In questo caso ci sarà una persona fisica, il programmatore scrive il programma che contiene le istruzioni immettendo dei dati di input dalla tastiera; quindi il CPU esegue le istruzioni e genera il risultato. Un esecutore del genere, in grado di eseguire algoritmi formali, è il computer.

IL SET DI ISTRUZIONI DI UN CALCOLATORE: Il set di istruzioni di un calcolatore è molto elementare. L’intelligenza sta nel programmatore che deve codificare elaborazioni più complesse.

Un processore o CPU in generale segue uno schema di lavoro: prende un’istruzione dalla memoria, la decodifica, esegue l’istruzione, quindi passa all’istruzione successiva. Nella memoria è scritto l’algoritmo che deve eseguire.

Il set di istruzioni di un processore appartiene ad un linguaggio di programmazione che si chiama “linguaggio macchina”.

Le istruzioni sono molto elementari ma scrivere un programma(algoritmo) è più oneroso.

Usando i linguaggi di programmazione per scrivere algoritmi è possibile ampliare il set di istruzioni di un CPU. Ci sono molti tipi diversi di linguaggi di programmazione:

Assembler, C, C++, C#, Java, Python, Perl, Ruby, R …

Per scrivere algoritmi formali, destinati ai calcolatori non si può infatti usare un linguaggio naturale dato che risulterebbe ambiguo(il significato delle parole varia con il contesto), ridondante(si usano parole in più non necessarie) e metaforico(si fa uso di figure retoriche che possono essere interpretate in modi diversi).

IL PROGRAMMATORE: codifica gli algoritmi in programmi (software).

L’UTILIZZATORE: installa il software e lo esegue su un calcolatore.

Un bioinformatico è sia un programmatore che un utilizzatore.

SCRIVERE UN PROGRAMMA: Consiste nel formulare l’algoritmo che risolve un determinato problema e codificarlo usando un linguaggio di programmazione. Ma anche i programmi possono essere sbagliati, ed essere soggetti a:

Errori sintattici: Il programma non è sintatticamente corretto. L’ambiente di programmazione è in grado di verificare

automaticamente se un programma rispetta la sintassi del linguaggio.

Errori semantici: Il programma sebbene sintatticamente corretto non risolve in modo corretto il problema. Il calcolatore

NON è in grado di rilevare tali errori!

+++++

La disumanità del computer sta nel fatto che, una volta programmato e messo in funzione, si comporta in maniera perfettamente onesta. (Isaac Asimov)

Bon Travail !

II LEZIONE : INFORMATICA

Continuo con questo post la discussione sui numeri in binario aggiungendo le operazioni in binario e la rappresentazione dei numeri naturali in binario.

LEZIONE II : RAPRESENTAZIONE DELL’INFORMAZIONE : aritmetica binaria.

OPERAZIONI BINARIE: le operazioni fatte tra i numeri in base 2 sono identiche a quelle fatte con i numeri in base 10, o qualsiasi altra base. Quindi anche per la base 2:

• l’addizione può generare un riporto (carry) sulla cifra di posizione immediatamente superiore.

• la sottrazione può generare un prestito (borrow) dalla cifra di posizione immediatamente superiore.

Esempi:

1 + 1 = 0 (con riporto di 1)

0 - 1 = 1 (avendo prestato 1 allo 0, 10 – 1 = 1)

SOMMA (IN BINARIO): i numeri si sommano in colonna come per i numeri in base 10: Si sommano le cifre nella stessa posizione, se la somma dà un resto esso viene trasferito alla colonna sulla sinistra.

o Esempio sommare 1100 + 101=10001 .

SOTTRAZIONE (IN BINARIO): i numeri si sottraggono in colonna come per i numeri decimali: Si sottraggono le cifre nella stessa posizione, se la cifra in altro è minore di quella in basso allora ce il prestito di una unità dalla cifra immediatamente a sinistra.

o Esempio sottrarre 1100 – 101=111 .

MOLTIPLICAZIONE (IN BINARIO): come per i numeri decimali la moltiplicazione si fa sommando i prodotti parziali: Si sommano i prodotti parziali, che risultano essere 0 o una esatta replica del moltiplicando.

o Esempio moltiplicare 1110 x 111=100010 .

DIVISIONE (IN BINARIO): come per i numeri decimali: esempio:
A =10010110₂=150₁₀
B =1100₂=12₁₀
10010110₂:1100₂
150₁₀:12₁₀

Procedimento dell'operazione:  si cerca la prima parte del dividendo che sia maggiore del divisore. Tale prima parte è nel nostro caso 10010, e dobbiamo scrivere 1 al quoziente, calcolando il resto come differenza 10010-1100. Si ottiene 110.
A questo punto "si abbassa" la cifra successiva del dividendo, cioè 1, ottenendo 1101. Il divisore 1100 "sta" nel 1101, ovviamente una volta e con resto 1.  Il quoziente diviene 11 e abbassando la cifra successiva 1 si ha 11. Questa volta il divisore "non sta" in questa parte del dividendo e quindi si aggiunge uno 0 al quoziente, abbassando la cifra successiva. Questo è l'ultimo 0, che dà 110 nel dividendo. Di nuovo il 1100 non sta nel 110 e perciò si aggiunge un altro 0 al quoziente.  Non essendoci più cifre da calare ciò significa che l'operazione è finita: quindi il quoziente è 1100₂=12₁₀,  il resto è 110₂=6₁₀.

RAPPRESENTAZIONE DEI NUMERI NATURALI:

definizione: un numero naturale è un numero intero senza segno (positivo). Esso può essere rappresentato da una stringa di bit (una combinazione di simboli di una certa lunghezza) di lunghezza fissa, fissa perché le risorse Hardware sono limitate (memorie, bus, ecc.), la conseguenza è: non tutti i numeri naturali possono essere rappresentati all’interno del calcolatore.

Quindi: un numero intero può essere rappresentato con 1 o più byte, cioè tramite stringhe di simboli di lunghezza diversa la cui unità di misura è il bit. Con 1 byte(se 1byte=8bit) posso rappresentare 2⁸=256 numeri diversi.

I multipli del bit nel sistema binario sono:

1 bit

2³=8 bit = 1 byte

2¹⁰=1024 bit = 1 Kibit (kilo)

2²⁰=1024 * 1024 bit = 1 Mibit

2³⁰=1024 * 1024 * 1024 bit = 1 Gibit

Essi sono diversi da quelli del sistema internazionale che usa la base 10, infatti: per es. la capacità di un disco fisso è 120 GB(nel S.I.)=1.2*10⁹g=111.76GiB; la capacità di un floppy è: 1.406 MiB = 1.475 MB .

Processori diversi(CPU) possono rappresentare numeri con lunghezza max diversa, in generale se n è il numero di bit utilizzati, si possono rappresentare numeri da 0 a 2ⁿ-1 (il -1 si mette perché 1 numero viene usato per indicare lo zero, restano quindi 2ⁿ-1 numeri rappresentabili diversi da zero). Se da una operazione con questi numeri ottengo un numero che è maggiore di 2ⁿ-1 (cioè più lungo del numero di bit a disposizione)ottengo un overflow.

A causa della precisione finita, gli interi elaborati dall’elaboratore non godono della proprietà di chiusura rispetto alle 4 operazioni aritmetiche.

NOTA: per fare operazioni tra numeri binari, ternari, ecc. controlla il risultato convertendo tutto in decimale !

NOTA: per trovare il primo numero che causa overflow in un registro a 4 bit: 2ⁿ-1 è il numero massimo di cifre diverse da 0 rappresentabili usando 4 bit(in totale cioè sono 2ⁿ), quindi il primo numero che causa overflow è: 2ⁿ+1 .

*****

“La teoria della vita è dunque una teoria

dell’informazione”

[Manfred Eigen, Nobel per la chimica 1967]

Bon Travail !

I LEZIONE : INFORMATICA

Con questo articolo inauguro la nuova rubrica in cui voglio inserire un po’ delle mie conoscenze di studio per la scuola e per gli esami, questo è il materiale che ho ricavato dai miei appunti, dalle lezioni seguite e dai libri. Inizio con la prima lezione di informatica

I LEZIONE: INTRODUZIONE AL SISTEMA BINARIO & SISTEMI DI NUMERAZIONE: i Sistemi posizionali.

Origini. Per sistema di numerazione si indica un insieme di simboli e di regole tramite i quali si rappresenta il concetto di numero. Un sistema di numerazione nasce dal bisogno di contare dell’uomo che risale alle sue origini. I sistemi di numerazione si dividono in: posizionali e non posizionali. Un sistema di numerazione si dice posizionale se la cifra cambia valore in base alla posizione che occupa. In un sistema non posizionale come quello romano il numero rappresentato è dato dalla somma del valore di ogni simbolo. Un sistema di numerazione non posizionale è quello dei numeri romani. Un sistema di numerazione posizionale è quello usato dai Maya, e quello che usiamo oggi. Il sistema usato dai romani è detto additivo, i numeri chiave si indicano con un simbolo, gli altri si ricavano per addizione o sottrazione. Il sistema Maya è invece vigesimale, i primi 20 numeri hanno un simbolo e da essi si ricavano tutti gli altri.

Nei sistemi di numerazione posizionali dato un numero B>1 detto base, e un insieme di simboli, detti cifre, un numero intero si rappresenta come una sequenza di n simboli (o cifre). La cifra che si trova più a sinistra è la più significativa, quella più a destra è la meno significativa. Se B=10 il sistema viene detto decimale, i suoi simboli sono 0,1,2,3,4,5,6,7,8,9 e vengono raggruppati per unità, decine, centinaia, ecc. per rappresentare i numeri. Data allora una sequenza di cifre decimali che esprimono un numero intero posso ricavare la corrispondente forma polinomia, la quale mette in evidenza il valore numerico della sequenza di cifre: a_n‐1B_n‐1+a_n‐2B_n‐2+…+a₂B₂+a₁B₁+a₀B₀ . Es. 2435 diventa: 5*10⁰+3*10¹+4*10²+2*10³ .

Per rappresentare un numero decimale razionale posso usare la stessa formula: a_n‐1B_n‐1+a_n‐2B_n‐2+…+a₂B₂+a₁B₁+a₀B₀+a_‐1B_‐1+a_‐2B_‐2+…+a_‐(m‐2)B_‐(m‐2)+ a_‐(m‐1)B_‐(m‐1)+ a_‐mB_‐m . Es. 23.42 = 2*10¹+3*10⁰+4*10^‐1+2*10^‐2 .

Riguardo ai sistemi posizionali al variare della base varia il numero di cifre utilizzabili, se B=3, le cifre sono 0,1,2. La numerazione sarà: 0 1 2 10 11 12 20 21 22… . se B=3 il sistema si dice ternario. Il sistema usato oggi nel mondo occidentale è quello decimale perché 10 è una base né troppo grande(quindi con l’uso di molti simboli) né troppo piccola(pochi simboli), anche perché 10 è il numero di dita delle mani.

I sistemi di numerazione decimali sono vantaggiosi perché:

1)      Sono compatti: cioè la lunghezza delle stringhe (parole) cresce in modo logaritmico con il crescere del valore dei numeri, per i numeri interi.

2)      Sono operativi: sulle cifre così rappresentate facilmente si possono eseguire delle operazioni aritmetiche.

SISTEMA BINARIO: se la base è 2 il sistema si dice binario. I simboli usati si dicono “bit” e sono 0,1 . Se si vuole rappresentare l’informazione (costruire un codice)2 è il numero minimo di simboli da utilizzare(cioè il supporto fisico deve avere almeno 2 diverse configurazioni), dato che deve essere B>1 . Per questo il sistema binario è il più adatto ai circuiti digitali. Anche la logica booleana usa solo 2 simboli: VERO=1 e FALSO=0 .

Allora nel sistema binario se ho 2 simboli e N è la lunghezza della stringa da usare, potrò rappresentare 2^N valori diversi. Se N=2 (2 bit) posso rappresentare 2²=4-1=3 valori diversi: 00 01 10 11 .

Posso anche affrontare il problema inverso: se conosco il numero di valori che voglio rappresentare, V, mi basterà usare la formula inversa: V=2^N cioè N=log₂V , e si arrotonda per eccesso. Es. se V=5 => N=log₂5=log5/log2=2.3=>3, infatti: 000 001 010 011 100 101 .

Lo zero non si conta!

I sistemi di numerazione posizionale si dicono completi per il teorema di divisione euclidea. Infatti il teorema garantisce che tutti i numeri naturali possono essere rappresentati in un sistema di numerazione (posizionale) a base B.

Invece la rappresentabilità dei numeri frazionali non è garantita!

Significa che alcune frazioni sono rappresentabili (con un numero finito di cifre decimali)in una base mentre non lo sono in un’altra(diventano a numero infinito di cifre decimali).

Esempi:

Il numero 1.2 (decimale) non è rappresentabile in binario

Per rappresentarlo sarebbero necessarie infinite cifre: 1.00110011…

Il numero 0.1 (ternario) non è rappresentabile in decimale

Si può rappresentare con la notazione frazionaria 1/3, che in decimale è pari

a: 0.3333…

RAPPRESENTAZIONE DI UN NUMERO: esiste una procedura universale per rappresentare un numero in un sistema posizionale a base B. Tale procedura (simile ad un algoritmo) può non terminare nel caso di numeri frazionari(=numeri frazionari a numero infinito di cifre decimali). Con tale procedura è possibile passare da una base ad un’altra. Per evitare ambiguità in presenza di più sistemi di numerazione, la sequenza appartenente ad un sistema viene denotata con la base del sistema di numerazione: per esempio, (11010)₂=(26)₁₀=(1A)₁₆ .

CONVERSIONI:

1)Base --> Decimale: Si ottiene con la forma polinomia.

2)Decimale --> Base B: Metodo delle divisioni e moltiplicazioni successive.

1)      La conversione di un numero (anche frazionario) da un sistema di numerazione a base B al sistema decimale è effettuata usando la forma polinomia: (211)₃=(2*3²+1* 3¹+1* 3⁰)₁₀= (18+3+1)₁₀= (22)₁₀ .

a_n‐1B_n‐1+a_n‐2B_n‐2+…+a₂B₂+a₁B₁+a₀B₀  : nella formula polinomia le cifre “a”, la base “B” e le operazioni sono quelle della base di arrivo, cioè decimale.

2)      Si effettua usando il metodo delle divisioni e moltiplicazioni successive. La parte intera e la parte decimale si convertono separatamente. La parte intera del numero in base B è ottenuta dividendo ripetutamente la parte intera del numero decimale per la base B (rappresentata in decimale) e registrando via via i resti delle divisioni, fino a ottenere un quoziente uguale a zero. La parte frazionaria del numero in base B è ottenuta moltiplicando ripetutamente la parte frazionaria del numero decimale per la base B e registrando la parte intera dei successivi prodotti, fino ad ottenere un prodotto pari a uno.

Le conversioni dal sistema binario e i sistemi potenze di 2 sono facilitate, es. il sistema ottale è 8=2³ , devo solo raggruppare la cifre scritte in modo binario a tre a tre a partire dal punto, e convertire in ottale ogni gruppo. La stessa regola è valida anche per tutti i sistemi che hanno basi che sono tra loro multiple o sottomultiple.

Negli altri casi, se per es. devo passare dalla base 2 alla base 3 converto prima il numero in decimale e poi faccio la conversione.

Per chiudere lascio un aforisma in inglese:

There are only 10 types
of people in the world:
those who understand binary
and those who don't.

Bon travail !