INFORMATICA

Universita' degli Studi di Brescia

Corso di Laurea in Fisioterapia

Dott. Mattia Moretti

mattia.moretti@ospedalimantova.it

Alan Turing (1912-1954)

• Brillante matematico alla ricerca della soluzione dell’entscheidungsproblem

• Turing, agente al servizio di Sua Maestà

MdT per calcolare funzioni

• La Macchina di Turing è una macchina ideale che consente di calcolare funzioni mediante algoritmi

• Data una Macchina di Turing che calcola una funzione f è possibile specificare un input ed ottenere, al termine della computazione, l’output

• La tesi di Church postula che tutte le funzioni effettivamente calcolabili siano esprimibili con una Macchina di Turing

Come è fatta una MdT?

• Una MdT è definita da:– un nastro infinito

– una testina lettura/scrittura/cancellazione

– uno stato interno

– un programma

– uno stato iniziale

Il nastro

• Il nastro è – infinito– suddiviso in celle

• In una cella può essere contenuto un simbolo preso da un linguaggio formale

• Un linguaggio formale è semplicemente un insieme di simboli

• Una cella deve contenere un simbolo che appartenere al linguaggio

Lo stato interno e la testina

• La macchina è dotata di una testina di lettura/scrittura

• La testina è in grado di leggere, scrivere e cancellare il contenuto della cella del nastro su cui si trova

• La macchina ha uno stato interno• Uno stato è un elemento appartenente all’insieme

degli stati

Il programma di una MdT

• Il comportamento della macchina è determinato da un insieme di regole

• Una regola ha la forma di una quintupla:(A, a, B, b, dir)

• Una regola viene applicata se lo stato corrente della macchina è A e il simbolo letto dalla testina è a

• L’applicazione della regola cambia lo stato in B, scrive sul nastro b ed eventualmente sposta la testina di una cella a sinistra o a destra (dir)

Il funzionamento di una MdT

• La macchina opera come segue:– Determina la regola da applicare in base allo stato

interno e al simbolo corrente (quello letto dalla testina)– Se esiste una tale regola cambia lo stato, scrive il

simbolo sulla cella corrente si sposta come indicato dalla regola

– Se non esiste la regola l’esecuzione termina

• In questo modello non può esistere più di una regola per uno stato ed un simbolo corrente

Esempio: cambiamo X in Y

• Vogliamo programmare una Macchina di Turing che, dato sul nastro di input una stringa di X e Y, rimpiazza ogni occorrenza di X in Y ma non viceversa

Cambiamo X in Y (continua)

• Le regole corrispondenti sono:

(0, X, 0, Y, >)

(0, Y, 0, Y, >)

(0, -, 0, -, [])

• In questo caso è sufficiente lo stato 0• Al termine della stringa l’esecuzione sarà arrestata

John von Neumann (1903-1957)

• Realizzazione concreta di una macchina di Turing

• Architettura dell’elaboratore

La macchina di Von Neumann

Unità diElaborazione(CPU)

MemoriaCentrale (MM)

InterfacciaPeriferica P1

InterfacciaPeriferica P2

Bus di sistema

Esecuzione istruzioni

Memoria di lavoro

Memoria di massa,stampante, terminale…

Collegamento

La macchina di Von Neumann

• Il processore estrae le istruzioni dalla memoria e le esegue– Le istruzioni possono comportare operazioni di manipolazione dei

dati– Oppure operazioni di trasferimento dei dati

• I trasferimenti di dati attraverso elementi funzionali diversi avvengono attraverso il bus di sistema

• Le fasi di elaborazione si susseguono in modo sincrono rispetto ad un orologio di sistema

• Durante ogni intervallo di tempo l’unità di controllo (parte del processore) stabilisce la funzione da svolgere

• L’intera macchina opera in maniera sequenziale

Hardware

• La Res Extensa del computer

Processore(CPU- Central Processing Unit)

È il cervello del computer. Elabora, comprende e agisce in base alle istruzioni contenute nei programmi.

La memoria centrale (MM)• La memoria centrale si chiama usualmente ram o memoria ad

accesso casuale– Viene cosi detta una memoria il cui tempo di accesso sia indipendente

dall’indirizzo della parola alla quale si vuole accedere– Si tratta di una memoria volatile

• Altri tipi di memoria presenti in un calcolatore sono le rom– Hanno caratteristiche generali simili alle ram– Un tempo di accesso notevolmente maggiore– Si tratta di memorie permanenti– Sono tipicamente utilizzate per memorizzare quei dati e programmi

che servono al momento dell’accensione dell’elaboratore, prima del caricamento del S.O.

– Esempio: Il BIOS (Basic Input Output System) che carica in memoria il sistema operativo quando la macchina viene accesa

La memoria centrale (MM)• Il numero di bit che costituiscono l’indirizzo di un word

all’interno della memoria è caratteristico del microprocessore e identifica lo spazio di indirizzamento del microprocessore– Esempio: Pentium 32 bit– Avendo a disposizione k bit è possibile indirizzare 2k byte

• Si ricorda che:– 210 byte = 1Kilo Byte– 220 byte = 1Mega Byte– 230 byte = 1 Giga Byte– 240 byte = 1Tera Byte

Memoria di Massa

• Biblioteche, libri, scaffali e tavoli da lettura

• Memorie magnetiche e ottiche

• Nuove memorie allo stato solido

Hard disk

Unità di archiviazione a supporto magnetico destinata alla registrazione permanente dei dati.

Garantisce un’elevata capacità di archiviazione ed un accesso veloce ai dati.

CD-ROM

Unità di archiviazione a supporto ottico rimuovibile che può contenere grandi quantità di dati (650 Mb).

Più recentemente è apparso un nuovo tipo di supporto ottico, il DVD (Digital Versatile Disc), analogo al CD-ROM, ma in grado di contenere fino a 17 Gb di dati.

Periferiche di input/output

• Le parti stupide del computer

• Inserimento dell’informazione: tastiera, mouse, scanner

• Riproduzione dell’informazione: stampante, monitor

• Il bus di sistema collega tra loro i vari elementi del calcolatore

• In ogni istante il bus è dedicato a collegare due unità, una trasmette ed una riceve– Il processore seleziona la connessione da attivare e

indica l’operazione da svolgere (bus mastering)• Il bus è suddiviso in tre insiemi di linee:

– Bus dati– Bus indirizzi– Linee di controllo: trasportano informazioni relative

alla modalità di trasferimento e alla temporizzazione

Il bus di sistema

Software

• La Res Cogitans del computer

Categorie di software• Software di sistema

• Sistema operativo (kernel)• Altro software

– Interprete dei comandi (shell)– Sistemi a finestre (GUI, graphical user interface)– Software di rete– Editor, compilatori, ecc.

• Software applicativo• I programmi che svolgono attività utili per l’utente

finale

Funzioni del sistema operativo

• Nascondere la complessità e la varietà dell'hardware• “macchina astratta”• fornitura di system calls generiche, adattabili ai

diversi dispositivi

• Gestire le risorse ed i conflitti• rispetto al tempo (turni nell'uso)• rispetto allo spazio (es. memoria, disco)

Kernel

E’ il sistema operativo vero e proprio

• gestisce direttamente l’hardware della macchina e le sue periferiche

• è sempre (quasi tutto) residente in memoria: viene caricato alla accensione del sistema, e ci resta fino al suo spegnimento (o a un crash)

• fornisce i servizi necessari ai processi in esecuzione attraverso un insieme di system call

• gestisce gli interrupts generati dall’hardware

ProcessiSono i programmi in esecuzione

• Nei sistemi Unix tradizionali, ogni processo esegue una singola sequenza di istruzioni in un proprio spazio di indirizzi: un unico program counter specifica la prossima istruzione da eseguire

• I sistemi più moderni possono eseguire più thread in uno stesso spazio di indirizzi (in Linux: lightweight process)

• Ogni processo è indipendente dagli altri, e può interagire con essi solo attraverso il kernel, mediante opportune system call

• Il codice di un processo non necessariamente deve risiedere tutto in memoria centrale (varie tecniche di memory management…)

Time sharing

Unix è un sistema time-sharing: un processo esegue per un quanto di tempo (o finchè non si sospende in attesa di un evento, es.: fine I/O)