Dal problema al programma
Unità di apprendimentoTratte da moduli presentati dalle prof.sse Piera De Maio e Maria Cantone – PNFI TIC
Scopo
Conoscere alcuni concetti fondamentali dell’informatica: algoritmo, automa a programma, 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
Indice
UA.1 Problemi e algoritmi1.1 introduzione intuitiva del concetto di problema1.2 cenni sulle strategie per la risoluzione dei problemi
– soluzione di un problema: fase di analisi e algoritmi1.2a Diagrammi a blocchi1.2b Linguaggio di progettoEsempi ed esercizi
UA.2 Automi esecutori2.1 Automi esecutori 2.2 Caratteristiche di un automa 2.2a Concetto di sistema2.2b Concetto di modello2.3 Automi e classi di problemiEsercitazioni
UA.3 Linguaggi3.1 Sintassi e semantica dei linguaggi3.1a Linguaggi nella comunicazione uomo-macchina3.2 Linguaggi e automi3.3 Linguaggi di programmazione con esempio
1.1 Introduzione intuitiva al concetto di problema
Il problema è una situazione che pone delle domande alle quali si devono dare delle risposte. Risolvere il problema vuol dire uscire dalla situazione
Un problema è incertezza cioè mancanza di informazioni
Problema è quando non sappiamo affrontare “normalmente” la vita; di solito il nostro comportamento è meccanico, le nostre azioni sono frutto di abitudine ma nasce il problema quando un fatto imprevisto ci causa dubbio, disagio perché ci impone una scelta con esigenza di riflettere cioè ragionare analizzando dettagliatamente il pro e il contro delle decisioni al fine di sciogliere quel dubbio (analysis = “scioglimento, risoluzione”).
Problemi e algoritmiUn problema consta dei seguenti elementi
•Dati iniziali: ossia ciò che è noto (misura reale) e che indichiamo col termine input
•Risultati o dati finali: gli elementi incogniti che si devono determinare e che indicheremo con output
•Condizioni: le limitazioni o vincoli cui devono soggiacere i risultati
Il “che cosa” e il “come”:
• il problema descrive “che cosa” si deve calcolare
• l’algoritmo descrive “come” effettuare un calcolo
Problemi e algoritmi
Tipi di problemi
Problemi di decisione
Problemi di ricerca
Problemi di ottimizzazione
1.2 Strategie per la risoluzione dei problemi
Problema
Interpretazione
ModelloProcedimento risolutivo
(algoritmo)
Esecuzione
Verifica dei risultati
1.2 Strategie per la risoluzione dei problemi
TOP DOWN
Suddivide il problema in tanti sotto-problemi fino ad operazioni elementari
Utilizza uno schema grafico a segmenti
GRAFICO
Interpretazione
Esempio di Problema
Individuare il percorso più breve per andare a scuola (scomponendo in sotto-problemi)
1.2 Strategie per la risoluzione dei problemi
Algoritmo
Insieme dei comandi che definiscono una sequenza finita di operazioni da eseguire mediante le quali si risolve il problema
Deve essere :
finito (numero limitato di passi: i comandi sono in numero finito
e vengono eseguiti un numero finito di volte);
definito (ogni istruzione deve consentire un’interpretazione
univoca – non ambigua e precisa);
eseguibile (la sua esecuzione deve essere possibile con gli
strumenti a disposizione);
deterministico (ad ogni passo deve essere definita una ed una
sola operazione successiva).
Passo
Azione elementare che deve essere intrapresa per procedere nell’esecuzione dell’algoritmo.Questo concetto richiede di stabilire l’insieme delle azioni che l’esecutore dell’algoritmo (persona o la macchina) è in grado di svolgere.In altre parole, chi definisce un algoritmo deve accordarsi con chi lo dovrà eseguire circa le istruzioni da utilizzare per descrivere l’algoritmo stesso.
Supponiamo ad esempio di dover descrivere la ricetta per la preparazione di una frittata: l’istruzione “mettere quattro uova in una padella “ può essere utilizzata solo se si è sicuri che la persona che eseguirà la ricetta è abbastanza esperta da capire che nella padella deve essere versato il contenuto delle uova che devono quindi venire rotte in modo da eliminare i gusci.
Esempi di algoritmo
Preparazione di una torta
Ricetta: descrizione precisa di un procedimento “meccanico”
Esempi di algoritmo
Prelevamento col Bancomat
Una dettagliata sequenza di azioni/operazioni che devono essere eseguite per risolvere una classe di problemi. Il nome deriva dal matematico Uzbeko-Iraniano Al-Khawarizmi Al-Khawarizmi ي vissuto) الخوارزمintorno all'anno 800)
Esempio di algoritmo (continua)
L'algoritmo "va' dal salotto alla cucina" si compone in realtà delle seguenti istruzioni: – esci dal salotto – curva a sinistra – prosegui per il corridoio fino all'ultima porta sulla sinistra – attraversa la porta a sinistra
L'algoritmo "attraversa la porta a sinistra" si compone di: – controlla se la porta è aperta – nel caso che la porta sia aperta salta il passo seguente – apri la porta (cioè protendi braccio, afferra maniglia ….)– avanza di un metro
Esempio di algoritmo
Un modo dettagliato di rappresentare l'algoritmo "attraversa la porta a sinistra" specificando le sequenze sotto-algoritmiche è allora il seguente: – controlla se la porta è aperta – nel caso che la porta sia aperta salta il passo seguente – apri la porta
─ protendi il braccio ─ afferra la maniglia ─ rotea la mano di 30 gradi in direzione antioraria ─ applica una pressione alla maniglia diretta di fronte a te ─ ...
– avanza di un metro
Esercizi
Spedire una lettera all’amico Giorgio che abita a Roma:1 - Ordinare le seguenti operazioni:
- metto il foglio nella busta- attacco il francobollo- prendo una busta- esco di casa- imbuco la lettera nella cassetta- aggiungo il c.a.p. di Roma- prendo il francobollo- vado all’ufficio postale- scrivo sulla busta l’indirizzo di Giorgio- chiudo la busta- cerco il numero del c.a.p di Roma- cerco l’indirizzo di Giorgio nella rubrica.
2 - Specificarne le sequenze sotto-algoritmiche
Esercizi
Considerando i seguenti concetti come il percorso che va dal problema al programma, collegare con parole o frasi significative ogni parola alla successiva e a quanti più concetti è possibile:
PROBLEMA, ALGORITMO, DIAGRAMMA A BLOCCHI, LIGUAGGIO DI PROGETTO, AUTOMA, SISTEMA, MODELLO, LINGUAGGI DI PROGRAMMAZIONE, PROGRAMMA
1.2 Strategie per risoluzione dei problemi
Rappresentazioni grafiche e formalizzate di un algoritmo
Diagramma a blocchi
o flow-chart
La descrizione delle fasi esecutive del problema può avvenire mediante la formalizzazione dei passi elementari da effettuare che può essere realizzata con:
Pseudocodifica
e/o
1.2a Diagrammi a blocchi
Ha il pregio di evidenziare visivamente l’avanzamento in sequenza e le varie strutture che compongono l’algoritmo, presenta istruzioni di input e/o output, calcolo e/o di elaborazione, condizioni ed individua un inizio ed una fine.
INPUT
ISTRUZIONI
CONDIZIONI
fine
Diagramma a blocchi o flow-chart
1.2a Esempio di diagramma a blocchi
N
S =
A
S= S+A
N=N-1
N > S
fine
NO SI
inizioSomma S di una sequenza di N numeri di valore A variabile
1.2b Linguaggio di progettoLinguaggio di progetto o pseudo-codifica
È un linguaggio formale (linguaggio di progetto), con regole prive di ambiguità ed eccezioni che esprimono i vari tipi di istruzioni. Viene definito pseudo-codifica o notazione lineare strutturata.
Generalmente utilizzato nella soluzione informatizzata di problemi più complessi.
inizio
leggi N
S
fai
leggi A
S S+A
N N-1
mentre ( N > )
stampa S
fine
In modo più efficiente, al posto di inizio/fine si possono usare le parentesi graffe
Algoritmo: media aritmetica
Calcolo della media aritmetica di una sequenza di valori numericiDiagramma a blocchi o flow-chart
Algoritmo: media aritmetica
inizio
N S fai
leggi V
S S + V
N N +1
mentre (V > )
N N-1
M
scrivi M
fine
Linguaggio di progetto o pseudo-codifica
Tecnica descrittivadi più semplice
lettura/comprensione
2.1 Automi esecutori
La risoluzione di un problema è un processo di manipolazione di informazioni per generare nuove informazioni .
Per risolvere un problema ci sono due tipi di attività :
“intelligenti”di elaborazione “routinarie” di esecuzione
2.2 Caratteristiche di un automa
Sono macchine che compiono attività complesse in cui sono riconoscibili elementi propri delle attività superiori del comportamento umano. Possono essere programmate per svolgere diverse mansioni e per modificare le proprie azioni in relazione ai mutamenti ambientali. (Es: lavatrici, sistemi di controlli ascensori, bancomat…computer)
Un automa è un sistema :
Dinamico Passa da uno stato (condizione di funzionamento) all’altro
secondo gli input che riceve
Invariante Se le condizioni iniziali sono le stesse il comportamento
del sistema è invariato
Discreto Le variabili (d’ingresso, di stato e d’uscita) possono
assumere solo valori discreti
Automi
2.2a Concetto di sistemaSi dice Si dice sistemasistema un insieme di elementi che interagiscono tra loro in modo da un insieme di elementi che interagiscono tra loro in modo da formare una nuova entità (con un determinato scopo o funzionalità) che, al formare una nuova entità (con un determinato scopo o funzionalità) che, al verificarsi di un dato evento (azione) proveniente dall’ambiente esterno, verificarsi di un dato evento (azione) proveniente dall’ambiente esterno, produce una risposta definitaproduce una risposta definita.
Un sistema non è un oggetto ma la definizione di un ambito (limiti di analisi): si sceglie cosa
nascondere (come in una scatola nera) e cosa evidenziare, interessati all’uso.
Rappresentazione sistemica (paradigma ingresso-uscita): descrizione a blocchi funzionali cioè una rappresentazione grafica che distingue tra variabili in ingresso (grandezze su cui possiamo agire per introdurre modifiche) e in uscita (risposte cioè grandezze che risultano influenzate e che possiamo osservare per studiare sperimentalmente l’andamento) individuando gli eventuali parametri costanti :
Per una classificazione rigorosa dei sistemi: http://professoressa.altervista.org/Dispense_III/Classificazione%20sistemi.pdf
2.2b Concetto di modello
Modello
E’ uno schema teorico (una descrizione semplificata) elaborato per rappresentare elementi fondamentali di fenomeni o enti
Modelli descrittivi (riproducono in modo semplice la realtà, senza presupporre l’uso
che ne verrà fatto)
Modelli predittivi (danno gli elementi di una situazione per prevederne l’evoluzione)
Modelli prescrittivi (impongono un particolare comportamento in previsione dell’obiettivo
da raggiungere)
Modelli simbolici o matematici (danno una rappresentazione astratta mediante un
insieme di equazioni che legano le grandezze)
Modelli iconici (danno una rappresentazione fedele della realtà in scala ridotta)
Modello per trascurare gli aspetti superflui alla soluzione di problemi
Per una motivazione all’uso della modellizzazione ed una classificazione rigorosa dei modelli: http://professoressa.altervista.org/Dispense_III/Apprendimento_Modelli.pdf
2.3 Automi e classi di problemi
Un sistema automatico o automa è un sistema nel quale la componente umana è completamente eliminata nell’ambito dei processi, che sono ben determinati e prevedibili:
lavatrice, lavastoviglie, computer (automa a programma)
Un sistema umano, al contrario, presenta un carattere probabilistico, poiché l’uomo può assolvere a funzioni impreviste, utilizzando il ragionamento, la creatività e l’intuito.
Problemi e algoritmi
ESERCITAZIONI
Testo dei problemi on-line http://utenti.multimania.it/pbiasotti/Dispense_III/Esercizi_da_problema_ad_algoritmo.pdf Introduzione alla logica delle proposizioni: quesiti on-line http://professoressa.altervista.org/Dispense_III/Cavalieri_furfanti.pdf
Un bambino ha costruito una torre di tre blocchi colorati così disposti dall’alto in basso: ROSSO-GIALLO-VERDE. IL bambino vuole capovolgerla in modo da avere VERDE-GIALLO-ROSSO. Può spostare solo un blocchetto alla volta. Individuare il numero minimo di stati per i quali si arriva alla configurazione desiderata
Problemi e algoritmi
Soluzione all’ ESERCITAZIONE (spazio degli stati)Un bambino ha costruito sul tavolo una torre di tre blocchi colorati, così disposti dall’alto in basso: ROSSO-GIALLO-VERDE. Vuole capovolgerla, in modo da avere VERDE-GIALLO-ROSSO e si serve di una sola mano per spostare non più di un blocchetto alla volta sul tavolo.
Il percorso ottenuto componendo in successione le 4 transizioni elementari (nella figura) conduce alla soluzione: una volta arrivato alla configurazione in cui tutti i blocchi poggiano sul tavolo, può completare in sequenza la torre seguendo diverse alternative (ne è illustrata una delle possibili)
Per approfondire: La Torre di Hanoi
3 Linguaggi
Il linguaggio è un sistema codificato di segni che consente la comunicazione, intesa come scambio di informazioni
3.1 Sintassi e semantica dei linguaggi
Essere acquisita direttamente tramite rilevamento di un evento reale attraverso percezione sensoriale.
Un’informazione può :
Essere trasmessa (messaggio) intenzionalmente da un emittente ad un ricevente per mezzo di un canale
La comunicazione
Il messaggio presuppone l’utilizzo di un codice (sistema di regole) e di un linguaggio (sistema di segni) che devono essere conosciuti sia dalla sorgente emittente che dal destinatario, altrimenti la comunicazione non ha effetto ?
??
?
sorgentedestinatario
3.1 Sintassi e semantica dei linguaggi
La funzione del linguaggio è quella di sostituire ad oggetti o concetti dei segni/simboli per trasmettere un messaggio.
Il segno è l’associazione di qualcosa di materiale e sensibile (immagine, suono…) che chiamiamo significante con qualcosa di puramente concettuale che chiamiamo significato
Il codice ci consente l’interpretazione dei segni
Segno = significante + significato
gatto Il gruppo dei suoni o di lettere g/a/t/t/o
Nella storia si sono usate diverse forme di comunicazione
3.1 Sintassi e semantica dei linguaggi
Alfabeto insieme finito e non vuoto di simboli convenzionali espressi con segni tipografici detti caratteri Ortografia insieme finito e non vuoto di regole per la scrittura dei suoniSintassi insieme finito e non vuoto delle regole (di posizione) mediante le quali si formano le stringhe o le frasi di un linguaggioSemantica insieme finito e non vuoto di significati da attribuire alle stringheMorfologia insieme finito e non vuoto di tutte le regole che servono per generare le forme di un linguaggio
ELEMENTI DI UN LINGUAGGIO
3.1.a Linguaggi nella comunicazione uomo - macchina
L’uomo per comunicare all’ automa le strategie risolutive di un problema ha bisogno di un linguaggio formale che gli consenta di passare dall’ algoritmo al programma, cioè ad una sequenza di istruzioni in linguaggio comprensibile al calcolatore mediante le quali si può risolvere il problema.
3.2 Linguaggi e automi
Linguaggi non evolutiLinguaggio macchina, linguaggio assemblativo (Assembler).
Vicino alla logica della macchina
Linguaggi evoluti Linguaggi non orientati alla macchina, ma alla soluzione dei problemi.
Vicino alla logica dell’uomo
3.2 Linguaggi e automi
I principali software
Sistema operativo Office Automation
•Word processor
•Foglio di calcolo
•Sistemi di gestione base dati
•Programmi per la realizzazione di
presentazioni multimediali
•Programmi di grafica computerizzata
•Editor di suoni
•Editor di pagine web
Software di base, controlla tutte le risorse del computer, necessita di un linguaggio più vicino al linguaggio macchina
(Assembler)
Programmigeneral purpose
3.3 Linguaggi di programmazione
Problema
Algoritmo
Programma sorgente
Programma traduttore
Programma oggetto
Elaborazione
Risultati
Dalla formulazione del problema
alla sua soluzione
3.3 Linguaggi di programmazione
Programma sorgenteL’algoritmo risolutivo viene trasformato in un programma attraverso un linguaggio di programmazione che può contenere:
Istruzioni di dichiarazione Istruzioni di
assegnazione
Istruzioni di controllo
Istruzioni di input e output
Descrivono dati e variabili utilizzati dal programma, definendone tipo e struttura
Consentono di assegnare alla variabile un valore dello stesso tipo della variabile
Sono istruzioni che richiedono salti di sequenza nell’esecuzione del programma
Richiedono l’ingresso o l’uscita di un’informazione da una periferica alla memoria centrale e viceversa
3.3 Linguaggi di programmazione
Principali linguaggi
Fortran
Algol
Cobol
Basic
Logo
Lisp
PL1
Pascal C /C++ Java
PHP
Esempio: da problema a programma
Calcolo dell’interesse composto generalizzato: dall'analisi all'implementazione, con richiami a concetti pregressi on-line http://professoressa.altervista.org/Dispense_I/Analisi_Modellizzazione_Es_Interessi.pdf (linguaggio C/C++)
Giocando con la torre di Hanoi on-line http://professoressa.altervista.org/Dispense_III/La%20torre%20di%20Hanoi_3D.pdf (linguaggio C/C++ o JavaScript)
Top Related