INTRODUZIONE AL SOFTWARE - pallacordarai.it al software.pdf · E’ chiaro che in base al principio...

A.ScaringellaA.A. 14-15

INFORMATICA E TECNOLOGIE DELLA INFORMATICA E TECNOLOGIE DELLA COMUNICAZIONE DIGITALECOMUNICAZIONE DIGITALE

pag.1

INTRODUZIONE AL SOFTWARE

L’informatica è la scienza che tratta della elaborazione delle informazioni.

Elaborare informazioni rientra nell’ambito delle attività quotidiane dell’individuo e delle forme associative.



pag.2

IMMAGINE realizzata da Alessandro MARABITTI = mappa concettuale

010010110000111100001000000001110



pag.3

Vediamo alcuni esempi:Vediamo alcuni esempi:

consultare una agenda telefonica;

seminare un campo di grano;

calcolare la probabilità di fare 6 al superenalotto.

ricerca del valore più grande all’interno di un insieme di valori;

raggiungere una data località servendosi di mezzi pubblici;

ordinamento di una sequenza di interi;

operazioni chirurgiche.



pag.4

L’elaborazione delle informazioni non riguarda soltanto ed esclusivamente l’ambito numerico o scientifico ma, al contrario, coinvolge tutte le attività umane.

In realtà ogni informazione, di qualsiasi natura essa sia, è codificata attraverso una tecnica matematica, nota come aritmetica binaria.



pag.5

Oggi è più che mai evidente che l’informatica risulta

essere uno strumento, un mezzo essenziale per la

comunicazione tra individui e per l’accesso alla

conoscenza nelle sue più svariate forme:

testuali, artistiche,

numeriche, filmiche,

sonore, scientifiche, etc..



pag.6

Elaborare informazioni significa ricercare soluzioni a determinati problemi.

Infatti, ognuno degli esempi sopra citati riguarda la ricerca di soluzioni ad un problema.

E’ bene introdurre una classificazione dei problemi, anche al fine di chiarire che

non tutti i problemi ammettono soluzioni o le ammettono in modo univoco.



pag.7

Problemi che ammettono sempre una sola soluzione

ad esempio dati due numeri interi dire se sono uguali e, in caso contrario, dire quale è il maggiore.

Una classificazione semplificata di problemi relativamente alle soluzioni che possono ammettere è la seguente:

E’ chiaro che in base al principio del terzo escluso, noto come tertium non datur, della logica matematica classica, due numeri interi o sono uguali oppure uno è maggiore dell’altro, per cui esiste sempre una e soltanto una soluzione a questo problema.



pag.8

Problemi che ammettono in generale più soluzioni

ad esempio cercare il numero telefonico di Mario Rossi.

Negli elenchi telefonici di grandi città infatti sono presenti numerosissimi Mario Rossi, ed in molti casi neppure l’esatta conoscenza dell’indirizzo riesce a dirimere la questione di quale Mario Rossi sia effettivamente quello che stiamo cercando noi: perciò siamo di fronte ad un problema che presenta, nella generalità dei casi, molte soluzioni.



pag.9

Problemi di cui non si sa se esistono soluzioni

Le congetture matematiche, cioè affermazioni di evidente realtà ma senza alcuna dimostrazione rigorosa e formale, costituiscono istanze di questa classe di problemi.

Ad esempio la congettura di Goldbach asserisce che ogni numero intero pari è somma di due numeri primi. Ed infatti qualunque numero pari ci venga in mente è effettivamente somma di due numeri primi: 6= 1 + 5;

22 = 3 + 19; e così via.

Però, di questo fatto, a prima vista semplice e (forse) intuitivo, non vi è nessuna dimostrazione matematica, al punto che su di esso sono anche sorte leggende ed ispirazioni per romanzi di successo.



pag.10

Dato un problema, l’obiettivo consiste nel determinare tutte le possibili soluzioni ad esso.

Ciò significa che occorre determinare un metodo di soluzione ed applicarlo ai dati del problema.

Ora, consideriamo un tipico e molto quotidiano problema: quello di eseguire una ricetta culinaria.

Prendiamo in considerazione la ricetta dello sciroppo d’amarena secondo l’Artusi:



pag.11

Siroppo di AmarenaPrendete ciliege marasche vere, le quali, benché mature, devono essere molto agre. Levatene i gambi e disfatele come l'uva quando si pigia per fare il vino; poi mettete da parte una manciata di noccioli per l'uso che vi dirò in appresso e riponete le ciliege con un bel pezzo di cannella intera in luogo fresco, entro a un vaso di terra per aspettarne la fermentazione, la quale deve durare almeno quarantott'ore; ma dal momento che le ciliege hanno cominciato ad alzare, affondatele e mescolatele di quando in quando ……



pag.12

Questo specifico metodo, come quasi tutti i metodi appartenenti alla categoria ‘ricette culinarie’, soffre però di alcune rilevanti caratteristiche negative sotto il punto di vista dell’informatica.

Infatti, già dalla prima frase:

Prendete ciliege marasche vere, le quali, benché mature, devono essere molto agre,

si entra in uno scenario in cui l’interpretazione, l’esperienza personale e la fantasia giocano un ruolo essenziale, senza le quali non si può dare corso all’opera.



pag.13

Infatti, cosa vuol dire:

marasche vere?

Chè forse ce ne sono di false, costruite artificialmente?

Ed ancora, quand’è che esse sono, allo stesso tempo,

benché mature… molto agre?



pag.14

La ricetta consiste di ‘istruzioni’

e la sua esecuzione richiede la capacità di

‘interpretare’ quelle istruzioni.

Così, dopo avere preso quel particolare tipo di ciliegie, l’Artusi raccomanda:

disfatele come l'uva quando si pigia per fare il vino,

istruzione che risulterà senz’altro ben precisa soltanto per poche persone.



pag.15

Non da ultimo, qualunque cuoco vorrà conoscere quanto tempo richiede l’esecuzione della ricetta.

L’Artusi dice:

…e riponete le ciliege con un bel pezzo di cannella intera in luogo fresco, entro a un vaso di terra per aspettarne la fermentazione, la quale deve durare almeno quarantott'ore.

E quanto bisogna aspettare perché inizi la fermentazione?



pag.16

Si consideri invece il seguente altro problema, anch’esso di attualità:

calcolare la media dei voti ottenuti in Informatica dagli studenti iscritti a Scienze della Comunicazione nello scorso anno accademico.

Se gli studenti che hanno superato l’esame sono n,

basterà addizionare tutti i voti riportati da ciascuno studente e poi dividere la somma ottenuta per n,

eventualmente arrotondando all’intero più prossimo.



pag.17

Cosa distingue i due problemi, sotto il profilo del metodo adottato per la loro soluzione? Mentre il problema della ricetta culinaria descritta dall’Artusi viene risolto mediante un metodo espresso in modo ambiguo e non sempre chiaramente eseguibile, tanto da lasciare abbondante spazio all’inventiva ed alla libera iniziativa. Si pensi ad esempio al famoso q.b. ampiamente utilizzato nella descrizione di ricette.

Al contrario il metodo adottato per calcolare la media dei voti è estremamente chiaro, non ambiguo, sicuramente eseguibile e certamente conduce a soluzione in un tempo finito.



pag.18

In informatica, i metodi che godono delle caratteristiche di:

non ambiguità, cioè ogni istruzione è univocamente interpretabile;

eseguibilità, cioè ogni istruzione è sicuramente eseguibile;

terminazione, cioè il metodo perviene al risultato dopo un tempo finito;

sono chiamati

algoritmi



pag.19

Un problema può essere considerato come una

funzione. Questa funzione è una relazione che lega dati in ingresso e dati in uscita.

I dati in ingresso (input) di un problema descrivono le informazioni rilevanti legate al problema stesso,

mentre i dati in uscita (output) descrivono una soluzione del problema.

Per esempio, la ricerca del valore più grande all’interno di un insieme di valori prevede come dati in ingresso i valori all’interno dei quali cercare il massimo, mentre prevede come dato in uscita il valore massimo.

Algoritmi



pag.20

Considerando il problema della ricerca del tragitto più veloce per spostarsi in aereo da una città all’altra, i dati in ingresso sono costituiti dalla descrizione di tutte le connessioni aeree più l’indicazione della città di partenza e della città di arrivo.

I dati in uscita, invece, descrivono il tragitto più veloce dalla città di partenza alla città di arrivo.

Nella teoria della calcolabilità si parte dall’osservazione che un algoritmo indica una sequenza di operazioni che devono essere eseguite in modo automatico da un esecutore. Esempio fatto in aula per la ricerca del massimo tra tre numeri interi dati.



pag.21

È quindi necessario precisare nel dettaglio, usando un approccio matematico, le caratteristiche che un esecutore deve avere.

A tal fine sono stati definiti diversi tipi di esecutori astratti (definiti sulla carta e non costruiti nella realtà anche se approssimabili con elaboratori reali) che hanno caratteristiche differenti; fra questi i più conosciuti sono gli:

•Automi a Stati Finiti e le

•Macchine di Turing.

Algoritmi



pag.22

Un algoritmo è una sequenza di operazioni che può essere eseguita in modo automatico. In pratica i metodi che possono essere programmati ed eseguiti da un calcolatore sono solo quelli appartenenti alla classe degli algoritmi.

Il metodo consistente nella ricetta culinaria dell’Artusi non è un algoritmo, in quanto non gode delle suddette proprietà di non ambiguità, eseguibilità e terminazione.

Esso, perciò, non può essere programmato ed eseguito da un calcolatore a meno di rendere non ambigue le frasi del tipo “ciliege marasche vere” ed interpretare in modo chiaramente eseguibile le istruzioni del tipo “disfatele come l'uva…etc”.

Algoritmi



pag.23

Quindi, un algoritmo è una procedura che risolve un dato problema in termini di: azioni (nell’esempio sono 6)

ordine di esecuzione delle azioni

Esempio: algoritmo “al mattino”.

1) Alzarsi dal letto (1°)

2) Togliersi il pigiama (2°)

3) Farsi la doccia (3°)

4) Vestirsi (4°)

5) Fare colazione (5°)

6) Dirigersi al lavoro (6°)

Algoritmi



pag.24

L’algoritmo modificato in cui si scambia l’ordine

delle azioni 3 e 4 produce risultati non desiderati

(quali ?)

L’ordine di esecuzione di un algoritmo si chiama

Controllo dell’algoritmo.

Algoritmi



pag.25

Il problema del calcolo della media è, senza alcuna

necessità di adottare varie interpretazioni,

sicuramente un algoritmo, e quindi può essere

programmato ed eseguito da un calcolatore.

Algoritmi



pag.26

Vediamo come la soluzione di questo problema può

essere decomposta in operazioni elementari in modo

da poter essere trovata da un calcolatore attraverso un

algoritmo.

L’ algoritmo deve poter essere tradotto in una

successione di istruzioni di un linguaggio di

programmazione. Ritorneremo su questo esempio

quando parleremo dei linguaggi.

Algoritmi



pag.27

Caso in cui il numero degli studenti è fissato.

Supponiamo che gli studenti siano 100. Il calcolo

della media può essere effettuato eseguendo la

successione delle seguenti operazioni, in cui

TOTALE e CONTATORE sono i nomi di due

variabili conservate ciascuna in una zona di

memoria del calcolatore.

Algoritmi



pag.28

Inizializzare TOTALE a 0 Istr. 1

ALGORITMO PER IL CALCOLO DELLA MEDIAogni

riga

è

una

Istruzione

Inizializzare CONTATORE a 1 Istr. 2

Finchè CONTATORE resta minore o uguale a 100 Istr. 3

prendere dall’input il prossimo voto Istr. 4

aggiungere il voto a TOTALE Istr. 5

aggiungere 1 a CONTATORE Istr. 6

Impostare il valore della media a TOTALE diviso 100 Istr. 7

Visualizzare la media. Istr. 8



pag.29

Un algoritmo può essere rappresentato graficamente con un diagramma di flusso costituito da simboli:

Se un diagramma di flusso deve rappresentare un algoritmo completo, all’inizio viene posto un simbolo ovale con la parola “inizio” (in inglese begin).

rettangoli, ovali, cerchietti, Rombi Linee di flussoI simboli sono connessi tra loro tramite linee, dette linee di flusso, orientate con frecce che indicano l’ordine con cui vengono eseguite le azioni.

Algoritmi



pag.30

Se invece il diagramma rappresenta solo una parte dell’algoritmo, all’inizio e alla fine si pongono dei cerchietti detti “simboli di connessione”.

I rombi vengono detti “simboli decisionali” e vengono posti nei punti dove la linea di esecuzione delle azioni può prendere diverse direzioni a seconda del verificarsi di alcune condizioni.

Analogamente all’uscita si pone un ovale con la parola “fine” (end).Il rettangolo, detto anche simbolo di azione, indica qualsiasi tipo di operazione.

Algoritmi



pag.31

Inizio

TOTALE = 0

CONTATORE = 1

CONTATORE <= 100 ?

prendere dall'input ilprossimo voto

aggiungere il voto a TOTALE

aggiungere 1 a CONTATORE

VisualizzaMedia

Media =TOTALE / 100

Fine

vero

falso

Algoritmi



pag.32

Caso in cui il numero degli studenti non è fissatoInizializzare TOTALE a 0Inizializzare CONTATORE a 0Effettuare l’input del primo voto (può essere il valore sentinella)Finchè l’utente non ha ancora digitato il valore sentinella aggiungere il voto a TOTALE aggiungere 1 a CONTATORE prendere dall’input il prossimo voto (può essere il valore sentinella)Se CONTATORE non è uguale a 0 Impostare il valore della media a TOTALE diviso CONTATOREVisualizzare la mediaAltrimenti

visualizzare “non è stato digitato alcun voto”



pag.33

Il valore sentinella è un valore con cui chi immette i voti segnala al calcolatore che è finita la lista dei voti. Questo valore deve essere scelto diverso dai possibili valori dei voti, ad esempio negativo (-1).

Anche su questo ritorneremo quando parleremo dei linguaggi di programmazione e tradurremo questa successione di istruzioni in un programma scritto in uno specifico linguaggio.

Algoritmi



pag.34

ALGORITMIESERCIZI IN AULA: La successione di Fibonacci è definita nel seguente modo: i primi due termini della successione sono 1, 1, il termine successivo è dato dalla somma dei due termini precedenti. Rappresentare con un diagramma di flusso l'ennesimo termine della successione.

Rappresentare con un diagramma di flusso un algoritmo per calcolare la somma dei primi n numeri dispari.

Trovare un algoritmo e disegnare il diagramma di flusso per calcolare il prodotto tra due numeri interi positivi usando l'operazione di somma.

Trovare un algoritmo per calcolare il quoziente e il resto della divisione tra due numeri interi positivi e rappresentarlo con un diagramma di flusso.

Trovare un algoritmo per determinare il massimo tra tre numeri e rappresentarlo con un diagramma di flusso.

STUDIO e ESERCIZI A CASA: Libro di testo “Introduzione all'Informatica” da pag. 319 a pag. 324



pag.35

Per fissare le idee, gli elementi che entrano in gioco nel trattamento delle informazioni sono:

i problemi;

le informazioni: sono informazioni quelle che vengono date in ingresso al problema e sono parimenti informazioni quelle che si vogliono ottenere in uscita;

un metodo di soluzione;



pag.36

un esecutore: si parla di un esecutore, non necessariamente di un calcolatore; infatti, l’elaborazione delle informazioni può essere effettuata anche da umani; il calcolatore è soltanto un esecutore più efficiente, preciso, veloce, economico;

le interfacce verso l’esterno: sono le modalità e gli strumenti attraverso i quali un esecutore riceve/fornisce le informazioni.



pag.37

esecutore

problemi

metodo

interfacce

informazioni



pag.38

PROBLEMIPROBLEMI

RISOLUBILI NON RISOLUBILI

TRATTABILINON

TRATTABILI

NON ESISTE NON SI SA SE ESISTE

LA SOLUZIONE

E’INDECIDIBILE



pag.39

COMPLESSITÀ DEGLI ALGORITMI E DEI PROGRAMMI

È la misura dell’efficienza di un algoritmo o di un programma che lo implementa.

Può essere riferita:

Al tempo di esecuzione di un programma. Questa misura, che indichiamo con T(n) è pressoché equivalente al numero di istruzioni che devono essere eseguite. Infatti ha poca importanza che una moltiplicazione sia, supponiamo, dieci volte più lenta di un’addizione, dato che entrambe le operazioni richiedono tempi costanti, seppur diversi. Infatti non è tanto la differenza di costo della singola operazione a far aumentare il tempo, ma il numero di volte che le operazioni sono eseguite. Nel seguito riferiremo la complessità al tempo di esecuzione del programma.

Alla memoria richiesta per eseguire il programma



pag.40

Per esprimere la complessità dei programmi è necessario fare riferimento alla DIMENSIONE DEL PROBLEMA.

Essa può intuitivamente essere considerata come il numero di valori da elaborare cioè la dimensione dei dati in ingresso (input). Ad esempio, ordinare un insieme di 1.000 valori richiede senz’altro meno tempo che ordinare un insieme di 1.000.000 di valori.

Pertanto, la dimensione del problema è nel primo caso 1.000 e nel secondo caso 1.000.000.

In generale, la dimensione del problema è indicata dalla lettera n.

COMPLESSITÀ DEGLI ALGORITMI



pag.41

La complessità si esprime attraverso una funzione matematica e può essere dei seguenti tipi:

Costante: quando il tempo di esecuzione del programma è indipendente dalla dimensione del problema.

Ad esempio, il tempo richiesto (come numero di operazioni) per calcolare le radici di una equazione algebrica di secondo grado è sempre lo stesso, e non dipende dalla dimensione dei coefficienti dell’equazione. ax2+bx+c=0




pag.42

Complessità di un Algoritmo

y=t

x è Dimensione del problema



pag.43

Logaritmica: quando il tempo di esecuzione è proporzionale al logaritmo della dimensione del problema.

Ad esempio, il problema di cercare il nome di una persona in un elenco ordinato alfabeticamente, ha complessità O(log n), dove n è il numero di elementi presenti nell’elenco e O è il simbolo per esprimere la complessità nel senso che T(n) è stimabile, a meno di una costante, con il logaritmo di n.Così, se l’elenco avesse 8 nomi, la ricerca richiederebbe al massimo l’esecuzione di Cx3 istruzioni, dove C è una costante (log 8=3 se il logaritmo è in base 2 ma un’altra base (ad esempio 10) non farebbe altro che cambiare la costante C), mentre se ne avesse 1024 allora richiederebbe al massimo l’esecuzione di Cx10 istruzioni (log 1024=10 in base 2). Ricordiamo che il logaritmo di un numero è l'esponente a cui bisogna elevare la base per ottenere il numero.




pag.44


Il numero delle operazioni da eseguire cresce come una costante per il Logaritmo di n.



pag.45

Lineare: quando il tempo di esecuzione è proporzionale alla dimensione del problema. Cioè a un incremento di n corrisponde un ugual incremento della funzione T(n), a meno di costanti.

Ad esempio, la fusione di due insiemi ordinati di n elementi ciascuno in un unico insieme ordinato di 2n elementi, richiede l’esecuzione di 2n istruzioni.

Così, se ciascun insieme di partenza ha 16 elementi, devono essere eseguite 32 istruzioni.




pag.46




pag.47

Polinomiale: quando il numero di istruzioni da eseguire è espresso da un polinomio di grado k. In questo caso si dice che la complessità è polinomiale di ordine k.

C’è la possibilità che per un algoritmo non basti un tempo Lineare, per esempio un algoritmo potrebbe richiedere un tempoche cresce come n alla terza cioè n per n per n. Una funzione T(n) è detta polinomiale se cresce come n alla k per un k costante.Perciò si parla di complessità




pag.48




pag.49

Ad esempio, il problema del commesso viaggiatore:

Supponiamo di avere una rete autostradale che collega n città ed i cui tronchi hanno lunghezze diverse. Determinare un circuito che tocchi tutte le città una sola volta percorrendo il minimo percorso.

Esponenziale: quando il numero di istruzioni da eseguire è esprimibile da una funzione esponenziale della dimensione del problema. E vi sono complessità ancora maggiori che, come la complessità esponenziale, si dicono superpolinomiali.

COMPLESSITÀ DEGLI ALGORITMICi sono poi dei casi in cui T(n) cresce più rapidamente di un polinomio: ad esempio come exp(cn), una funzioneEsponenziale di n. In questo caso si parla di complessità



pag.50




pag.51




pag.52

PROBLEMI TRATTABILI E PROBLEMI INTRATTABILI

Tra tutti i problemi che ammettono soluzioni, si distingue tra quelli TRATTABILI e quelli NON TRATTABILI.

Problemi trattabili: hanno una complessità al massimo polinomiale di ordine inferiore alla decina.

Problemi intrattabili: hanno una complessità esponenziale o comunque superpolinomiale o anche polinomiale di ordine superiore alla decina.



pag.53

2x108 secoli6.5 anni0.059sO(3n)

35.7 anni17.9 m0.001sO(2n)

5.2 m24.3s0.1sO(n5)

0.125s0.027s0.0001sO(n3)

0.00005s0.00003s0.00001sO(n)

0.0000054s0.000005s0.000003sO(log n)

n=50n=30n=10

Tempo di esecuzione di una istruzione: 1 µs (1 micro secondo = 0.000001 s)



pag.54

I problemi che hanno complessità esponenziale sono detti intrattabili perché anche in presenza di un calcolatore potentissimo, richiedono comunque tempi inammissibili per la loro soluzione.

Ad esempio, nella tabella precedente il problema

che ha complessità O(3n) richiederebbe, per n=50:

200.000 secoli utilizzando un calcolatore che esegua una istruzione in 1 ns (nanosecondo=1miliardesimo di secondo)

200 secoli utilizzando un calcolatore che esegua una istruzione in 1 ps (picosecondo= 1 millesimo di nanosecondo)



pag.55

CalcolabilitàGli algoritmi descrivono procedimenti che un calcolatore elettronico deve eseguire per risolvere un particolare problema.

E' naturale chiedersi se tutti i problemi possano essere risolti tramite l'uso del calcolatore, in altri termini, se tutti i problemi possano essere risolti dagli algoritmi.

Per esempio possiamo essere interessati a usare un calcolatore per trovare il tragitto aereo più veloce per muoverci da una città a un'altra passando, eventualmente per alcune città intermedie.



pag.56

CalcolabilitàGli algoritmi descrivono procedimenti che un calcolatore elettronico deve eseguire per risolvere un particolare problema.

E' naturale chiedersi se tutti i problemi possano essere risolti tramite l'uso del calcolatore, in altri termini, se tutti i problemi possano essere risolti dagli algoritmi.



pag.57

Un altro tipo di problema potrebbe essere verificare, dato un algoritmo e una particolare istanza di dati in ingresso, quale sia l'ordine di grandezza del tempo necessario per restituire un risultato. Per rispondere in modo esauriente a questo tipo di quesiti è necessario definire in modo chiaro che cosa intendiamo per problema e che cosa intendiamo per algoritmo.

Calcolabilità



pag.59

Esiste una particolare branca

dell'informatica, chiamata teoria della

calcolabilità, che si propone di studiare in

modo matematico problemi del tipo cui

abbiamo accennato.

Nel seguito descriveremo che cos'è un

problema e che cos'è un algoritmo.

Calcolabilità



pag.60

ESECUTORI: MACCHINA di TURING

Nel paragrafo precedente abbiamo introdotto il problema di definire un esecutore automatico che abbia una memoria in cui leggere e scrivere simboli durante la computazione.

Definiremo ora più precisamente le macchine di Turing (MdT), un tipo di esecutore automatico equipaggiato con memoria.

La memoria di una MdT è un nastro di lunghezza illimitata sul quale possono essere collocati dei simboli. I simboli sul nastro sono posti in sequenza, uno dopo l'altro.



pag.61

Alan Mathison Turing fu un matematico e logico matematico britannico (1912 -1954). Pioniere della scienza dell'informazione e dell'intelligenza artificiale, ha legato il suo nome, in particolare, alla macchina di Turing, con cui l'autore risolveva il problema della decidibiltà lanciato nel 1900 da Hilbert. La questione posta da Hilbert era se esistesse sempre un metodo meccanico attraverso cui, dato un qualsiasi enunciato matematico, si possa stabilire se esso sia vero o falso.




pag.62

Un tale algoritmo sarebbe stato in grado di risolvere tutti i problemi matematici.

La soluzione proposta da Turing consiste nell'utilizzo di un modello matematico capace di simulare il processo di calcolo umano, scomponendolo nei suoi passi più elementari.

La macchina è formata da una testina di lettura e scrittura con cui è in grado di leggere e scrivere su un nastro potenzialmente infinito partizionato in caselle. Ad ogni istante di tempo t1, la macchina si trova in uno stato interno s1 ben determinato, risultato dell'elaborazione compiuta sui dati letti.




pag.63

DefinizioneUna macchina di Turing (o più brevemente MdT) è una macchina ideale che manipola i dati contenuti su un nastro di lunghezza infinita, secondo un insieme prefissato di regole ben definite. In altre parole, è un modello astratto che definisce una macchina in grado di eseguire algoritmi e dotata di un nastro infinito su cui può leggere e/o scrivere simboli.




pag.64

Essa ha la particolarità di essere retta da regole di natura

molto semplice e si dimostra che è in grado di

eseguire tutte le elaborazioni effettuabili dagli altri

modelli di calcolo noti all'uomo.

Di conseguenza si è consolidata la convinzione che per

ogni problema calcolabile esista una MdT in grado di

risolverlo: questa è la cosiddetta congettura di Turing, la

quale postula in sostanza che per ogni funzione calcolabile

esista una macchina di Turing equivalente.




pag.65

La macchina di Turing è composta dai seguenti elementi:

1. Nastro: non si pone un limite superiore alla capacità di memoria. Questa, in una MdT, è rappresentata da un nastro monodimensionale infinito, costituito da una sequenza lineare di caselle quadrate o celle, che viene considerata infinita in entrambe le direzioni.

Ogni casella sul nastro o è vuota, o contiene un singolo segno. Così benché il nastro venga considerato infinitamente lungo, su di esso deve essere presente un numero finito di segni reali.




pag.66

MACCHINA di TURING : Nastro + Testina



pag.67


2 Testina: non si pone un limite alla durata dei processi di calcolo e si assume anche che una tale macchina funzioni sempre perfettamente.

I processi di calcolo eseguibili da una MdT sono estremamente elementari: dotata di una testina di lettura/scrittura che può osservare solo una casella per volta, essa può stampare un simbolo da un alfabeto finito sulla casella osservata o spostare la testina di lettura di una casella, a sinistra, o, a destra della casella osservata.



pag.68

MACCHINA di TURING : Nastro + Testina



pag.69


1 Alfabeto: i simboli che una MdT può utilizzare sono in numero finito, l’insieme di questi simboli è l’alfabeto di una MdT.



pag.70


4 Stato interno: un altro importante elemento delle MdT è lo stato interno che è la configurazione memorizzata dalla macchina in base agli ingressi (input) presentatesi in istanti precedenti (cioè in base a ciò che ha potuto leggere sul nastro).

Gli stati interni devono essere in un numero finito.



pag.71

MACCHINA di TURING: Gif animata di RosarioVanTulpe



pag.72

MACCHINA di TURING: Gif animata di RosarioVanTulpe



pag.73


Configurazione: definiamo configurazione di una MdT in una data fase di calcolo la coppia ordinata costituita dallo stato interno che essa presenta in quel momento e dal simbolo osservato dalla testina.



pag.74

L'importanza della MdT deriva dal fatto che permette di compiere tutte le elaborazioni effettuate mediante le macchine apparse nella storia dell'umanità e perfino le dimostrazioni matematiche che l'umanità ha raccolto nel corso della sua storia, diciamo a partire da Euclide.

Infatti, tutte le macchine che si conoscono possono essere ricondotte al modello estremamente semplice a macchine di Turing. Ad esempio, anche i più complessi computer odierni possono essere ricondotti a questo modello.




pag.75

Innanzitutto, si individuano macchine relativamente semplici che effettuino le operazioni aritmetiche di base;

Quindi, si individuano versioni della MdT più ricche di risorse, che consentano di descrivere più agevolmente operazioni via via più complesse, ma tutte riconducibili a numeri naturali;

Proseguendo in questa direzione, si introducono MdT dotate di memorie complesse, come sequenze di nastri e memorie bidimensionali e tridimensionali.




pag.76


A questo punto si deve anche aggiungere che della MdT risulta opportuno anche considerare macchine formali che sono in grado di portare avanti contemporaneamente diverse elaborazioni, in numero illimitato.

Esse possono considerarsi idealizzazioni di sistemi di computer che operano in parallelo.



pag.77


Con questo ragionamento si ottengono macchine formali che, in linea di principio, si possono ricondurre alla MdT introdotta inizialmente, ma che possono essere programmate molto più agevolmente, e soprattutto che possono essere realizzate con le tecnologie disponibili oggi.

Dimostrare che una di queste macchine può risolvere un certo problema vuol dire dimostrare che anche la MdT può risolverlo. La conclusione è che tutte le computazioni effettuabili dalle macchine a noi note sono effettuabili anche dalla MdT.



pag.78


Una macchina che permetta di risolvere tutti i problemi risolvibili anche dalla MdT si dice "Turing-Equivalente".

La conclusione è che tutte le computazioni effettuabili dalla MdT sono effettuabili anche da tutte le macchine di cui si è in grado di dimostrare l'equivalenza con la MdT.



pag.79

Anche se la lunghezza del nastro è illimitata, il numero di simboli importanti in ogni istante della computazione risulta essere finito.

Questo deriva dal fatto che i dati in ingresso devono essere in quantità finita, in quanto un algoritmo non ha la possibilità di effettuare delle elaborazioni su una quantità infinita in ingresso.




pag.80

ESECUTORI: MACCHINA di TURINGTutte queste considerazioni rendono ragionevole sostenere la congettura di Turing.

Esse riguardano la calcolabilità degli algoritmi, e non la loro trattabilità: macchine equivalenti sono realizzate in modo diverso, e quindi possono eseguire la stessa computazione con un diverso numero di passi o dispendio di risorse.



pag.81

Ad esempio, un calcolo che un odierno computer esegue in pochi secondi richiederebbe un numero enorme di passi se eseguito su un meccanismo dotato di dispositivi operativi estremamente semplici come quelli della MdT.

In sintesi, macchine diverse possono risolvere gli stessi problemi con programmi che hanno una diversa complessità computazionale.




pag.82

Come per gli Automi a Stati Finiti o, il lambda

calcolo o λ-calcolo, una MdT ha associati un

numero finito di stati: in base allo stato e al

simbolo che si trova sotto la testina in un certo

istante del calcolo, la MdT decide se e con quale

simbolo sostituire il simbolo letto, in quale

direzione muovere la testina (a destra oppure a

sinistra) e in quale nuovo stato passare.




pag.83

Linguaggi di programmazione

I linguaggi di programmazione sono alla base dell’Informatica, perché consentono di generare il software,

sia quello di base (Sistemi Operativi), sia quello applicativo utilizzato nei vari aspetti dell’elaborazione di dati,



pag.84

come ad esempio: operazioni eseguite da un programma, sequenze di passi eseguiti da una macchina per l’automazione di processi produttivi, controlli e protocolli di telecomunicazione, le interfacce utente, raccolta di dati da Internet, ecc.




pag.85

I linguaggi di programmazione occupano una posizione intermedia tra il linguaggio naturale (tipicamente inglese), comprensibile dalle persone, e quello binario (composto da sequenze delle sole cifre 0 e 1), comprensibili solo dal computer, l'unico linguaggio che pilota direttamente le unità fisiche dell'elaboratore (memoria centrale e cpu).




pag.86

Qualsiasi linguaggio di programmazione , si compone di parole e di regole;

• le prime generate da un dato alfabeto o simboli secondo un metodo prefissato,

• le seconde costituiscono la portante grammaticale e sintattica del linguaggio che consente di aggregare le parole per formare frasi di senso compiuto, cioè frasi ammissibili in quel particolare linguaggio.




pag.87

Grammatiche di ChomskyOgni linguaggio di programmazione è costituito da

• un suo proprio alfabeto,

• da una propria grammatica,

• da una propria sintassi e

• da una propria semantica.

La sintassi riguarda l’insieme di regole che devono essere rispettate per scrivere programmi corretti.



pag.88

La costruzione delle stringhe di caratteri avviene secondo una metodologia che, in informatica è nota con il nome “Grammatiche formali”.

Una grammatica formale (come introdotta da Chomsky) è un sistema che comprende:

• variabili terminali,

• variabili,

• un insieme di regole di produzione e

• un insieme di assiomi.

Grammatiche di Chomsky



pag.89

La grammatica permette di operare su stringhe di simboli attraverso le regole di produzione che fanno passare da una stringa ad un’altra a partire dagli assiomi.

Il linguaggio generato dalla grammatica è l’insieme di stringhe composte solo da variabili terminali che si possono ottenere a partire dagli assiomi operando con le regole di produzione.

Grammatiche di Chomsky



pag.91

• Queste due modalità devono essere paragonate in termini di interattività, velocità di attivazione (quella iniziale) e velocità di esecuzione.

• INTERATTIVITA’• VELOCITA’ DI ATTIVAZIONE• VELOCITA’ DI ESECUZIONE• INTERPRETE (traduce ed esegue frase per frase)• COMPILATORE (traduce tutto il discorso)

Linguaggi e modalità di esecuzione



pag.92

Il BASIC nasce come interprete. Nelle sue evoluzioni conserva la struttura di interprete, ma allo stesso tempo offre oggi anche la modalità compilatore (MS-QUICKBASIC).

Alla categoria degli interpreti appartengono i servizi di sistema capaci di interpretare a run-time i cosiddetti script (macro istruzioni capaci di indirizzare il funzionamento di parti di software, ad esempio i Java-script).




pag.93

Il PASCAL e il FORTRAN sono invece compilatori. La funzione “DEBUG” permette di interagire per cercare gli errori

sparsi (trasforma il programma in una sorta d’interprete durante l’esecuzione).

Si può compilare un programma scritto in PASCAL o FORTRAN appendendolo al DEBUG. Quando si trova l’errore però si deve tornare nel programma sorgente, correggere e poi ricompilare. Con questo tipo di funzione DEBUG attivato si perde in velocità di esecuzione.

Le funzioni DEBUG sono poco intuitive in quanto sono incapsulate dentro il programma eseguibile.

Esistono vari tipi di linguaggi: - Assemblatori [ASSEMBLER]- Procedurali- Non procedurali




pag.94

1) I linguaggi Assemblatori sono capaci di rappresentare degli “mnemonici”, a cui poi si può associare una parola, che verrà tradotta in linguaggio macchina. Sono dei traduttori “uno a uno” del linguaggio macchina. Sono dei linguaggi che vengono adattati ai computer a seconda della loro architettura.

Gran parte del Sistema Operativo è scritto in ASSSEMBLER.

2) Esistono diversi linguaggi procedurali, o "imperativi", che sono linguaggi attraverso i quali si devono specificare esattamente la sequenza di azioni da eseguire per svolgere una determinata azione. Questi sono i più usati ancora oggi, quali:




pag.95

Linguaggi e modalità di esecuzione- BASIC => Beginner's All-purpose Symbolic Instruction Code, esiste laversione QUICK che è più veloce e più avanzata; nella versione Visual-

Basic è in grado di manipolare oggetti.

- FORTRAN => FORmulas TRANslator, versioni (II), V e VI, ANSIXX (con XX si indica l’anno di rilascio). Questo tipo di linguaggio è particolarmente adatto per tradurre le formule matematiche;

- ALGOL => ALGOrithmic Language, è un linguaggio ormai poco usato. Questo tipo di linguaggio è noto per descrivere con la massima facilità gli algoritmi (ALGORITMO: descrizione procedurale che permette di arrivare alla soluzione del problema);

- PASCAL => è una forma avanzata dell’ALGOL, adatto per la programmazione strutturata.



pag.96

- C/C++ => è un linguaggio formale che assomiglia molto al PASCAL, ma che anche permette

un controllo della macchina come se fosse in parte un assembler. E’ meno leggibile del

PASCAL. Gli oggetti sono dei moduli software che permettono un più rapido e sicuro

sviluppo (scrittura) di programmi riutilizzando dei “pezzi”, dei moduli, già scritti e provati

diffusamente. Tali moduli vengono visti ed utilizzati come “scatole chiuse” delle quali è

fornita la descrizione in termini di proprietà (informazioni di configurazione incapsulate

dentro l’oggetto, accessibili solo tramite operazione controllate dall’oggetto stesso) e metodi

(azione che l’oggetto può svolgere se sollecitato dal programma o in risposta ad eventi

predefiniti). considerato un linguaggio da professionisti; la versione C++(o Visual-C)

è in grado di manipolare oggetti;




pag.97

- Java => è un linguaggio proposto dalla Sun-Microsystems negli ultimi anni per applicazioni di rete; sintatticamente è simile al C++ (con alcune restrizioni); la forza del linguaggio è quella di non compilare il risultato in linguaggio macchina, ma piuttosto in un byte-code intermedio, che è in grado di essere eseguito in varie macchine e sistemi operativi, permettendo la scrittura di applicazioni platform independent e intrinsecamente virus free, a patto che su ogni piattaforma esista la macchina virtuale (un interprete del byte code) Java e che questa si comporti nello stesso modo su ogni altra piattaforma. Il byte code è anche libero da virus (virus free) per definizione, dato che non è eseguibile, ma deve essere interpretato dalla macchina

virtuale, che non accetta operazioni di sistema illegali.




pag.98

- Perl un linguaggio “vecchio” di soli pochi anni, nato nel 1987 con l’obiettivo di essere facile ed aperto, distribuito gratuitamente in forma di software aperto, particolarmente adatto a integrare applicazioni Internet e altri linguaggi.

- COBOL=> Common Business Oriented Language, questo linguaggio è stato concepito per descrivere le risoluzioni di problemi di ordinamento e è un linguaggio più gestionale che scientifico; si utilizza ancora per la manutenzione dei sistemi legacyi42.

3) I linguaggi non procedurali, o "non imperativi", permettono l'esecuzione di azioni specificando il risultato da ottenere piuttosto che i passi mediante i quali ottenerlo. Si utilizzano specialmente nel campo dell’Intelligenza Artificiale (AI) e dei Sistemi Esperti (ES), come pure nel campo dei DATA BASE.




pag.99

- LISP=> LISt Processor, primo linguaggio "non imperativo", in grado di trattare liste di qualsiasi natura, numeri compresi.

Un programma lisp è un insieme di funzioni matematiche composte fra loro in modo che ciascuna di esse ricavi i propri dati da quella precedente.

Il LISP possiede una sintassi semplice e uniforme che lo rende ideale per manipolare informazioni e confrontare problemi.




pag.100

- PROLOG=> PROgramming in LOGic, "Programmare in logica" vuole dire non specificare le operazioni da eseguire per risolvere i problemi proposti, in quanto le procedure risolutive vengono svolte automaticamente dal computer.

I programmi adottano una tecnica di ricerca inversa (backtracking): il PROLOG cerca la soluzione in base a una serie di regole concatenate, ponendosi di volta involta un nuovo obiettivo da raggiungere




pag.101

Si definiscono legacy quei sistemi software, sviluppati e messi a punto nel corso di decenni (come le applicazioni bancarie, di sicurezza militare, etc.), che hanno raggiunto un elevato grado di affidabilità e per i quali è troppo “rischioso” (magari sbaglierebbero i conti in qualche caso particolare con enormi danni economici) un rifacimento con tecniche e linguaggi moderni.




pag.102

- HTML=> Hyper Text Mark-up45 Language, definito attraverso il Metalinguaggio SGML (Standard General Mark-up Language), usato per la definizione di ipertesti che sfruttano le risorse di rete (internet).

- XHTML=> eXtensible (eXtensive) HTML, è un’estensione dell’HTML definita attraverso il metalinguaggio XML (extensible Mark-up Language, sottoinsieme del SGML), con la quale si struttura il documento per una sua più agevole esplorazione.

- VRML=> Virtual Reality Modeling Language, permette la creazione diipertesti (pagine web) tridimensionali.- J-script=> Java script, per l’esecuzione di applet (oggetti programma) Java

all’interno di un browser, in modo da animare la pagina web, assumendone un controllo profondo con l’HTML.

- ActiveX=> Alternativa Microsft alla tecnologia Java e Java script (di Sun- Microsystems).

- PHP Hypertext PreProcessor, è un linguaggi di script, operante dal lato server (in modo da non rivelare il codice ai client). Offre agli sviluppatori di applicazioni web un insieme completo di strumenti per costruire siti dinamici.

- XML (extensible Mark-up Language) linguaggio semantico per il WEB.

Linguaggi di MARCATURA



pag.103

LA RICORSIONE

In informatica viene detto algoritmo ricorsivo un algoritmo espresso in termini di se stesso,

ovvero in cui l'esecuzione dell'algoritmo su un insieme di dati comporta la semplificazione o suddivisione dell'insieme di dati e l'applicazione dello stesso algoritmo agli insiemi di dati semplificati.



pag.104

LA RICORSIONETale tecnica risulta particolarmente utile per eseguire

dei compiti ripetitivi su di un set di variabili in input.

L'algoritmo richiama se stesso generando una sequenza di chiamate

che ha termine al verificarsi di una condizione particolare che viene

chiamata condizione di terminazione, che in genere

si ha con particolari valori di input.



pag.105

LA RICORSIONETale tecnica risulta particolarmente utile per eseguire

dei compiti ripetitivi su di un set di variabili in input.

L'algoritmo richiama se stesso generando una sequenza di chiamate

che ha termine al verificarsi di una condizione particolare che viene

chiamata condizione di terminazione, che in genere

si ha con particolari valori di input.



pag.106

Quando l'algoritmo viene eseguito la prima volta, il valore di n viene confrontato con 0 e con 1, nel caso in cui il valore sia diverso, la procedura viene chiamata ricorsivamente su valori più piccoli sino a quando n non risulta uguale ad 1, nel qual caso il risultato è noto e può essere restituito dalla funzione attuale a quella che l'aveva in precedenza chiamata.

I risultati restituiti da ognuna delle procedure ricorsive vengono di volta in volta moltiplicati. Il penultimo valore restituito sarà proprio uguale ad (n-1)!, quest'ultimo verrà moltiplicato per n e l'algoritmo potrà restituire il risultato cercato.

LA RICORSIONE

Possibile classificazione dei linguaggi di programmazioneSe è vero che tutti i linguaggi di programmazione sono costituiti da un lessico, una sintassi ed una semantica, è altrettanto vero che questi tre elementi non sono sufficienti a caratterizzarli, in quanto gli aspetti più significativi dei linguaggi di programmazione risiedono essenzialmente nel modello di calcolo a cui si ispiranoed al livello di qualità dei programmi che riescono a supportare.

Linguaggi




pag.107

La tradizionale classificazione di linguaggi di programmazione è la seguente:

• linguaggi imperativi,

• linguaggi funzionali,

• linguaggi dichiarativi.

Linguaggi



pag.108

Esistono infatti linguaggi imperativi orientati agli oggetti, linguaggi funzionali orientati agli oggetti e linguaggi logico/dichiarativi orientati agli oggetti.

Per questi motivi, nel seguito si illustreranno le caratteristiche fondamentali dei linguaggi di programmazione prendendo a riferimento l’orientamento agli oggetti e facendo riferimento, quando ne sarà necessario, al linguaggio Java.

Il paradigma object_oriented programming è basato su due concetti fondamentali: i tipi astratti di dato ed i meccanismi di ereditarietà.

Linguaggi



pag.109

INTRODUZIONE AL SOFTWARE - pallacordarai.it al software.pdf · E’ chiaro che in base al principio...

Documents

Transcript of INTRODUZIONE AL SOFTWARE - pallacordarai.it al software.pdf · E’ chiaro che in base al principio...