INFORMATICA UMANISTICA B

STORIA DELL’INFORMATICA

massimo.poesio@unitn.it

RIASSUNTO

Modelli teorici della computazione Macchine calcolatrici Modelli matematici della computazione: la

macchina di Turing Computer elettronici

I: MODELLI TEORICI DELLA COMPUTAZIONE

Un PROGRAMMA e’ un ALGORITMO posto in forma comprensibile al computer

Il nome ALGORITMO non e’ stato inventato dagli informatici ma dai matematici

Deriva dal nome del matematico persiano Muhammad ibn Mūsa 'l-Khwārizmī che attorno all’825 scrisse un trattato chiamato Kitāb al-djabr wa 'l-muqābala (Libro sulla ricomposizione e sulla riduzione) AL-KHWARIZMI ALGORISMO ALGORITMO (ALGEBRA deriva da AL-DJABR)

ALGORITMO

Definizione informale di ALGORITMO: una sequenza FINITA di passi DISCRETI e NON AMBIGUI che porta alla soluzione di un problema

UN PROBLEMA, DUE ALGORITMI: IL MASSIMO COMUN DIVISORE

MCD: UN ALGORITMO ELEMENTARE

A scuola si impara un algoritmo molto semplice per calcolare MCD: la SCOMPOSIZIONE IN FATTORI PRIMI

42 = 2 x 3 x 7 56 = 2 x 2 x 2 x 7

Algoritmo MCD(M, N):1. Scomponi M ed N in fattori primi2. Estrai i componenti comuni

Questo metodo si’ puo’ solo applicare per numeri piccoli (la scomposizione in fattori primi e’ molto costosa)

MCD: ALGORITMO DI EUCLIDE

Come vedremo piu’ avanti, i moderni calcolatori non usano l’algoritmo elementare per calcolare il MCD, ma un algoritmo molto piu’ efficiente la cui prima menzione e’ negli Elementi di Euclide, e che divenne noto agli occidentali tramite Al-Khwarizm

II: PRIME MACCHINE CALCOLATRICI

L’abaco Calcolatrici meccaniche

L’ABACO

MACCHINE CALCOLATRICI MECCANICHE

Cenni storici: IX – XIII sec. macchine complesse per automazione industriale,

in particolare industria tessile. Telaio di Jacquard, controllato da schede perforate di cartone, che rendevano automatica la lavorazione della stoffa e i disegni realizzati nello stabilimento di tessitura

Macchina per il calcolo inventata dal filosofo Pascal Macchina analitica di Charles Babbage, modello teorico, venne

costruita di recente al museo della scienza e della tecnica di Milano.

IL TELAIO A SCHEDE DI JACQUARD

LE MACCHINE DI BABBAGE

III: MODELLI MATEMATICI DELLA COMPUTAZIONE

LA MACCHINA DI TURING

Una descrizione estremamente astratta delle attivita’ del computer che pero’ cattura il suo funzionamento fondamentale

Basata su un’analisi di cosa fa un calcolatore (umano o macchina)

Le funzioni di un computer

elaborare l’informazione usando il processore (Central Processing Unit -

CPU) memorizzare l’informazione

usando la memoria principale (RAM)usando la memoria secondaria

fare l’input/output dell’informazioneusando i dispositivi di input/output

COMPUTAZIONE E MEMORIA IN UN COMPUTER

INPUT OUTPUT

MEMORIA

CPU

Istruzioni Dati

COMPUTAZIONE E MEMORIA NELLA MACCHINA DI TURING

In una macchina di Turing abbiamo: Una ‘CPU’:

Un PROGRAMMA: un insieme di regole che determinano il comportamento della testina a partire dal suo stato e dal simbolo letto (= sistema operativo)

una testina che si trova in ogni momento in uno fra un insieme limitato di stati interni e che si muove sul nastro, leggendo e se del caso modificando il contenuto delle cellette

Una ‘MEMORIA’: un nastro di lunghezza indefinita, suddiviso in cellette

che contengono simboli (ad es. ‘0’e ‘1’);

LA MACCHINA DI TURING

FUNZIONAMENTO DI UNA MACCHINA DI TURING

UNA DIMOSTRAZIONE DEL FUNZIONAMENTO DELLA MACCHINA DI TURING

http://www.warthman.com/ex-turing.htm

PROGRAMMI E DATI

Programmi: Prossima lezione: i programmi dal punto di visto

dell’hardware I programmi: sequenze di istruzioni per l’elaborazione delle

informazione Definiscono quale debba essere il comportamento del

processore Dati:

Distinzione tra dato e informazione: Dato: sequenza di bit, può essere interpretato in più modi

diversi Informazione: dato + significato del dato

MACCHINA DI TURING UNIVERSALE

Nelle macchine di Turing piu’ semplici, si trova una distinzione molto chiara tra PROGRAMMA (= gli stati) e DATI (= contenuto del nastro)

Turing pero’ dimostro’ che era possibile mettere anche il programma sul nastro, ed ottenere una macchina di Turing ‘universale’ – che LEGGEVA sul nastro la prossima istruzione da eseguire prima di leggere i DATI su cui occorreva eseguirla

I computer moderni sono macchine di Turing universali.

ALCUNI RISULTATI DIMOSTRATI USANDO IL MODELLO DI TURING

Non tutte le funzioni sono CALCOLABILI Ovvero: non e’ possibile scrivere un algoritmo per risolvere

qualunque problema in modo ESATTO ed in tempo FINITO

Il PROBLEMA DELL’ARRESTO (HALTING PROBLEM): non e’ possibile dimostrare che una macchina di Turing universale si fermera’ o no su un programma specifico

Questi risultati valgono per qualunque calcolatore, ammesso che valga la TESI DI CHURCH-TURING

DALLA MACCHINA DI TURING AI COMPUTER MODERNI

La macchina di Turing aiuta a capire come sia possibile manipolare informazione in base a un programma, leggendo e scrivendo due soli simboli: ‘0’e ‘1’

Da questo punto di vista, pur essendo un dispositivo ideale, la macchina di Turing è strettamente imparentata col computer

Dalla macchina di Turing alla macchina di von Neumann

Un passo ulteriore, volendoci avvicinare al funzionamento di un vero computer, è costituito dalla

MACCHINA DI VON NEUMANN

IV: ELETTRONICA E CALCOLATORI

Cio’ che ha permesso il passaggio a calcolatori basati sull’elettronica e’ lo sviluppo di INTERRUTTORI ELETTRONICI: Prima il TUBO A VALVOLE Poi il TRANSISTOR

Un interruttore permette di rappresentare i due stati: 1 (= passa la corrente), 0 (= non passa)

TUBI A VALVOLE

TRANSISTOR E CIRCUITI INTEGRATI

STORIA DEI COMPUTER ELETTRONICI Ispirati alla macchina di Turing

1936 Konrad Zuse costruì in casa lo Z1 usando i relè; 1941 c/o politecnico di Berlino Z3;

1942 macchina per il computo elettronico (Satanasso-Berry-Computer). La memoria erano condensatori fissati ad un grande tamburo cilindrico di 1500 bit;

1943 COLOSSUS, costruito e rimasto segreto fino al 1970. Memorizzazione di dati in aritmetica binaria basati sulla ionizzazione termica di un gas

SVILUPPO DEI CALCOLATORI ELETTRONICI

1943-46 ENIAC (Electronic Numerical Integrator and Computer) sviluppato da Eckert & Mauchly

Logica DECIMALE 30 armadi x 3m, 30t per una superficie di 180mq, 300 moltiplicazioni al

secondo fino al 1973 ritenuto il primo calcolatore elettronico ‘programmabile’

(riconnettendo i circuiti!!)

1945-49 EDVAC (Electronic Discrete Variable Automatic Computer ) Primo computer basato sull’ “Architettura di von Neumann” (dovuta a Eckert,

Mauchly & von Neumann): programmi immagazzinati in memoria Logica BINARIA

ARCHITETTURA ‘DI VON NEUMANN’

Eckert e Mauchly, dopo aver sviluppato ENIAC, proposero un modello in cui i programmi erano immagazzinati direttamente in memoria. (Mentre in ENIAC il programma doveva essere codificato direttamente in hardware). Il modello teorico che ne risulto’ – l’Architettura “di Von Neumann” influenzò direttamente la realizzazione di EDVAC (Electronic Discrete Variable Automatic Computer)

DA ZUSE A EDVAC

DOPO EDVAC

1948: primo computer commerciale (UNIVAC) 1954: primo computer a transistors (Bell Labs) ~1960: valvole sostituite da transistors 1971: primo microprocessore (Intel 4004) 1975: primo microcomputer (Altair) 1975: fondazione di Microsoft 1976: Apple I e Apple II 1979: primo Spreadsheet (VisiCalc)

PROSSIME LEZIONI

Architettura di Von Neumann Rappresentazione dei dati

LETTURE

Storia dell’Informatica http://www.dimi.uniud.it/~cicloinf/mostra/index.html Wikipedia:

http://it.wikipedia.org/wiki/Storia_dell%27informatica Wikipedia: http://it.wikipedia.org/wiki/Storia_del_computer

Paul Ceruzzi, Storia dell’Informatica, Apogeo Macchina di Turing applets

http://www.warthman.com/ex-turing.htm http://wap03.informatik.fh-wiesbaden.de/weber1/turing/tm.h

tml