Insegnamento di Informatica – a.a. 2015-16
Fondamenti di informatica
INSEGNAMENTO DI INFORMATICA – A.A. 2015-16
Francesco Ciclosi
Macerata, 7 ottobre 2015
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
Definizione
Da un punto di vista logico possiamo definire i
moderni computer come macchine o automi
di calcolo generale
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
Alan Mathison Turing
È un logico matematico inglese
Nato a Londra nel 1912
Morto nel 1954 per avvelenamento da cianuro di
potassio
È uno dei padri fondatori dell’informatica moderna
Nel 1936 pubblicherà un saggio rivoluzionario sul
funzionamento di una macchina teorica
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
Algoritmo: definizione informale
Un algoritmo è una procedura computazionale
ben definita, che viene eseguita per risolvere un
dato problema computazionale
QUINDI
È una sequenza di passi computazionali che
partendo da valori ricevuti in input, ne produce
altri in output
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
Algoritmo: definizione (più formale)
Un algoritmo è un procedimento di calcolo
esplicito
descrivibile con un numero finito di regole
che conduce al risultato dopo un numero
finito di operazioni (ovvero di applicazioni
delle regole)
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
La ricerca di Touring
Touring voleva:
1. Formalizzare la nozione di algoritmo
2. Individuare i limiti nell’applicazione dei metodi
algoritmici per la soluzione di problemi logici
matematici
Turing progetta una macchina teorica in grado
di simulare il comportamento di un uomo
intento a eseguire un calcolo aritmetico
(macchina di Touring)
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
La Macchina di Touring
È costituita da:
1. Un nastro di lunghezza potenzialmente
infinita, suddiviso in sezioni o celle
2. Un’unità di lettura e scrittura
3. Una memoria interna, che può assumere un
insieme finito di stati
4. Un insieme di simboli distinti (alfabeto della
macchina)
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
MdT – La macchina di Touring
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
Cosa può fare la macchina di Touring
1. Far scorrere il nastro avanti e indietro
2. Leggere, scrivere o cancellare i simboli (uno
alla volta) nelle celle del nastro
La macchina funziona eseguendo una
successione di passi discreti, determinato da
un insieme finito di regole
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
Le regole della MdT
Una regola indica alla MdT come comportarsi
in corrispondenza di condizioni in ingresso
IN SINTESI
Regole
MdT
Simbolo letto
Stato interno
della macchina
Simbolo da scrivere
Stato da assumere
Verso di spostamento del
nastro nel passo successivo
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
MdT e programmazione
Con le regole opportune una MdT può eseguire
calcoli di qualsiasi natura e complessità
Si può costruire una MdT universale in grado di
imitare qualsiasi MdT
• Codificando regole di trasmissione e dati di una
MdT con l’alfabeto della MdT universale
programma
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
Calcolabilità
Una MdT può risolvere qualsiasi problema
purché questo:
1. Possa essere risolto in modo algoritmico
2. Sia espresso in forma simbolica
Differenti approcci al problema della
calcolabilità forniscono tutti dei risultati
equivalenti a quelli ottenibili tramite una MdT
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
Tesi di Churc-Turing
L’insieme dei problemi effettivamente risolvibili
con qualsivoglia metodo meccanico coincide con
quello dei problemi risolvibili dalla Macchina di
Turing
Un problema non T-Calcolabile non è Calcolabile
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
La macchina a registri
a programma memorizzato
Viene elaborata nel 1945 dal matematico John
Von Neumann
Non è un modello concettuale come quello di
Touring
È usata nella progettazione dell’EDVAC, il
primo computer digitale della storia
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
Componenti della macchina a registri
Un’unità di elaborazione centrale (CPU)
Una memoria divisa in celle dotate di indirizzi
(registri)
Un nastro, diviso in celle, di ingresso (input)
Un nastro, diviso in celle, di uscita (output)
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
L’architettura di Von Neumann
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
Composizione della CPU Un’unità logico-aritmetica (ALU)
• che si occupa dell’esecuzione delle istruzioni primitive
Un accumulatore (un registro)
• per memorizzare i dati durante le operazioni di calcolo
Un’unità di controllo
• che governa l’esecuzione sequenziale delle operazioni e
coordina le componenti della macchina
Un contatore delle istruzioni
• che segnala la successiva istruzione da eseguire
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
L’architettura base di un computer
La struttura della macchina di Von Neumann
corrisponde alla struttura fisica di un computer
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
Macchina di V.N. e operazioni logiche
Dati e istruzioni primitive sono codificati con i
simboli della notazione binaria (linguaggio macchina)
Le operazioni binarie sui numeri equivalgono alle
operazioni logiche del calcolo proposizionale (algebra
di Boole)
Le operazioni possono essere semplicemente
implementate a livello fisico attraverso i
transistor (circuiti elettrici bistabili)
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
Algebra di Boole
Opera essenzialmente con i soli valori di verità 0 e 1
Permette di definire vari operatori logici
• AND (prodotto logico)
• OR (somma logica)
• NOT (negazione o complementazione)
• XOR, NAND, NOR, XNOR (operatori derivati)
la cui combinazione permette di sviluppare qualsiasi
funzione booleana
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
NOT L'operatore NOT restituisce il valore
inverso a quello in entrata
Una concatenazione di NOT è
semplificabile con
• un solo NOT in caso di ripetizioni
dispari
• nessun NOT in caso di ripetizioni pari
La porta logica NOT possiede una
sola variabile binaria
Spesso è inglobato in operatori brevi
A NOT A
0 1
1 0
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
AND ⋀
A B A AND B
0 0 0
0 1 0
1 0 0
1 1 1
Gode della proprietà
associativa
La porta logica AND è un
meccanismo comune per
avere un segnale di vero se
un certo numero di altri
segnali sono tutti veri
Nella teoria degli insiemi
corrisponde all'intersezione
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
OR ⋁
A B A OR B
0 0 0
0 1 1
1 0 1
1 1 1
Gode della proprietà
associativa
La porta logica OR è un
meccanismo comune per
avere
• un segnale alto se almeno un
segnale è alto
• un segnale basso se e solo se
tutti i segnali sono bassi
Nella teoria degli insiemi corrisponde all’unione
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
XOR ⊕ L’operatore è detto
anche EX-OR oppure
OR esclusivo
Restituisce 1 se e solo se
il numero degli operandi
uguali a 1 è dispari,
mentre restituisce 0 in
tutti gli altri casi
A B A XOR B
0 0 0
0 1 1
1 0 1
1 1 0
Nella teoria degli insiemi
corrisponde alla differenza simmetrica
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
Altri operatori (1/2)
NAND
A B A NAND B
0 0 1
0 1 1
1 0 1
1 1 0
NOR
A B A NOR B
0 0 1
0 1 0
1 0 0
1 1 0
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
Altri operatori (2/2)
XNOR
A B A XNOR B
0 0 1
0 1 0
1 0 0
1 1 1
Buffer
A Buffer A
0 0
1 1
Unimc - Dipartimento di Economia e Diritto - Corso di Laurea in Economia: banche, aziende e mercati
© Francesco Ciclosi – Settembre 2015 CC-BY-SA 4.0 – Common Deed – Legal Code
Insegnamento di Informatica – a.a. 2015-16
I miei contatti linkedin
http://it.linkedin.com/pub/francesco-ciclosi/62/680/a06/
https://www.facebook.com/francesco.ciclosi
@francyciclosi
www
http://www.francescociclosi.it
Top Related