Corso—Programmazione Fondamentidiprogrammazione ...

Lezione 1 - Premesse per il corso

Corso — Programmazione

Fondamenti di programmazione— Le origini della

programmazione

Marco Anisetti

e-mail: [email protected]

web: http://homes.di.unimi.it/anisetti/

Università degli Studi di Milano — Dipartimento di informatica

http://homes.di.unimi.it/anisetti/

Obiettivi del corso(1)

• Corso introduttivo alla programmazione

• Nella sua carriera professionale un informatico potrebbe

non aver mai a che fare direttamente con la

programmazione, ma la sua conoscenza è di

fondamentale importanza dato che tutti gli strumenti con i

quali interagirà sono di fatto dei software

• Costituisce la differenza tra un utilizzatore del computer

(seppur professionista) e un informatico

Obiettivi del corso(2)

• Fornire gli strumenti di base per affrontare la

programmazione

• Fornire gli strumenti utili per apprendere qualsiasi

linguaggio di programmazione

• Approfondimenti sul il paradigma di programmazione

imperativo e il linguaggio C

• Paradigma di programmazione ad oggetti con elementi di

programmazione Java

Programma del corso

• Fondamenti per la programmazione

• Nozione di algoritmo

• Linguaggi di programmazione

• Dalla progettazione alla programmazione

• Paradigmi di programmazione

• Programmazione strutturata

• Linguaggio C (lezioni di laboratorio prof Cordone)

• Programmazione ad oggetti con elementi di Java

• Elementi di programmazione evoluta

Materiale consigliato

• D. E. Knuth. The Art of Computer Programming, vol. 1:

Fundamental algorithms. Addison-Wesley, Reading (MA),

1997.

• N. Wirth. Principi di programmazione strutturata. ISEDI,

Torino, 1995.

• Ravi Sethi. Programming Languages. Addison-Wesley

1996.

• G. Pighizzini M. Ferrari. Dai fondamenti agli oggetti Corso

di programmazione JAVA. Terza Edizione Pearson

Addison-Wesley Febbraio 2008

Altro materiale di dettaglio verrà indicato durante il corso

Modalità d'esame

Due prove obbligatorie:

• Scritto cartaceo con più domande a risposta aperta su

tutti gli argomenti del programma le domande possono

richiedere scrittura di programmi in pseudocodice

• Esame di programmazione in linguaggio C che viene

effettuato in piattaforma (prof. Cordone)

• Progetto di programmazione Java.

Progetto di programmazione a oggetti (da inviare 15 giorniprima della discussione) con orale in cui presentare ediscutere il proprio progetto

Prefazione

• Due approcci possibili:

Idealistico: Presentare la materia già organizzata alla lucedei moderni sviluppi (OO, pattern, ecc.)Evoluzionistico: Presentare la materia come evoluzionestorica fino ad arrivare ai suoi recenti sviluppi

• Agli albori dell'Informatica poteva essere considerata

un'arte o un mestiere, si è evoluta col tempo in una vera e

propria disciplina accademica

• Si integra in un piano di studi che comprenda ``Algoritmi

e Strutture Dati'', ``Linguaggi di Programmazione'' ed

``Ingegneria del software''

Fondamenti per la programmazione

• Fondamenti per la programmazioneOrigini della programmazione

Le origini della programmazione

Il ruolo della programmazione oggi

Elementi di matematica e logica per la programmazione

Elementi di insiemistica

Logica dei predicati

Induzione matematica

Macchine a Stati

Formalizzazione di un linguaggio

Macchine a Stati finiti

Macchina di Turing

Architettura di un elaboratore

• Algoritmi

Lezione 2 - Origini della programmazione



programmazione

Marco Anisetti





Elaboratore elettronico programmabile

• Nel corso si parlerà di programmazione di elaboratori

elettronici

• Per prima cosa dobbiamo chiederci perchè gli elaboratorielettronici possono essere programmati

Cosa significa programmabile?

• Gli elaboratori elettronici non sono nati già essendo

programmabili

• Si tratta di una evoluzione lunga

• Gli elaboratori elettronici non sono altro che macchine

Scopo di sostituirsi o facilitare il lavoro umano

Origini della programmazione

• Attrezzi con forma e proprietà tali da estendere le

possibilità manuali dell'uomo

• La maggior parte degli attrezzi e delle macchine è

concepita per svolgere un solo compito

• Attrezzi o macchine più complesse possono essere

adattate a compiti leggermente diversi mediante

regolazioni (embrione della programmazione)

• Attrezzi regolabili

Macchine programmabili

• Versatilità delle macchine programmabili

• Esempio lavatrice

• Si adatta a diverse tipologie di panni da lavare con diversi

procedimenti di lavaggio

• Attività di regolazione che viene chiamataprogrammazione

Definisce un programma di lavoro da seguire

• Ogni programma è adatto ad uno scopo e non funziona

bene per altri scopi

Calcolatori programmabili

• Primo approccio storico: un modello di calcolatore diverso

per ciascuno dei calcoli che erano di volta in volta richiesti

• C'è un motivo molto valido per cui molto presto si

intraprese a progettare dei calcolatori general purpose

• Al crescere della complessità degli elaboratori, il compito

di programmarli iniziò a superare in complessità

addirittura il compito di progettarli

Lezione 3 - Il ruolo della programmazione

oggi



programmazione

Marco Anisetti





Importanza della programmazione

• Importante in qualsiasi ambito informatico

• Permette di comprendere più a fondo il funzionamento di

programmi o sistemi programmabili

• Con la tendenza alla Cloud Computing la cognizione

dell'elaborazione di un programma o processo è

fondamentale per un uso consapevole della tecnologia

• In ambito di sicurezza e privatezza sapere come viene

ideato un programma che tratta i dati sensibili è

importante

• Malfunzionamenti o problemi nei sistemi informativi sono

quasi sempre dovuti a malfunzionamenti di programmi

Il programmatore oggi(1)

• Il programmatore degli albori si occupava di tutto dalla

soluzione del problema alla implementazione e spesso

anche all'uso del programma

• Nel corso partiamo con un approccio che ci farà indossare

i panni del programmatore agli albori della

programmazione

• Ad oggi la programmazione è una parte del processo disviluppo di un software che è un lavoro di team e cheprevede diverse macro fasi

RequisitiProgettazioneSviluppoTest

• Spesso il programmatore viene interpellato

(erroneamente) sono nelle fasi di sviluppo e parzialmente

in quella di test


• Il programmatore non è più visto come un factotum, ma

una parte di un team

• Il programmatore è uno specialista verticale (ma le

competenze base devono essere presenti a tutti i livelli del

team)

• Il programmatore è l'esperto di codifica dell'algoritmo

• Purtroppo questa visione non è completamente corretta

• Si dovrebbe parlare di Analista e Programmatore in

qualsiasi caso

• Ammettendo che la soluzione al problema venga ottenuta

da altre figure professionali l' Analista e Programmatore

troverà la soluzione implementativa migliore per la

soluzione al problema proposta


• La programmazione è ancora un'arte!

• La componenti di inventiva non è solo per la ricerca della

soluzione al problema ma anche per la ricerca della

implementazione migliore della soluzione

• Non è da escludere una retroazione se l'analisi di una

implementazione evidenzia una migliore soluzione al

problema

• La programmazione di dispositivi embedded o di app pur

assistita da SDK e tool di sviluppo che automatizzano gran

parte del lavoro richiede fortissime competenze di sviluppo

• A qualsiasi livello del team di sviluppo le competenze di

programmazione orizzontali sono sempre fortemente

necessarie

Lezione 1 - Elementi di insiemistica


Fondamenti di programmazione— Elementi di matematica e

logica per la programmazione

Marco Anisetti





Insieme

[Insieme]

e' una qualsiasi collezione di elementi

• Esempio: insieme A delle prime sei lettere dell'alfabeto è

A = {a,b,c,d,e,f }• La lettera b è un elemento dell'insieme A: b ∈ A

• E' prassi comune indicare:

Maiuscole per denominare gli insiemi: A,B,C, . . .Minuscole per denominare i loro elementi: a,b,c, . . .:Negazione dell'appartenenza ad un insieme a 6∈ A: a non èelemento dell'insieme A

Rappresentazione di insiemi

• Grafica: attraverso il diagramma di Eulero-Venn

• Intensiva: associando gli elementi ad una proprietà

A = {x ∈ IR : x mod 3 = 0};

• Extensiva: elencando tutti gli elementi dell'insieme:

B = {cane,gatto,canarino,lucertola}.

Operazioni sugli insiemi(1)

[Sottoinsieme]

Un insieme B è detto sottoinsieme dell'insieme A (oppure B è

incluso in A) se ogni elemento di B è anche elemento di A:

B ⊆ A

[Intersezione]

Dati due insiemi A e B, la loro intersezione A∩ B è l'insieme di

tutti gli elementi comuni ad A e B

Operazioni sugli insiemi(2)

[Unione]

Dati due insiemi A e B, la loro unione A∪ B è l'insieme di tutti

gli elementi che appartengono ad A o a B o ad entrambi

[Complementare]

Il complemento di un insieme A, A, è l'insieme di tutti gli

elementi che non appartengono ad A

L'insieme vuoto si indica con ∅ oppure {}

Proprietà delle operazioni(1)

U simboleggia l'universo del discorso

• Proprietà commutativa:

A∪ B = B ∪ A

A∩ B = B ∩ A

• Proprietà associativa:

A∪ (B ∪ C) = (A∪ B) ∪ C

A∩ (B ∩ C) = (A∩ B) ∩ C

• Proprietà distributiva:

A∪ (B ∩ C) = (A∪ B) ∩ (A∪ C)

A∩ (B ∪ C) = (A∩ B) ∪ (A∩ C)


• Idempotenza:

A∪ A = A

A∩ A = A

• Identità:

A∪ ∅ = A

A∩ U = A

A∩ ∅ = ∅;A∪ U = U


• Proprietà transitiva dell'inclusione:

se A ⊆ B ⊆ C, allora A ⊆ C.

• Involuzione:

A = A.

• Leggi di De Morgan:

A∩ B = A∪ B;

A∪ B = A∩ B.

Prodotto cartesiano

[Prodotto cartesiano]

Dati 2 insiemi A e B, il loro prodotto cartesiano A× B è

l'insieme di tutte le coppie ordinate (a,b) dove a ∈ A e b ∈ B.

[Relazione tra insiemi]

Una relazione R tra insiemi A,B è un sottoinsieme del loroprodotto cartesiano, contenente tutte le coppie che la

soddisfano.

R ⊆ A× B.

Relazioni composte

[Relazioni composte]

Sia R1 ⊆ Z × K una relazione tra elementi degli insiemi Z e K,

e R2 ⊆ K ×W una relazione tra elementi degli insiemi K e W. E

possibile comporre le due relazioni R1 e R2 in modo da

ottenere una nuova relazione R1 ◦ R2 ⊆ Z ×W, con

(z,w) ∈ R1 ◦ R2 sse esiste un elemento k ∈ K : (z,k) ∈ R1 e

(k,w) ∈ R2

[Funzione]

Dati due insiemi A e B, una funzione f di dominio A e

codominio B, f : A→ B, associa ad ogni elemento a ∈ A un

elemento b = f (a) ∈ B (mapping)

Funzione iniettiva e suriettiva

[iniettiva]

Una funzione f si dice iniettiva se e solo se x1 6= x2 implica

f (x1) 6= f (x2)

Immagine di f è Imf ≡ {y|∃x ∈ A : y = f (x)}

[suriettiva]

Una funzione si dice suriettiva se

{∀y ∈ B|∃x ∈ A : y = f (x)}Ovvero la sua immagine coincide con il suo codominio

Funzione biiettiva ed inversa

[biiettiva]

Una funzione che sia sia iniettiva che suriettiva è detta

funzione biiettiva

[inversa]

Data una funzione biiettiva f : A→ B, si dice inversa di f la

funzione f−1 : B → A tale che x = f−1(y) se e solo se y = f (x)

Cardinalità(1)

[Cardinalità di un insieme]

La cardinalità di un insieme A è il numero di elementi che

appartengono all'insieme A, e si denota ‖A‖.

• Siano A e B due insiemi: allora, l'insieme prodotto, ovvero

costruito come prodotto cartesiano, A× B ha una

cardinalità che è il prodotto delle cardinalità degli insiemi

A e B:

‖A× B‖ = ‖A‖ · ‖B‖.

Cardinalità(2)

Siano A e B due insiemi: allora

• l'insieme di tutte le funzioni f : A→ B ha una cardinalità

esponenziale data da ‖B‖‖A‖;• Un caso particolare del precedente è quello dell'insieme

potenza di A, cioè l'insieme di tutti i sottoinsiemi di A, la

cui cardinalità è 2‖A‖

Lezione 2 - Logica dei predicati




Marco Anisetti





Logica proposizionale(1)

• Una proposizione è una frase di senso compiuto che può

essere vera o falsa

• La logica proposizionale si occupa della verità o falsità di

proposizioni composte sulla base della verità o falsità delle

proposizioni che le compongono

• Ogni proposizione viene contrassegnata da un simbolo es

P

• Le proposizioni sono considerate come delle unità

elementari e non possono essere parametrizzate

• Le proposizioni composte è ottenuta da più proposizionisemplici tramite connettivi logici

¬ (non, negazione), ∧ (e, congiunzione), ∨ (o,disgiunzione), ⊃ (implica, implicazione), ≡ (se e solo se,equivalenza)Esempio: (P ∧Q) ⊃ ¬ C (''se fa caldo e c'è molta umiditànon si sta bene'').

Logica proposizionale(2)

• Problemi per formalizzare un ragionamento che comporta

affermazioni su un gran numero di oggetti individuali

• Esempio: 500 posti a sedere in un palazzetto possono

essere liberi o occupati. In logica proposizionale

dovremmo definire una proposizione per ciascun oggetto

(Pi =′′Il posto numero i è libero′′,...)

• La costruzione di certe proposizioni diverrebbe veramente

lunga ed impraticabile: ′′c'è un posto libero′′, cheassumerebbe la forma P1 ∨ P2 ∨ . . . ∨ P500.

• Alcune inferenze logiche non possono venire giustificate

sulla base del calcolo proposizionale

Logica dei predicati(1)

Nella logica dei predicati si assume l'esistenza di:

• Simboli individuali: i nomi dei singoli oggetti di cui si

vuole ragionare, che chiameremo le istanze:

{pastello,matita,penna},{nero, blu, rosso}• Variabili (tipo x, y e z): le quali possono assumere valori

sull'insieme dei simboli individuali

• Simboli di funzione: ciascuno con la propria arità, che

possono essere utilizzati per costruire nuove istanze:

Colore(pastello)

• Simboli di predicato: ciascuno con la propria arità, che

servono per costruire proposizioni su particolari istanze o

insiemi di istanze, Ha-colore(pastello,nero)


Gli argomenti di un predicato ovvero le entità sulle quali si

costruiscono le affermazioni, si chiamano anche termini. Un

termine può essere

• Un simbolo individuale

• Una variabile

• Una funzione: se f è una funzione n-aria e t1, . . . ,tn sonotermini, anche f (t1, . . . ,tn) è un termine.


L'utilizzo dei quantificatori rende possibile specificare se una

data proposizione contenente variabili libere si riferisca a tutte

le istanze che potrebbero sostituire una data variabile o ad un

numero di istanze più ristretto

Ci sono due quantificatori:

• Quantificatore esistenziale ∃ (′′esiste′′)• Quantificatore universale ∀ (′′per ogni′′)

Tutti gli uomini sono mortali: ∀x Uomo(x) ⇒ Mortale(x)

Esiste una penna blu: ∃y penna(y) ∧ blu(y)

Predicati ed insiemi

• I predicati definiscono insiemi

Le istanze x, che verificano il predicato studente(x)costituiscono l'insieme degli studenti

• La disgiunzione ∨ definisce un'unione ∪Le istanze x che verificano il predicato ′′studente(x) ∨professore(x)′′, costituiscono l'insieme delle persone chesono studente o professore (o entrambi)

• La congiunzione ∧ definisce un'intersezione ∩Le istanze x che verificano il predicato ′′studente(x) ∧straniero(x)′′, costituiscono l'insieme delle persone chesono studenti e che sono straniere.


Nella logica dei predicati del prim'ordine i quantificatori

possono essere applicati solo alle variabili libere di una

formula, ottenendo formule come

∀x(Posto(x) ∧ Libero(x))

per esprimere l'affermazione che tutti i posti del palazzetto

sono liberi o

∃x(Posto(x) ∧ ¬Libero(x))

per esprimere l'affermazione che almeno un posto è occupato

La logica dei predicati permette di analizzare gli elementi di

cui la proposizione è composta

Essa è quindi uno strumento più potente (e più complesso)

della logica proposizionale.


Esistono anche delle logiche dei predicati di ordine

superiore al primo, dove anche i simboli di funzione e i simboli

di predicato possono essere quantificati.

Logica del primo ordine agisce su proprietà che riguardano gli

elementi di un insieme X (X contiene elementi semplici)

La logica del secondo ordine riguarda proprietà sui

sottoinsiemi di X, (X non contiene più elementi semplici)

“per tutti i sottoinsiemi dell'insieme X vale la proprietà P”

Abbastanza potenti da esprimere ricorsione e quindi i numeri

naturali

Per ordini superiori al primo: Teorema di Gödel non esiste

algoritmo che calcoli in tempo finito il valore di verità data una

qualsiasi proposizione.

Lezione 3 - Induzione matematica




Marco Anisetti





Induzione matematica(1)

• Si usa nelle definizioni e nelle dimostrazioni

• Definizione induttiva: definisco induttivamente i numeripari

Il numero 0 è pariSe n > 0 è un numero pari anche n+ 2 è un numero pari

• Dimostrazione induttiva: dimostro (2n)2 = 4n2

Per n = 1 la formula risulta vera (caso base)Suppongo la relazione sia vera per n = k e la dimostro pern = k + 1 (passo induttivo)(2(k + 1))2 = 4k2 + 8k + 4 = 4(k2 + 2k + 1) = 4(k + 1)2


• Esiste un caso base, rappresentante un sotto-problema

facilmente risolubile

• Per esempio: se n = 0 so calcolare il fattoriale di n.

• Prima o poi occorre ricondursi a questo caso base

• Supponiamo di voler dimostrare una proposizione P

dipendente da un numero naturale

• Se P è vera per 0 (base di induzione) e se il fatto che siavera per un generico naturale n comporta

necessariamente che sia vera per n+ 1 (ipotesid'induzione) allora P è vera per tutti i numeri naturali


• Si può generalizzare la base di partenza con un k qualsiasi

naturale

• La somma degli angoli di un poligono di n lati è (n− 2) ∗ 180• Si parte da una base di induzione con k = 3 e si concludeche sia vera per tutti i naturali n ≥ 3

Dimostrazione induttiva: esempio(1)

• Dimostrare induttivamente che la somma dei primi n

numeri dispari è n2

• Numero dispari (2n− 1)

• Somma dei primi n dispari: 1 + 3 + 5 + · · ·+ (2n− 1) = n2

• Dimostrazione:

L'enunciato è vero per n = 1Dimostrare che se è vero per un n allora è vero anche per ilsuccessore n+ 1.Il successore di un dispari (2n− 1) è (2n+ 1)1 + 3 + 5 + · · ·+ (2n− 1) + (2n+ 1) = n2 + 2n+ 1 = (n+ 1)2

Si conclude che è vera per tutti gli n ≥ 1

Dimostrazione induttiva: esempio(2)

• Interessante la visualizzazione grafica che dimostra che la

somma dei numeri dispari è un quadrato

Dimostrazione induttiva: controesempio

• Valutiamo P(n) come il numero delle partizioni di n ovveroil numero dei modi differenti con cui si può scrivere ncome somma di numeri non valutando l'ordine.

P(1) = 1,P(2) = 2,P(3) = 3,P(4) = 5,P(5) = 7Uno sarebbe tentato di derivare induttivamente che questepartizioni sono i numeri primiEsempio: P(5)=1+1+1+1+1;2+1+1+1;2+2+1; 3+1+1;3+2; 4+1; 5 = 7 partizioniSe proviamo P(6) avremmo la conferma dato che è 11Purtroppo però P(7) = 15Quindi non si riesce a dimostrare

Considerazioni

• Induzione matematica non equivale al ragionamento

induttivo scientifico

• Ragionamento induttivo: crea una teoria generale

dall'osservazione di alcuni casi particolari

• L'induzione matematica serve per spiegare i concetti di

programmazione relativi a iterazione e ricorsione

• L'induzione può anche essere applicata ad algoritmi per

farne delle prove di alcune proprietà

Lezione 1 - Formalizzazione di un

linguaggio


Fondamenti di programmazione— Macchine a Stati

Marco Anisetti





Introduzione(1)

• Linguaggio: si intende la capacità d'uso e l'uso stesso diun qualunque sistema di simboli adatti a comunicare [cit.Garzanti].

Accezione generale: linguaggio dell'arte, linguaggio dellamusica, linguaggio del cinema.Esempio concreto: linguaggio naturale, scritto (fortementecodificato da caratteri tipografici e spazi) o parlato (suoni).Linguaggio scritto: sequenza finita di simboli preso da uninsieme finito prefissato di simboli (non tutte le sequenzesono parte del linguaggio)

Introduzione(2)

• La linguistica ha come obiettivo quello di dare unarigorosa descrizione di un linguaggio scritto, specificandoquali frasi sono formate correttamente.

linguaggi artificiali: utili per la comunicazioneuomo-macchina.Es: linguaggio C descritto dalle sequenze di caratteri cheun compilatore C accetta

Approfondimenti in un corso di Linguaggi formali e automi

Alfabeto e stringhe

• Un alfabeto è un insieme (finito) di elementi chiamatilettere o simboli.

Un esempio molto semplice di alfabeto è l'alfabeto binarioΣ = {0,1}

• Una stringa s su un alfabeto è unasequenza finita di simboli appartenenti all' alfabeto

Ad Esempio s = 001101 è una stringa sull'alfabeto binarioΣ = {0,1}

• Esiste una nozione di lunghezza di una stringa s definitacome cardinalità della stessa |s|

Es |001101| = 6

• Esiste la nozione di stringa vuota ε ovvero la stringa connessun simbolo - |ε| = 0

Operazioni sulle stringhe

• Kleene Star: Dato alfabeto Σ la chiusura di Kleene Σ∗ è l'insieme di tutte le possibili stringhe su Σ.

Esempio consideriamo Σ = {0,1} alloraΣ∗ = {ε,0,1,00,01,10,000, · · · }

• Concatenazione: Consideriamo due stringhe a e b la

loro concatenazione è la stringa ab (esistono anche

notazioni esponenziali per concatenazioni multiple tipo an)

• Sottostringa: Consideriamo la stringa s, unasottostringa di s è una qualsiasi parte di simboliconsecutivi della stringa s

Esempio b è sottostringa della stringa s se ∃ a e b (anchevuote) : s = abc

• L'insieme di tutte le stringhe che si possono ottenere da Σtranne la stringhe vuota ε viene indicato come Σ+

Linguaggio formale

• Un linguaggio formale è un insieme diparole su un alfabeto (non sono generalmente degliinsiemi finiti)

linguaggio L è un sottoinsieme delle parole costruibili su unalfabeto Σ, L ⊆ Σ∗.

Simboli o token: sono gli atomi di cui è costituito unenunciato in un linguaggioParola di un alfabeto è una stringa di quello stesso alfabetoΣ∗ denota l'insieme di tutte le parole composte da elementidi Σ, compresa ε

• Il linguaggio non contenente alcuna parola viene detto

linguaggio vuoto

Sui linguaggi si possono utilizzare molte delle operazioni definite sugli insiemi quali

intersezione unione e differenza.

Esempi di linguaggi

• Italiano: parole sull'alfabeto {a,b, . . . ,z} elencate nelvocabolario. Linguaggio finito {a,abaco, . . . ,zuppo}

• Espressioni aritmetiche: parole sull'alfabeto{0,1, . . . ,9,(,),+ ,∗} secondo delle regole ben precise

Es. ((10 + 4) ∗ 3) è una parola in L, mentre (10 + 4( non è unaparola in L

Operazioni sui linguaggi

• Cardinalità: numero di stringhe che lo compongono

• Concatenazione linguaggio Lc = L1L2

• Potenza n-esima Ln :insieme di stringhe ottenuteconcatenando n stringhe di L, con possibili ripetizioni.

Es. Se L = {a,bb}S0 = {ε}S1 = {a,bb}S2 = {aa,abb,bba,bbbb}

• Chiusura L∗ : linguaggio costituito dal'unione di tutte len-esime potenze di L

• Chiusura positiva L+ : Chiusura con n > 0

Codice

• Codice: Un linguaggio L in cui ogni parola in L+ èdecomponibile in un unico modo come prodotto di paroledi L.

Proprietà: univocamente decifrabileData una parola in L+ esiste un solo modo di ottenerlacome prodotto di parole di L.

C = {1,10} è un codiceC′ = {bab,aba,ab} non è un codice

Il codice ASCII rappresenta i 256 caratteri sul codiceprefisso formato da tutte le parole binarie di lunghezza 8,cioè da tutte le sequenze di 8 bit.

• Un linguaggio L in cui ogni parola non è prefisso di nessun

altra parola

• Linguaggio formato da parole di ugual lunghezza

Appartenenza ad un linguaggio

• Data una parola (stringa o frase) w ∈ Σ∗, ci sono duepossibilità:

w appartiene al linguaggio, w ∈ L, cioè rappresenta unenunciato di Lw non appartiene al linguaggio, w /∈ L, cioè nonrappresenta un enunciato valido di L.

L contiene un numero infinito di parole cioè di possibili enunciati.

Riconoscitori e generatori

• Approccio basato sul riconoscimento: rappresentare Lattraverso la definizione di un algoritmo che, per ogniparola w ∈ Σ∗, termina con il risultato ``si'' se w ∈ L e``no'' altrimenti.

Non tutti i linguaggi ammettono un riconoscitoreQuelli che lo ammettono sono detti ricorsivi o decidibiliAutomi a stati finiti: famiglia di riconoscitori (riconoscitoridi linguaggi regolari)

• Approccio generativo: consiste nel definire una procedura

in grado di generare sistematicamente tutte le parole w di

L, una dopo l'altra.

• Un'importantissima classe di sistemi generativi, che sono

di fatto impiegati per descrivere in modo finito linguaggi

infiniti, sono le grammatiche.

Catalogazione dei linguaggi formali

• Definita attraverso la grammatica di Chomsky

Inizialmente definita per il linguaggio naturale IngleseRivelatasi inadeguataRuolo rilevante per lo studio della proprietà sintattiche deiprogrammi e dei linguaggi di programmazione

• Tipo 0: senza restrizioni

Macchine di Turing

• Tipo 1: contestuali

Macchine di Turing non deterministiche

• Tipo 2: non-contestuali → descrizione formale deilinguaggi di programmazione

Automi a pila non deterministici

• Tipo 3: regolari → i componenti sintattici più elementaridi un linguaggio di programmazione (identificatori,costanti, parole chiave)

Automi a Stati Finiti

Linguaggio: definizione informale

• Un repertorio di segni convenzionali e di regole per

combinarli in enunciati più complessi

• Un insieme di regole che permettano di associare un

significato a ciascun enunciato.

• Si distinguono 3 livelli

Sintattico: regole che specificano in quali modi i segnipossano essere combinati per formare enunciati;Semantico: regole che permettono di associare a ciascunsegno e a ciascun enunciato il loro significato;Pragmatico: implicazioni pratiche e le conseguenze di unenunciato.

Importanza dei linguaggi formali

• In ambito di programmazione ci interessiamo a linguaggi

infiniti le cui stringhe hanno delle caratteristiche

• Definite su un particolare alfabeto alfabeto

Es per C, C++ e Java{a,b, . . . ,z,A,B, . . . ,Z,0,1,2, . . . ,9, > , < , = ,+ ,?,?,/,(,), . . . }

• Avrà delle parole definite a partire da questo alfabetocome le direttive, le istruzioni, simboli matematici ecc.

Es il linguaggio C è costituito da tutte le stringheanalizzabili dal compilatore C

• Studio delle proprietà sintattiche dei programmi

Definizione della sintassiVerifica delle proprietà sintatticheTraduzione

Lezione 2 - Macchine a Stati



Marco Anisetti





Sistema a Stati(1)

• Una ``black box'', dotata di un ingresso e di una uscita

input: messaggi, dati da un alfabeto finito S = {s1,s2,…,sn}Output: un valore in {0,1}

• Il funzionamento consiste nell'esecuzione di``esperimenti'':

input: sequenza di messaggi come parola w ∈ S∗

output: se il risultato è 1 la parola viene accettata,altrimenti respinta.

Sistema a Stati(2)

• Il comportamento del sistema è descritto dall'insieme di

parole accettate

• Riconoscitore di linguaggi

• Si può pensare di modellarlo attribuendo al sistema un

insieme di possibili stati interni

Un esempio intuitivo

• Esempio macchina per l'erogazione di bibite/snack da 50centesimi

Accetta monete da 10c e da 20cNon da restoRifiuta moneta superiori

Enigma del lupo, del cavolfiore e della

pecora

Un barcarolo doveva trasportare sull' altra riva del fiume un

lupo, una pecora e un cavolo, ma non trovò che una barca

capace di portarne due alla volta (egli stesso più un altro). Gli

era stato ordinato di non procurare alcun danno né agli

animali né alla pianta (non può lasciare soli cavolo e pecora o

pecora e lupo).( Tratto dalle Propositiones ad acuendos

juvenes di Alcuino )

Soluzione

Prima trasporta la pecora, lasciando a terra il lupo e il

cavolfiore; poi torno indietro e porta sull'altra riva il lupo:

giunto sull'altra riva, fa scendere il lupo, carica in barca la

pecora e la riporto indietro. Faccio scendere dalla barca la

pecora, prende il cavolfiore e lo porta sull'altra riva, quindi

ritorna con la barca vuota ed infine trasporto la pecora.

Codifica come stringa

• Consideriamo le seguenti mosse

Attraversa con lupo (l)Attraversa con pecora (p)Attraversa con cavolofiore (c)Attraversa solo (s)

• Stringa che identifica la soluzione: pslpcsp

Modellazione della soluzione(1)

• Come possiamo modellare questa soluzione?

• Consideriamo le presenze sulle due sponde Est e Ovestcome lo stato del sistema

Dobbiamo considerare anche la presenza del barcarolosulle sponde (barcarolo simbolo b)

• Le transizioni da uno stato all'altro sono gli spostamenti

Modellazione della soluzione(2)

Linguaggio delle soluzioni

• Il grafo definisce il linguaggio delle soluzioni {x ∈ {l,p,c,s}∗|iniziando in uno stato iniziale e seguendo gli archi definiti

da x si arriva nello stato finale}• Il linguaggio è infinito

Procedura computazionale per decidere se una stringa èsoluzione: genera un percorso dallo stato iniziale allostato finale.

Automi a stati finiti

• Un automa a stati finiti è un modello matematico di un

sistema con ingressi e uscite discreti

• In un certo istante il sistema può trovarsi in uno stato

scelto tra un numero finito di stati possibili

• Lo stato corrente del sistema riassume l'informazione

circa la sequenza di ingresso fornita in passato e serve per

determinare il comportamento del sistema al successivo

ingresso (stato futuro)

• Il passaggio tra stati è detto transizione

• E' un modello semplice per un calcolatore con memoria

finita (in: stringa, out: accetta o rifiuta la stringa)

• Automa Completamente Specificato: una transizione

per ogni stato e per ogni lettera in Σ

Automi a stati finiti: esempi software

• Firmware: macchina per l'erogazione delle bibite, driver

• Compilatori: analizzatore lessicale, parser

• Progettazione circuiti digitali

• Protocolli, sistemi biologici

• Elaboratori di testo

• Ricerche web o su file

• Video giochi

Definizione formale

• Formalmente, un automa finito M su un alfabeto Σ è unaquintupla

〈K ,Σ,δ,q0,F 〉• K è un insieme finito e non vuoto di stati in cui si può

trovare M

• Σ è un alfabeto finito di simboli di ingresso,

• δ : K × Σ → K è la funzione di transizione di stato

• q0 ∈ K è lo stato iniziale

• F ⊆ K è l'insieme degli stati finali

Rappresentazione

• Un automa può essere convenientemente rappresentato

in forma tabulare, mediante la sua funzione δ, o in formagrafica

• La forma grafica utilizza un grafo orientato detto grafo

delle transizioni

• Se c'è una transizione dallo stato q allo stato p ricevuto

l'ingresso a, allora c'è un arco da q a p etichettato con a

• Permette di risolvere in modo elegante alcuni problemi

(riducibili a riconoscimenti di stringhe di un linguaggio)

Proprietà

• Dinamicità: evoluzione attraverso diversi stati

• Discretezza: le variabili d'ingresso e gli stati del sistema

possono essere espressi con valori discreti

• Simboli finiti: il numero di simboli di ingresso e di stati

sia rappresentabile da un numero finito

• Automi a stati finiti deterministici (ASFD)

• Automi a stati finiti non deterministici (ASFND)

• ASFD per qualsiasi input, esisterà una ed una sola

transizione

• ASFND almeno uno stato presentapiù di una possibile computazione per determinaticaratteri in ingresso (più stati raggiungibili con un input).

Il determinismo è un caso particolare di non determinismo

Automi a stati finiti deterministici:

esempio

Un esempio di automa deterministico con la relativa tabella di

transizione

Automi a stati finiti non deterministici:

esempio

Un esempio di automa non deterministico con la relativa

tabella di transizione

Automi con output

• Automa di Moore: l'uscita dipende solo dallo stato.Definito come sestupla 〈K ,Σi ,Σo,δ,q0,G〉Con alfabeto che si distingua tra alfabeto degli ingressi Σi edelle uscite Σo

Non ho stati terminaliFunzione di uscita G : K → Σo

• Automa di Mealy: l'uscita dipende dallo stato e dagliingressi

Funzione di uscita G : K × Σi → Σo

Linguaggi regolari e automi

• Se L è l'insieme di tutte le stringhe che la macchina Maccetta allora L è il linguaggio di una macchina M

M riconosce (o accetta) L scritto anche L(M) = L

• Un Linguaggio è regolare se è riconosciuto da qualcheASFD o ASFND.

Sono definibili a partire da espressioni regolariUn sottoinsieme particolare dei linguaggi formali

Esempio di applicazione(1)

• Si supponga di dover scrivere un programma che filtra un

file sorgente C, C++ o Java eliminando tutti i commenti

• Risolvere questo problema definendo un automa che

legge un file di ingresso un carattere alla volta e, a

seconda dei caratteri letti, cambia stato

• Individuare gli stati e le transizioni dell'automa e

disegnarlo in forma grafica


1. (stato iniziale) in procinto di copiare i caratteri letti, che

non appartengono a un commento, nel file di uscita; se

viene letto il carattere ``/'', l'automa passa nello stato 2;

2. incontrato il carattere ``/'': se viene letto il carattere

``/'', l'automa passa nello stato 3; se viene letto il

carattere ``*'', l'automa passa nello stato 4; altrimenti,

l'automa copia in uscita sia ``/'' che il carattere letto e

passa allo stato 1;

3. dentro un commento che si estende fino alla fine della

linea, in procinto di scartare tutti i caratteri letti; se viene

raggiunta la fine della linea, l'automa ritorna nello stato 1;


4 dentro un commento racchiuso tra i due simboli ``/*'' e

``*/'', in procinto di scartare tutti i caratteri letti; se viene

letto il carattere ``*'', l'automa passa allo stato 5;

5 se viene letto il carattere ``/'', l'automa passa allo stato

1, altrimenti passa allo stato 4, a meno che non venga

letto il carattere ``*'', nel qual caso l'automa rimane in

questo stato.

Lezione 3 - Macchina di Turing



Marco Anisetti





Alan Mathison Turing

Alan Mathison Turing (1912 - 1954) matematico, logico e

crittanalista britannico, considerato uno dei padri

dell'informatica e uno dei più grandi matematici del

Novecento.

Fu uno dei più brillanti decrittatori che operavano in

Inghilterra, durante la seconda guerra mondiale.

Decifrò Enigma, il codice usato dai sottomarini tedeschi.

Morì mangiando una mela al cianuro, in seguito ad una

persecuzione omofobica condotta nei suoi confronti.

Macchina di Turing

• Modello fondamentale per la teoria dell'informatica

• Permette di analizzare e definire il concetto di algoritmo

• Ha permesso di ottenere risultati negli ambiti di

CalcolabilitàComplessitàEquivalenza di algoritmi

Macchina di Turing: struttura

• La Macchina di Turing (MdT) è una macchina a stati finiti

(dispositivo di controllo) con un nastro potenzialmente

infinito

• Sul nastro agisce una testina

• La testina può muoversi in entrambe le direzioni.

• Può leggere e scrivere in ogni cella del nastro (alfabeti

predefiniti)

• Le celle possono essere vuote

Operazioni

• La testina di lettura-scrittura:

Spostamento di una posizione (a sinistra o a destra).Scrittura o lettura di un simbolo nella cella sotto la testina(sostituendo il contenuto precedente).

• Il dispositivo di controllo in ogni istante si trova in

uno stato tra un insieme finito di stati

• A seconda dello stato e del simbolo letto

Cambia statoEsegue una delle azioni di elaborazione

MdT: determinazione

• Contenuto iniziale del nastro.

• Posizione iniziale della testina.

• Stato iniziale del dispositivo di controllo.

Automa → Tabella delle transizioni di statoCoppia stato-simbolo letto, stato successivo-simbolo scrittoe direzione del movimento della testina

Elaborazione

• Elaborazione y = F (x)

• x nastro allo stato iniziale

• y nastro nello stato finale

• F=d(MdT): posizione iniziale stato iniziale, tabella di

transizione

Tabella delle transizioni di stato

• Una quintupla di elementi:

s: lo stato della macchina all'istante presentei: il simbolo letto all'istante presenteS(s,i): lo stato della macchina all'istante successivoI(s,i): il simbolo scritto dalla macchina all'istante successivoV(s,i): il verso del movimento della macchina (destra osinistra)

MdT rappresentazione

• Esistono delle varianti della MdT: multinastro, non

deterministiche ecc.

Esempio(1)

• Costruiamo una macchina che valuti se il numero di

occorrenze del simbolo 1 in una sequenza di 0 e 1 è pari.

• Consideriamo che la sequenza debba iniziare e terminare

con il simbolo ?

• Numero di 1 pari: la macchina scrive 1 nella prima casella

a destra della stringa di ingresso

• Numero di 1 dispari: la macchina scrive 0 nella prima

casella a destra della stringa di ingresso

Esempio(2)

Utilizzi

• E' in grado di risolvere una classe di problemi molto vasta

Esempio: stabilire se una sequenza di parentesi è benformata.

• Algoritmo: una MdT che si arresti trasformando il nastro

da t a t ′ rappresenta l'elaborazione per Y = F (X)

• Calcolabilità: secondo la tesi di Church non esiste unformalismo né una macchina concreta che possa calcolareuna funzione F non calcolabile secondo Turing

Modello teorico di macchina potenteRiconducibilità alla MdT (Turing equivalenza)Si può usare per verificare la potenza di altri modelli teorici

Esistono problemi non Turing risolubili es il famosoproblema dell'arresto

MdT Universale

• Teorizzata anche in relazione al problema dell'arresto

• MdTU: MdT in grado di imitare una qualsiasi particolare

macchina di Turing

• Primo modello di calcolatore programmabile

MdT normali eseguono un solo programma, che è scrittonella tabella delle quintuple

• Gli odierni computer sono in un certo senso delle MdTU

• Turing ha dimostrato che la MdT universale non è in gradodi decidere il problema dell'arresto (Turing-indecidibile)

Questo identifica un limite per tutti i meccanismicomputazionali

MdTU e Architettura di un eleboratore

• Un calcolatore secondo l'architettura di von Neumann è in

un certo senso la realizzazione concreta di una MdTU

• La memoria dati/programmi può essere considerata

l'equivalente del nastro

• La potenza computazionale è la medesima

• Si dice che una macchina di von Neumann è un

calcolatore universale

• MdTU è un modello astratto degli attuali elaboratori

Lezione 4 - Simulatore di una MdT



Marco Anisetti





Simulatore MdT

• Essitono gare di programmazione della macchina di Turing

• Ad ogni passo, la macchina legge un simbolo sul nastro ein accordo al suo stato corrente:

Decide il suo prossimo stato internoScrive un simbolo sul nastro e decide se spostare o meno latestina a sinistra o a destra di una posizione

• Un programma per tale macchina è una quintupla < stato

corrente, simbolo letto, stato prossimo, movimento,

simbolo scritto>

• Si possono creare programmi ad hoc per risolvere

problemi

• Si possono far eseguire a simulatori di macchine di Turing

per controllarne la correttezza

Simulatore: esempio

• Consideriamo ad esempio una MdT che modifica una

sequenza di Z rimpiazzando ogni Z in posizione dispari

con un A

• Supponiamo di avere sul nastro una sequenza predefinita

di Z

• Quali sono le quintuple che definiscono il programma?

Simulatore: Soluzione

• Ecco delle quintuple per il programma:

0 Z 1 > Z

1 Z 0 > A

0 - FINE - -

1 - FINE - -

• Provate a darla in pasto al simulatore che trovate

http://www.turingsimulator.net/• Sintassi e ordine della quintupla: (stato corrente,

simbolo-letto, stato prossimo, simbolo scritto,

movimento).

• Finestra a dx le sequenze di quintuple.

• Sotto la sequenza di caratteri che inizializza la macchina.

http://www.turingsimulator.net/

Simulatore: Esercizi(1)

• Dato un numero intero positivo n, n div 2 è il quoziente

della divisione di n per 2. Ad esempio, 6 div 2 = 3 ,

mentre 9 div 2 = 4 . Consideriamo il problema di

programmare una macchina di Turing che, dato un nastro

iniziale contenente una sequenza composta da nA

consecutive (con n > 1), termina la sua esecuzione

lasciando sul nastro la sequenza composta da n div 2 A

consecutive.

• Consiglio: Leggere e scrivere le A in zone differenti

• Programmare una Macchina di Turing che, dato un nastro

iniziale contenente una sequenza di cifre decimali,

termina la sua esecuzione lasciando sul nastro la

sequenza che si ottiene eliminando tutte le cifre 0 alla

sinistra della cifra diversa da 0 più a sinistra. Se la

sequenza iniziale è composta da sole cifre 0, la macchina

deve lasciare sul nastro un solo 0

Simulatore: Esercizi(2)

• Programmare una Macchina di Turing che, dato un nastro

iniziale contenente una sequenza di A e B , termina la sua

esecuzione lasciando sul nastro una sola T se la sequenza

iniziale contiene almeno una B , una sola F altrimenti

• Una sequenza si dice palindroma se la sua lettura da

sinistra verso destra è uguale alla sua lettura da destra

verso sinistra. Programmare una Macchina di Turing che,

dato un nastro iniziale contenente una sequenza di A e B,

termina la sua esecuzione lasciando sul nastro la sola S se

la sequenza iniziale è palindroma.

Tratti da una gara sulla programmazione della Macchina di Turing

Discussione(1)

• Questa prima esperienza di programmazione equivale alla

prima scrittura di una sorta di algoritmo

• Algoritmo: una sequenza ordinata e finita di passi non

ambigui costituita da operazioni elementari che portano

un ben determinato risultato in un tempo finito

• In questo caso abbiamo anche utilizzato un linguaggio

direttamente comprensibile all'esecutore (le quintuple)

• La macchina che esegue l'algoritmo non è una macchina

reale ma una macchina teorica

Discussione(2)

• Per ogni particolare istanza del problema abbiamo una

macchina di Turing differente

• Da notare che il linguaggio che usiamo per descrivere la

soluzione è un linguaggio formale comprensibile a chi

esegue poi la soluzione

• I passi dell'algoritmo sono quindi elementari per chi lo

esegue

• Le istruzioni che posso utilizzare per la descrizione

dipendono dalle capacità di chi esegue

Lezione 5 - Architettura di un elaboratore



Marco Anisetti





La Macchina di Von Neumann (1946)

• La macchina di Von Neumann costituisce l'architettura

della maggior parte dei Calcolatori

• John Von Neumann realizzò ENIAC (Electronic Numerical

Integrator and Computer)

• ENIAC era in grado di effettuare 300 moltiplicazioni al

secondo, ed occupava una stanza lunga più di 30 metri

• Fino al 1952, l'ENIAC fu il calcolatore più potente del

mondo. Poi entrarono in servizio due nuovi calcolatori,

EDVAC e ORDVAC, e nel 1955 ENIAC fu spento

definitivamente

Componenti fondamentali

• CPU, (Central Processing Unit):è in grado di acquisire,

interpretare ed eseguire le istruzioni di un Programma

• La Memoria Centrale: è il dispositivo dove si trovano le

informazioni necessarie all'esecuzione di un Programma,

ossia istruzioni e dati

• Dispositivi di Input/Output o Periferiche:

permettono di trasferire informazioni tra memoria centrale

e/o CPU e l'ambiente esterno

• Bus di sistema: collega tra loro i vari componenti

Componenti fondamentali (2)

Funzionamento

• La CPU coordina le varie attività, ed in particolare sioccupa delle fasi di

Fetch estrae istruzioni dalla memoriaDecode ne comprende il loro significatoExecute esegue quanto decodificato

• I contenuti della memoria sono indirizzati in base alla

posizione, indipendentemente dal tipo di dato o istruzione

contenuto

• Le istruzioni vengono eseguite in modo strettamente

sequenziale (limitazione principale del modello di Von

Neumann)

Esecuzione nella Macchina di Von

Neumann(1)

• Tre fasi: fetch, decode, execute

• Fetch si svolge a sua volta in quattro passi:

Il contenuto del PC (Program Counter) viene trasferitoattraverso il Bus indirizzi al Registro Indirizzi della MemoriaCentrale. Attraverso il Bus di Controllo viene specificataun'operazione di LetturaAvviene l'operazione di lettura dalla memoria centrale: ilcontenuto della cella specificato dal registro indirizzi vienecopiato nel registro dati della memoriaAttraverso il bus dati viene trasferita la nuova istruzionenell'IR (Instruction register) della CPU.Viene incrementato di 1 il valore del PC (ma in caso di saltoil PC sarà aggiornato con un altro valore)

Esecuzione nella Macchina di Von

Neumann(2)

• Decode: analisi dell'IR per identificare l'operazione da

eseguire (il suo codice operativo)

• Execute: dipende dal tipo di operazione

(aritmetico-logica, salto o trasferimento dati)

Estensioni alla Macchina di Von

Neumann(1)

• Elementi generali che determinano le prestazioni

Dimensione dei RegistriDimensione della RAMLa frequenza di clock della CPUAmpiezza del Bus DatiAmpiezza del Bus Indirizzi

• Elementi architetturali che determinano le prestazioni

Esecuzione sequenziale, un'istruzione dopo l'altraImpiego eccessivo del Bus di sistema per l'interscambiodelle informazioni con memoria e dispositiviTempi di accesso alla memoria centrale alti rispetto allavelocità di funzionamento della CPU

Estensioni alla Macchina di Von

Neumann(2)

• Architetture di tipo Pipeline: Esecuzione separata ed in

parallelo da parte di dispositivi appositi delle varie fasi di

un'istruzione (fetch, decode e execute):

• Utilizzo di memorie Cache (estremamente veloci ma

costose e di ridotte dimensioni) da inserire tra CPU e

Memoria centrale, dove conservare Dati e Istruzioni di uso

più frequente

• Architetture che utilizzano più processori:

Processori dedicati (es coprocessori matematici, GPU, DMA)Sistemi multiprocessore: architetture dotate di moltepliciCPU indipendenti.

Architettura di Von Neumann: conclusioni

• Architettura di riferimento per il programmatore

• Basilare per comprendere concetti come il costo

computazionale

• Legame con oggetti teorici come la MdTU

• Riferimento per estensioni a sistemi più evoluti

• Scomposizione tra istruzioni per risolvere un problema ed

esecutore che le esegue

Lezione 6 - Linguaggio, Automi e MdT



Marco Anisetti





Linguaggio e Automi(1)

• Linguaggio L è un sottoinsieme delle parole costruibili su

un alfabeto Σ, L ⊆ Σ∗.

• Il sottoinsieme di parole di un linguaggio può essere

descritto attraverso un riconoscitore o un generatore

• Il riconoscitore è implementato generalmente come una

macchina a stati finiti

• Formalmente, un automa finito M su un alfabeto Σ è unaquintupla

〈K ,Σ,δ,q0,F 〉

Linguaggio e Automi(2)

• Lo stato dell'automa rappresenta a pieno la sua

evoluzione a seguito di una sequenza di input

• Se si parla di automi con output allora avrò anche

l'alfabeto di output e non avrò stati terminali

• Alcuni problemi si possono descrivere come problemi di

accettazione di stringhe su un linguaggio

• Gli automi sono generalmente uno strumento concettuale

che nella programmazione servono per modellare diversi

problemi

Automi - MdT - Algoritmo

• Abbiamo visto una prima definizione intuitiva di algoritmo

• La MdT può essere vista come un modello matemtico di

algoritmo

• La MdT si descrive matematicamente usando i concetti di

insieme relazione e funzione che abbiamo visto

• La MdT è potente quanto la macchina di Von Neumann

• Ci son stati altri modelli importanti come il lambda calcolo

di Church

• Tesi di Church-Turing: qualsiasi algoritmo è modellabile

con una macchina di Turing

• Da cui il corollario che nessuna macchina potrà mai

risolvere problemi che una macchina di Turing non possa

risolvere

Programmazione e MdT universale

• Un MdTU è una MdT che:

Riceve la codifica di una MdT M e una stringa I ∈ ΣSimula i passi che la macchina M compirebbe se ricevessela stringa IRestituisce la stessa risposta (e lo stesso contenuto sulnastro)

• MdTU assume in input il programma che deve eseguire

• MdTU riceve in input la codifica di M che deve simulare

• M ha la funzione di consentire alla MdTU di interpretare e

di eseguire il programma rappresentato dalla MdT M

• Nota: come nel caso di Von Neumann programmi e dati

memorizzati nello stesso modo

• La MdTU tratta i programmi (M) e i dati (I) in maniera

sostanzialmente analoga ovvero essi vengono memorizzati

sullo stesso supporto, rappresentati utilizzando lo stesso

alfabeto di simboli ed elaborati in modo simile

Corso—Programmazione Fondamentidiprogrammazione ...

Documents

Transcript of Corso—Programmazione Fondamentidiprogrammazione ...