Dal problema al programma

Modulo 8

Piano Nazionale di Formazione degli Insegnanti sulle Tecnologie

dell’informazione e della Comunicazione

A cura della prof.ssa Piera De Maio

Scopo del modulo

Conoscere alcuni concetti fondamentali dell’informatica:algoritmo, automa, linguaggio formaleEssere 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

Indice8.1 Problemi e algoritmi8.1.1 introduzione intuitiva del concetto di problema8.1.2 cenni sulle strategie per la risoluzione dei problemi8.1.3 soluzione di un problema 8.1.4 gli algoritmi8.1.4a Diagrammi a blocchi8.1.4b Linguaggio di progetto

8.2 Automi esecutori8.2. Automi esecutori8.2.1 Caratteriatiche di un automa 8.2.1bConcetto di modello8.2.1cConcetto di automa8.2.1b 8.2.2 Automi e classi di problemiEsercitazioni

8.3 Linguaggi8.3.1 Sintassi e semantica dei linguaggi8.3.1a Linguaggi nella comunicazione uomo-macchina8.2.2 Linguaggi e automi8.3.3 Linguaggi di programmazione

8.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

8.1 Problemi e algoritmiUn problema consta dei seguenti elementi

•Dati: ossia ciò che è noto e che indichiamo col termine input

•Risultati: gli elementi incogniti che si devono determinare e che indicheremo con output

•Condizioni: le limitazioni cui devono soggiacere i risultati

8 .1 Problemi e algoritmi

Tipi di problemi

Problemi di decisione

Problemi di ricerca

Problemi di ottimizzazione

8.1.2 Strategie per la risoluzione dei problemi

Problema

Interpretazione

ModelloProcedimento risolutivo (algoritmo)

Esecuzione

Verifica dei risultati

8.1.2b Concetto di modello

Modello

E’ uno schema teorico 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’obiet

tivo da raggiungere)

Modelli simbolici o matematici (danno una rappresentazione astratta mediante un

insieme di equazioni che legano le grandezze)

Modelli analogici ( danno una rappresentazione fedele della realtà in scala ridotta )

8.1.2 Strategie per la risoluzione dei problemi

TOP DOWN

Suddivide il problema in tanti piccoli sottoproblemi

Utilizza uno schema grafico a segmenti

GRAFICO

Interpretazione

8.1.2 Strategie per la risoluzione dei problemi

AlgoritmoInsieme delle istruzioni che definiscono una sequenza di operazioni mediante le quali si risolve il problema

Deve essere : finito (numero limitato di passi );

definito (ogni istruzione deve consentire un’interpretazione

univoca);

eseguibile ( la sua esecuzione deve essere eseguibile con gli

strumenti a disposizione);

deterministico ( ad ogni passo deve essere definita una

operazione successiva ).

8.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

8.1.4a 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, calcolo e/o di elaborazione, condizioni e output.

INPUT

ISTRUZIONI

CONDIZIONI

OUTPUT

Diagramma a blocchi o flow-chart

8.1.4a Esempio di diagramma a blocchi

N

S =

A

S= S+A

N=N-1

N= S

FINE

SINO

inizioSomma di una sequenza di numeri

8.1.4b Linguaggio di progettoLinguaggio di progetto o pseudocodifica

E un linguaggio formale, ( linguaggio di progetto) con regole prive di ambiguità ed eccezioni che esprimono i vari tipi di istruzioni. Viene definito pseudocodifica o notazione lineare strutturata.

Generalmente utilizzato dai programmatori di elaboratori.

begin ESEMPIO IN PASCAL

Input N

S

repeat

input A

S S+A

N N-1

until N=

output S

end

8.2 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

8.2.1 Caratteristiche di un automa

Sono macchina 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 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

8.2.1 Il concetto di automaGrafi e tabelle di transizione

Servono a rappresentare il comportamento logico-funzionale di un automa

Es. tabella e grafo di un automa a stati finiti di un ascensore

S\i T 1 2

pt Pt/ fermo 1p/ su 2p/ su

1p Pt/ giù 1p/ fermo 2p/ su

2p Pt/ giù 1p/ giù 2p/ fermo

PT

2P

1P

1/fermo

2/su

1/ giù

T/giù

1/ su

2/ fermo

2/su

T / fermo

8.2.2 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

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.Cercare una chiave in un mazzo di 100 chiavi con il minor numero di prove (diagramma di flusso)

8.3 Linguaggi

Il linguaggio è un sistema codificato di segni che consente la comunicazione, intesa come scambio di informazioni

8.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 che devono essere conosciuti sia dal emittente che dal destinatario, altrimenti la comunicazione non ha effetto

?

??

?

emittentedestinatario

8.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

8.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 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 tuttele regole che servono per generare le forme di un linguaggio

ELEMENTI DI UN LINGUAGGIO

8.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 mediante le quali si può risolvere il problema.

8.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

8.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)

8.3.3 Linguaggi di programmazione

Problema

Algoritmo

Programma sorgente

Programma traduttore

Programma oggetto

Elaborazione

Risultati

Dalla formulazione del problema

alla sua soluzione

8.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

8.3.3 Linguaggi di programmazione

Principali linguaggi

Fortran

Algol

Cobol

Basic

Logo

Lisp

PL1

Pascal C /C++Java

PHP