Teoria di Informatica e Programmazione

WB.

12/10/2023

Sono i registri PC e IR che interagiscono con le istruzioni in linguaggio

macchina!

Il Registro PC (Program Counter):

• ad ogni passo conDene l’indirizzo in memoria centrale (RAM) della

prossima istruzione da eseguire

• all’inizio dell’esecuzione di un programma viene caricato con

l’indirizzo della prima istruzione di quel programma

• ad ogni istruzione eseguita, il suo contenuto viene modificato per

contenere l’indirizzo della istruzione successiva

Il Registro IR (InstrucDon Register):

• conDene l’istruzione correntemente in esecuzione da parte della

CPU

• ad ogni istruzione eseguita, il suo contenuto viene modificato per

contenere l’istruzione successiva da eseguire

Ci sono più Dpi di istruzioni possibili:

1. ISTRUZIONI DI TRASFERIMENTO

In PC si trova il numero della RAM da cui leggere l’informazione.

Dopodiché si passa al contenuto di tale ram che è un’istruzione di

trasferimento e nel mentre viene eseguita compare tale istruzione in IR.

Contemporaneamente in PC comparirà un altro numero indicante un’altra

RAM da cui prendere un’altra istruzione da eseguire subito dopo.

Come sono fa?e le istruzioni?

Budget di 32 bit per codificare l’istruzione, possiamo organizzarli come

vogliamo

8 bit per load o store

4 bit per indicare quale registro uDlizzare

20 bit per indicare quale cella di memoria ram

2a. ISTRUZIONI DI OPERAZIONI ARITMETICHE

Istruzione deve contenere info di due registri per i due operandi della

somma (per esempio)

Poi il risultato viene riscri?o su uno dei due registri argomenD, in questo

caso su Ri.

8 bit per l’operatore

4 bit dato da Ri

4 bit dato da Rj

I restanD 16 bit restano inuDlizzaD; quesD 16 non vengono usaD nel

registri perché non ci sono abbastanza registri per usare 5 o più bit per

indicare da quale registro prelevare il valore e quindi restano comunque

inuDlizzaD.

2b. ISTRUZIONE LOGICA DI CONFRONTO

Ad esempio, l’istruzione logica di confronto esamina il contenuto di due

registri per determinare se uno è maggiore o minore dell’altro.

In parDcolare, daD due registri di input Ri e Rj ed il registro RC (Registro

dei ConfronD):

• se Ri <Rj memorizza -1 in RC

• se Ri =Rj memorizza 0 in RC

• se Ri >Rj memorizza 1 in RC

3a. ISTRUZIONI DI CONTROLLO: IL SALTO

L’istruzione di controllo di salto (branch) perme?e di "saltare" ad un’altra

istruzione del programma a seconda del contenuto del registro RC.

Ovvero, a seconda del risultato di un confronto, l’istruzione di salto può

modificare il contenuto del registro PC (che conDene l’indirizzo della

prossima istruzione da eseguire).

8 bit per istruzione “branch=salto if …” di controllo

4 bit inuDlizzaD

20 bit per indirizzo ram dove inserire il dato da PC a una certa RAM

3b. ISTRUZIONI DI CONTROLLO: STOP

8 bit per scrivere SOLO 10000001 che significa STOP

L’istruzione di controllo di stop semplicemente termina il programma.

LINGUAGGIO ASSEMBLY

Consente di sosDtuire la scri?ura del binario con stringe alfanumeriche

più facilmente comprensibili e uDlizzabili.

PROBLEMA: traduzione deve essere fa?a, e quindi è stato creato

ASSEMBLER, programma sviluppato per tradurre alfanumerico in binario.

Primo linguaggio Assembly ( e relaDvo Assembler) sviluppato nel 1947 da

Kathlen Booh.

Ogni codice operaDvo (operaDon code) del linguaggio macchina viene

sosDtuito da una sequenza di cara?eri che lo rappresenta in forma

mnemonica.

I daD e gli indirizzi di memoria manipolaD dal programma vengono scril

in base numerica (esadecimale, binaria, decimale, o?ale) oppure in forma

simbolica uDlizzando stringhe di testo (idenDficatori).

Scrivere buon codice in Assembly è dispendioso in termini di tempo,

difficile, e quindi molto costoso, sopra?u?o nella prospelva di future

modifiche: per questo, la maggior parte del codice viene scri?a in un

linguaggio ad alto livello, mentre solo le parD più criDche (per moDvi di

performance, precisione del Dming o affidabilità) si scrivono in Assembly.

13/10/2023

Quando eseguiamo un programma, la CPU esegue la serie di istruzioni

che perme?ono di arrivare al risultato desiderato.

Tali istruzioni sono codificate in linguaggio macchina, dire?amente o

tramite la “traduzione” da parte di un interprete e/o di un compilatore.

Le operazioni logiche o aritmeDche vengono eseguite tramite l’impiego di

circuiX digitali (anche del circuiX logici).

Un circuito digitale è un circuito ele?ronico il cui funzionamento è basato

su un numero finito di livelli di tensione eleErica.

Essendo un sistema digitale possono assumere solo due staX: 1 (true)

oppure 0 (false), che in informaDca sono definiD variabili booleane.

I circuiD digitali sono in grado di implementare una parDcolare

operazione logica di una o più variabili booleane, ovvero di simularne la

logica matemaXca mediante opportuni controlli su segnali ele?rici.

I “ma?oncini” di base dei circuiD digitali sono le cosidde?e porte logiche,

ovvero semplici circuiD in grado di calcolare le principali operazioni

dell’algebra booleana.

Tipi base di porte logiche sono:

AND &&

OR ||

NOT ! PORTA OR ||

PORTA AND && PORTA NOT !

Non sono le uniche tabelle di verità, a parDre da queste se ne possono

codificare altre.

Porte logiche derivate:

Combinazione di AND + NOT = NAND

A NAND B = 0 se e solo se A = 1 e B = 1, 1

altrimenD → AND la cui uscita è negata

Combinazione di OR + NOT = NOR

A NOR B = 0 se A = 1 oppure B = 1, 1 altrimenD

→ equivale a un OR la cui uscita è negata

(l’output è vero solo se entrambi gli input sono

falsi)

OR esclusivo (XOR)

A XOR B = (!A && B) || (A && !B)

A XOR B = 1 se e solo se A e B hanno valori

opposD, 0 altrimenD

Combinazione di XOR + NOT = XNOR

A XNOR B = 0 se e solo se A e B hanno lo stesso

valore, 0 altrimenD

I costru?ori di CPU selezionano UN Dpo di porte tra NAND e NOR

incidendole sul silicio e usano lo stesso Xpo per tu?a la CPU al fine di

limitare i prezzi e semplificare la stru?ura. NAND e NOR hanno ciascuna

vantaggi e svantaggi e a seconda della situazioni viene scelta una piu?osto

che l’altra.

Dal punto di vista ele?ronico, le porte logiche sono realizzate con

elemenD alvi chiamaD transistor che operano come interru?ori

automaDci.

Nelle CPU i transistor sono incisi sul silicio, non si uDlizzano quesD già fal.

CIRCUITI ELETTRONICI

LEGGI DI DEMORGAN

!(A||B)=!A&&!B

è !(A&&B)=!A||!B

è

Questo es si fa per casisDche e si arriva a completare la tabella.

Espressione logica: OUT = C OR (!A AND B)

ESERCIZIO Prendo dove ho 1 in

OUT e creo le due

situazioni collegandogli

agli stessi A e B.

Successivamente collego tu?o a un OR e

me?o L’OUT.

Per visualizzare queste cosa provare su logic.ly/demo

RAPPRESENTAZIONE DEI NUMERI

2 1 0

431 = 4 * 10 + 3 * 10 + 1 * 10 scriEura polinomiale

2 1 0

(101) = 1 * 2 + 0 * 2 + 1 * 2 = (5)

2 10

Spesso si usa anche il sistema in base 8 (OTTALE) o in base 16 (HEX).

OTTALE 0-7

HEX 0-9 e A-F

TRASFORMAZIONE DA DECIMALE A BINARIA:

Se numero con virgola, parte intera si svolge con metodo di prima, parte

frazionaria si fa * 2, quando sorpasso 1 lo so?raggo. Mi fermo quando

arrivo a 0 o quando o?engo lo stesso numero già trovato. Significa che

quel numero è periodico in base 2.

La SOMMA nei numeri binari si esegue esa?amente come la somma nei

numeri in base 10.

Nella scri?ura dei numeri a virgola mobile si uDlizzano i bit nel seguente

modo:

1 bit per il segno

(tot-1)/2 bit per la manDssa

(tot-1)/2 bit per l’esponente

Il tot è il numero di bit disponibili nella CPU, 32 o 64 generalmente

19/10/2023 LE STRINGE

Le stringhe sono, insieme ai booleani, ai floats e agli integers, daX

fondamentali nella programmazione.

es. “Hello” oppure ‘Hello’.

“”” o ‘’’ per definire una stringa su più righe, con le stesse ma singole si

prende solo la riga su cui si sta scrivendo.

Stringhe si possono unire con l’operazione + e molDplicare una stringa per

un numero INTERO per ripetere n volte la stessa stringa.

Un numero scri?o in una stringa è pur sempre una stringa, non si possono

eseguire operazioni matemaDche: 2 + “2” resDtuisce un errore.

Con input , nello sezione shell inseriamo i daD e vengono riconosciuD

come stringhe. Con float e int traduco le stringhe in numeri, con e senza

virgola.

Per rappresertare i cara?eri / stringhe fu usata per la prima volta ASCII

(American Standard Code For In formaDon Interchange): una stringa è una

requenza di byte “PAROLA”con rispelvi bit.

8

Con 8 bit possono essere rappresentaD 2 = 256 cara?eri. La tabella ASCII

ne fornisce 128 dunque ve ne sono numerosi altri che possono essere

rappresentaD in diverso modo. La codifica standard ASCII perme?e la

rappresentazione di le?ere, numeri, cara?eri speciali e cara?eri di

controllo (enter, tab, ecc).

Siccome i bit disponibili sono 256, esiste anche la tabella ASCII ESTESA,

dal 128 al 255. Questa tabella perme?e di rappresentare altri cara?eri

speciali oltre alle le?ere accentate e simboli.

A?ualmente, tra emoji e altro, 256 cara?eri non bastano, ma negli anni 90

a?raverso l'UNICODE si passò ad usare + di 1 byte per associare più

cara?eri.

20/10/2023

Una stringa si definisce palindroma se la prima e la seconda metà sono

specchiabili a a b|b a a

" "la stringa VUOTA è palindroma

"_" la stringa con 1 cara?ere è palindroma

-> se è palindroma, il cara?ere 0 e n-1 sono uguali

-> se è palindroma, tolD il primo e l’ulDmo cara?ere trovo un palindromo

SE una di queste condizioni NON è verificata, allora la stringa non è

palindroma. ALGORITMI

Un matemaDco arabo dell'800 scrisse un tra?ato di matemaDca e algebra

→ l' ALGORITMO conduce da un input ben definito a un output ben

definito in un tempo finito.

È un processo ESEGUIBILE (anche su carta), PRIVO di AMBIGUITÀ e in un

tempo FINITO. Siccome i PC possono risolvere problemi allora può

eseguire algoritmi → ma non tul gli algoritmi sono eseguibili.

LISTE MATRICI TUPLE

• MATRICI • TUPLE

• LISTE Matrix = [ Tuple = (1, 2, 3, 4)

x = [1, 2, 3] [1, 2, 3],

y = [ [4, 5, 6],

"uno" [7, 8, 9]

"due" ]

]

Le matrici sono liste di liste, la visualizzazione pi&ugrav