PIANO NAZIONALE FORTIC/UMTS
PERCORSO FORMATIVO A
TAAA1043
SCUOLA ELEMENTARE G.MARCONI- MARTINA FRANCA
MODULO 8
DAL PROBLEMA AL PROGRAMMA
TUTOR INS. GIUSEPPE CAMPANELLA
MAPPA DEL MODULO
PROBLEMI E ALGORITMI
CONOSCERE IL CONCETTO
DI PROBLEMA
CONOSCERE LE PRINCIPALI
STRATEGIE RISOLUTIVE
CONOSCERE QUANTI TIPI
DI
PROBLEMI ESISTONO
SAPER ANALIZZARE
UN PROBLEMA
AUTOMI ESECUTORI
STRUTTURA E CARATTERI
DELL’AUTOMA
La macchina di
Touring
CONCETTO INTUITIVO
DI ALGORITMO
LE STRUTTURE DI
CONTROLLO
RAPPRESENTAZIONI
DELL’ALGORITMO
LINGUAGGI
PRINCIPI LOGICI DEI
LINGUAGGI FORMALI
SINTASSI E SEMANTICA
DEI LINGUAGGI
LINGUAGGI NATURALI
E FORMALI
LA COMUNICAZIONE
TRA UOMO E MACCHINA
EVOLUZIONE DEI
LINGUAGGI DI PROG.
DALL’ALGORITMO AL
PROGRAMMA
PRIMA GENERAZIONE
DI LINGUAGGI
I MODERNI LINGUAGGI
DI PROGRAMMAZIONE
OBIETTIVI DEL MODULO
•Conoscere alcuni concetti fondamentali
dell'informatica: algoritmo, automa, linguaggio
formale;
•Essere in grado di cogliere l'intreccio tra alcuni
risultati della matematica e della logica dei primi
decenni del secolo scorso ed i successivi sviluppi
e applicazioni che questi hanno avuto in campo
informatico.
Macrotematiche del modulo
Automi Esecutori
Problemi ed algoritmi
Linguaggi
Problemi ed algoritmi
Col termine problema o situazione problematica
s’indica una situazione che pone delle domande cui si
devono dare risposte
Risolvere il problema vuol dire uscire da tale situazione.
Un problema consta dei seguenti elementi:
I dati, ossia ciò che è noto, l’istanza che si deve affrontare e che
possiamo indicare col termine input.
I risultati, ossia ciò che si deve determinare, gli elementi incogniti
la cui determinazione fornisce l’output.
Le condizioni, che sono in generale le limitazioni cui devono
soggiacere i risultati.
TIPOLOGIE DI PROBLEMI
Per cogliere il collegamento tra la struttura di un problema ed
i metodi risolutivi per esso adottati, è opportuno tenere conto
della seguente ripartizione dei vari tipi di problemi in classi:
Problemi di decisione, in cui l’output è fornito dal valore vero o falso
a seconda che l’input soddisfi o meno una determinata proprietà.
Problemi di ricerca, in cui, nello spazio delle soluzioni possibili (spazio di ricerca),
si vuole determinare quella soluzione che soddisfa le condizioni poste dal problema,
che viene detta soluzione ammissibile.
Problemi di ottimizzazione, in cui alle soluzioni ammissibili è associata
una misura e si deve determinare la soluzione ammissibile la cui misura è massima o
minima.
TIPOLOGIA LOGICA DEI PROBLEMI
Si ha anche una suddivisione “logica” dei problemi in 3 classi:
Impossibili: non esiste una soluzione
Indecidibili: non è possibile decidere se
la soluzione esiste
Intrattabili: le risorse necessarie per la
soluzione, in termini di tempo e spazio,
sono proibitive.
Improponibili: nessuno è disposto a
perderci tempo
Esiste un meccanismo “dedicato” allo scopo
L’ANALISI DI UN PROBLEMA
Per compiere l’analisi di un problema il risolutore deve:
La prima fase dell’analisi di un problema, ossia la definizione dell’obiettivo
da raggiungere, può essere realizzata attraverso processi di affinamento
sempre più dettagliati. Si tratta di scomporre un problema complesso in
sottoproblemi più semplici, utilizzando la tecnica del top-down
TECNICA DEL TOP-DOWN
STRATEGIE PER LA SOLUZIONE DI UN PROBLEMA
Le strategie per la soluzione di un problema sono dette euristiche,
in quanto non passano in rassegna tutte le possibilità, ma si affidano
ad ipotesi che restringono i percorsi selezionando quelli che potrebbero
con più probabilità portare alla soluzione.
La definizione di una FUNZIONE EURISTICA permette di attivare
differenti strategie:
STRATEGIA MEZZO-FINE che mira a ridurre la differenza tra lo stato iniziale e
quello finale del problema.
STRATEGIA MINI-MAX che mira non tanto a massimizzare i vantaggi ma a minimizzare le contromosse dell’avversario.
STRATEGIA di SCOMPOSIZIONE DEI PROBLEMI nel caso di problemi
complessi occorre partire dalla soluzione di tutti i sottoproblemi
Soluzione di un problema
Non esistono metodi precisi che possano essere indicati per risolvere un problema,
in quanto ogni problema va affrontato nella propria specificità e la sua soluzione
dipende dalle conoscenze che si possiedono intorno a quel problema ed alle tecniche
per risolverlo.
Compiuto il primo passo, quello dell’analisi del problema,
si può far scaturire da essa una descrizione discorsiva
del problema e delle varie fasi del processo risolutivo.
Per la descrizione discorsiva spesso si usano
i diagrammi a blocchi
ESEMPI DI PROBLEMI
PROBLEMA 1. Trovare le chiavi di casa.
Prerequisiti: occorre saperle riconoscere dalle altre chiavi e occorre delimitare il posto in cui
cercarle.
Soluzione bruta: passare scrupolosamente in rassegna ogni centimetro dello spazio in cui dovrebbero
trovarsi, finché non le troviamo.
Solitamente però ci lasciamo guidare da informazioni
o ipotesi sui posti in cui conviene cercarle,
anche se così facendo non c’è la garanzia di risolvere il problema.
Gli algoritmi
Il concetto intuitivo di ALGORITMO:
Una procedura meccanica, seguendo la quale si può calcolare,
dopo un numero finito di passi, la soluzione di un problema.
La sequenza di azioni che compone l’ALGORITMO è valida
per un insieme di dati iniziali ben definito, e può essere eseguita
da un opportuno ESECUTORE.
CARATTERISTICHE DELL’ALGORITMO
Le caratteristiche fondamentali di un algoritmo sono:
1- precisione: assenza di ambiguità di interpretazione da parte dell'esecutore;
2- dettagliatezza: composto da istruzioni fondamentali;
3- comprensibilità: scritto in un linguaggio comprensibile all'esecutore;
4- composto da un numero finito di istruzioni: deve terminare in un punto del procedimento;
5- completezza: per tutti i casi che si possono verificare durante l'esecuzione deve indicare la strada da seguire;
6- eseguibilità: composto da istruzioni che l'esecutore è effettivamente in grado di compiere;
7- determinatezza: ogni istruzione deve provocare l'attivazione di un azione precisa;
8- riproducibilità: ogni successiva esecuzione dello stesso algoritmo con gli stessi dati di input,
deve produrre gli stessi dati di output;
9- correttezza: esso deve pervenire alla soluzione del compito cui è preposto, senza difettare di alcun passo fondamentale;
10- efficenza: deve pervenire alla soluzione del problema nel modo più veloce possibile;
- concludendo:
- dal punto di vista del problema: l'algoritmo è la sequenza di istruzioni da dare all'esecutore per ricevere i dati iniziali elaborati in
risultati finali;
- dal punto di vista dell'esecutore: l'algoritmo è la sequenza delle operazioni da compiere per risolvere il problema assegnato.
Le strutture di controllo
Spesso è necessario poter intervenire sull’ordine d’esecuzione
delle istruzioni. Per far ciò in ogni algoritmo bisogna disporre
di strutture di controllo, quali...
• Sequenza
• Iterazione
• Condizione
RAPPRESENTAZIONE DEGLI
ALGORITMI
Automi Esecutori
Un AUTOMA è un sistema, o meccanismo, che esegue da sé un
tipo prestabilito di compiti.
Gli automi possono differire notevolmente in base al tipo di compito
che sono chiamati a svolgere.
Classici tipi di automa sono il termostato, l’ ascensore, la calcolatrice tascabile.
Più tipi di compiti esegue, più tipi di dati sa
interpretare, più è complesso l’automa.
Gli automi e l’informatica
Le attività cui si dà luogo per risolvere un problema possono essere:
•attività intelligenti di elaborazione;
•attività routinarie di esecuzione
Mentre il primo ruolo è riservato alla MENTE UMANA, il secondo
viene delegato a strumenti capaci di svolgere in modo rapido ed esatto
le operazioni logico-matematiche.
Questi strumenti sono macchine, dette AUTOMI, e possono essere
programmate per svolgere diverse mansioni e per modificare le
proprie azioni in relazione ai mutamenti ambientali.
Struttura dell’automa
Inteso non come macchina fisica (hardware), ma come macchina
astratta (software) che automatizza la procedura risolutiva di un
problema, l’automa corrisponde a:
•Un linguaggio formale in cui esprimere il problema e la sua soluzione;
•Un insieme di istruzioni algoritmiche generali, codificate nel linguaggio formale;
•Un insieme di procedure per eseguire le istruzioni in ciascun caso particolare.
Caratteri degli automi
Un automa è un dispositivo in grado di eseguire solo una sequenza
di azioni stabilite in precedenza; dotato di meccanismi per acquisire
elementi dall'esterno e produrre elementi verso l'esterno passando
attraverso stati diversi tra loro.
Dal punto di vista formale l'automa viene definito come
"un insieme di cinque elementi":
1- l'alfabeto dei simboli di input: insieme di simboli che l'automa è in grado di ricevere
dall'esterno riconoscendoli;
2- l'alfabeto dei simboli di output: insieme di simboli che l'automa comunica verso l'esterno;
3- l'insieme dei possibili stati che l'a. può assumere: le situazioni più importanti dell'automa
durante il suo funzionamento;
4- la funzione degli stati successivi: la relazione che indica lo stato assunto dall'automa,
quando trovandosi in un determinato stato accetta dall'esterno un determinato simbolo
di input;
5- la funzione delle uscite: la relazione che indica il simbolo che viene emesso verso l'esterno
in corrispondenza di un determinato stato e di un determinato simbolo di input.
Il funzionamento dell'automa consiste quindi nell'accettare
un simbolo dall'esterno ed emettere un simbolo in uscita
producendo un cambiamento di stato.
L’automa si dice a stati finiti quando l’insieme dei possibili stati
e dei simboli è un numero finito.
L’automa si dice deterministico in quanto lo stato successivo è sempre
determinato dallo stato precedente.
L’automa si dice discreto in quanto le variabili d’ingresso, di stato e
d’uscita non variano con continuità nel tempo.
Concretamente, per automatizzare la procedura risolutiva di un
problema, bisogna prima di tutto aver ricondotto la formulazione
del problema ad un MODELLO MATEMATICO
Poi bisogna definire un ALGORITMO che faccia al caso
Infine bisogna implementare questo ALGORITMO su un sistema
fisico che lo esegua
In tutte queste fasi vi possono essere errori umani (oltre che
malfunzionamenti hardware), di tipo filosofico, matematico o bug
di programmazione, a seconda della fase in cui si rivelano.
La macchina di Touring
La macchina di Touring: è un dispositivo di elaborazione ideale estremamente semplice che
risponde ad alcune regole basilari di funzionamento
(prende il nome dal suo ideatore A. M. Touring).
La macchina di Touring è dotata dei seguenti elementi:
una testina di lettura/scrittura: in grado di leggere e modificare valori contenuti
in una serie di celle (queste possono contenere dei simboli che appartengono ad un alfabeto
finito);
una unità di controllo: in grado di assumere degli stati distinti e definiti;
una memoria: in grado di conservare lo stato dell'unità di controllo tra una lettura e la
successiva;
Essa funziona in base a due semplici presupposti:
•ogni algoritmo può essere espresso da una macchina la quale si limita a manipolare simboli
senza preoccuparsi di ciò che significano;
•ogni modo di manipolare i simboli in base a regole di calcolo si riduce ad una opportuna
combinazione di azioni elementari
I computer sono automi
Invece che in un singolo nastro la memoria può essere organizzata su più registri;
esattamente così avviene in un computer ove è presente:
•UN’UNITA’ LOGICO-ARITMETICA che legge/scrive ed
esegue operazioni sui simboli in base alle istruzioni ricevute.
•UN REGISTRO di INPUT OUTPUT
•UN REGISTRO DI CODIFICA (o contatore di programma) che
associa dei numeri alle istruzioni da eseguire.
Una macchina di Touring che non modifica la sua memoria è
un AUTOMA A STATI FINITI
Un computer invece è dotato di memoria,
di più dispositivi di input/output,
di una unità centrale di elaborazione,
comprendente registri, unità logica aritmetica e
unità di controllo che eseguono ciclicamente le
istruzioni.
La durata di questi cicli è scandita dalla velocità
di clock del processore, misurata in megahertz.
Il processore può anche utilizzare elaborazione
parallela per velocizzare il ciclo.
I LINGUAGGI
SONO UTILIZZATI NELLA COMUNICAZIONE
QUOTIDIANA TRA GLI ESSERI UMANI; SONO
PRIVI DI UNA DEFINIZIONE RIGOROSA ED IN
CONTINUA EVOLUZIONE, SPESSO PRESENTANO AMBIGUITA’, MA HANNO UNA ENORME
POTENZA ESPRESSIVA.
CREATI DALL’UOMO PER SCOPI PRECISI, SECONDO
REGOLE CONVENZIONALI ESPLICITE CHE NON
AMMETTONO ECCEZIONI,LE LORO FRASI HANNO
SEMPRE UN SIGNIFICATO NON AMBIGUO E
PIENAMENTE CONTROLLABILE. HANNO UN POTERE
ESPRESSIVO LIMITATO.
È l’insieme delle regole che specificano
in quale modo le parole possono
combinarsi fra loro per generare frasi
e in quali modi le frasi semplici
possano combinarsi per generare
frasi complesse.
LA FORMULAZIONE RIGOROSA DI UN
PROBLEMA E LA DEFINIZIONE DI UN AUTOMA
PER RISOLVERLO HANNO BISOGNO DI UN
LINGUAGGIO PIU’ PRECISO DI QUELLO DITUTTI I GIORNI
È l’insieme delle regole che governano
l’interpretazione delle parole e delle
frasi, stabilendo quale ne sia il significato.
Semantica di un linguaggio formale
Mentre un linguaggio naturale ha già una semantica implicita,
anche se imprecisa, per un linguaggio formale occorre anzitutto
definire un a FUNZIONE DI INTERPRETAZIONE, che associ
un significato alle parole ed ai modi di combinarle in proposizioni.
A tale scopo occorre specificare un dominio U di interpretazione,
costituito da un insieme di entità (oggetti concreti o astratti) e dalle
loro mutue relazioni.
Fissato il dominio U, un’interpretazione è una procedura che associa:
• a ciascuna costante individuale un elemento di U
•a ogni simbolo di operazione una particolare azione che, eseguita su
elementi di U, produce di nuovo elementi di U
•a ogni simbolo di predicato una proprietà o relazione tra elementi di U
Principi logici di un linguaggio formale
Esiste un sistema di principi logici in base ai quali si “ragiona” sui
dati codificati nel linguaggio formale.
Questi principi si possono formulare come istruzioni del tipo:
…per inferire una conclusione a partire da certe premesse o condizioni
L’UTILIZZO DI UN LINGUAGGIO FORMALE CONSENTE DI
PASSARE DA UN ALGORITMO AL CORRISPONDENTE
PROGRAMMA
I linguaggi nella comunicazione
uomo/macchina
Tra algoritmo e programma vi è una fondamentale differenza
che consiste nella MODALITÀ IN CUI LE ISTRUZIONI SONO
CODIFICATE.
Una prima essenziale differenza è quella tra:
Linguaggio macchina
Linguaggi assemblativi
Linguaggi algoritmici
Linguaggi orientati ad
oggetti
Dall’algoritmo al programma
Il passaggio dall’algoritmo risolutore di un problema al corrispondente
programma avviene mediante la codifica dell’algoritmo attraverso un
LINGUAGGIO DI PROGRAMMAZIONE
Per consentire la comunicazione tra uomo e macchina ogni computer
ha bisogno di un particolare programma, scritto in un linguaggio appena
superiore a quello macchina: il SISTEMA OPERATIVO.
Esso gestisce le funzioni di base, come l’accesso alle risorse e la gestione
degli applicativi.
Tutti i linguaggi riproducono una stessa serie di operazioni e processi effettivamente
eseguibili dell’elaboratore elettronico, ossia utilizzano una stessa tipologia di istruzioni.
Istruzioni di dichiarazione, descrivono dati e variabili utilizzati dal programma,
definendone tipo e struttura. Quanto più è evoluto il linguaggio, tanto più sono
semplici le istruzioni per definire strutture complesse.
Istruzioni di assegnazione, consentono di assegnare ad una variabile un valore
dello stesso tipo della variabile.
Istruzioni di controllo sono istruzioni che richiedono salti di sequenza nell’esecuzione
del programma.
Rientrano in questa categoria le istruzioni di selezione e di iterazione e i salti
incondizionati.
Istruzioni di input/output, richiedono l’ingresso di informazione da una periferica
alla memoria centrale oppure l’uscita di una informazione dalla memoria centrale ad
una periferica.
I principali linguaggi di programmazione
TRADUTTORE DI FORMULE
INVENTATO NEI PRIMI ANNI 50
PER RISOLVERE PROBLEMI IN
AMBITO MATEMATICO
LINGUAGGIO ORIENTATO AD
APPLICAZIONI COMMERCIALI
E’ IL PRIMO LINGUAGGIO UTILIZZATO
PER LO SVILUPPO DEI PROGRAMMI
GESTIONALI AZIENDALI
LINGUAGGIO ALGORITMICO
ELABORATORE DI LISTE
RISALE AGLI ANNI 50 ED ERA
APPLICATO NELLA PRODUZIONE
DI PROGRAMMI TRADUTTORI
PROGRAMMA STRUTTURATO IN BLOCCHI,
DELIMITATI DA UN BEGIN E DA UN END
E’ L’ANTESIGNANO DELLA
PROGRAMMAZIONE STRUTTURATA
E DEL PASCAL
Sviluppati tra gli anni ‘60 e ‘70
sono tutti linguaggi per così dire
“didattici”, cioè relativamente
facili da apprendere e
funzionali allo sviluppo
di altri linguaggi più elevati e di
programmi.
Dal BASIC sono derivati i linguaggi VISUALI ed ORIENTATI AGLI
OGGETTI come il VISUAL BASIC, JAVA e ACTION SCRIPT,
con interfaccia grafica di facile utilizzo (pulsanti e finestre).
I MODERNI LINGUAGGI DI PROGRAMMAZIONE
Oggi sono ormai centinaia i linguaggi esistenti.
Per praticità vengono classificati in famiglie,
accomunati da uno stesso
MODELLO COMPUTAZIONALE
STILI E METODOLOGIA DI
PROGRAMMAZIONE
BASATO SU SEQUENZE DI
ISTRUZIONI
PREVEDE LA SCOMPOSIZIONE DI UN SISTEMA
COMPLESSO IN PIU’ MODULI, IN ANALOGIA
ALLA SCOMPOSIZIONE DI UN PROBLEMA IN
SOTTOPROBLEMI
BASATO SU FUNZIONI
RICORSIVE
AL CONTRARIO PREVEDE LA COSTRUZIONE DI UN
SISTEMA ATTRAVERSO L’AGGREGAZIONE DI PIU’
MODULI. QUESTO APPROCCIO PREVEDE IL
RIUTILIZZO DEL SOFTWARE GIA’ DISPONIBILE ED
E’ ALLA BASE DELLA
PROGRAMMAZIONE AD OGGETTI
LA PROGRAMMAZIONE AD OGGETTI
E’ una tecnica di costruzione del software tesa a favorirne al
massimo la GENERALITA’ e quindi la RIUTILIZZABILITA’
I moduli od oggetti, di cui è composto il programma sono
chiamate CLASSI.
Esse possono essere manipolate con operazioni comuni.
Possono essere aggregate in classi più complesse.
Possono essere organizzate gerarchicamente attraverso il
meccanismo dell’ereditarietà
TRE LINGUAGGI PER PROGRAMMARE NELLA SCUOLA
DI BASE
LEGGI
APRI
LEGGI