Dal problema al programma
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
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
Problemi e algoritmi
Tipi di problemi
Problemi di decisione
Problemi di ricerca
Problemi di ottimizzazione
Strategie per la risoluzione dei problemi
Problema
Interpretazione
ModelloProcedimento risolutivo (algoritmo)
Esecuzione
Verifica dei risultati
Strategie per la risoluzione dei problemi
TOP DOWN
Suddivide il problema in tanti piccoli sottoproblemi
Utilizza uno schema grafico a segmenti
GRAFICO
Interpretazione
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 ).
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
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
Esempio di diagramma a blocchi
N
S =
A
S= S+A
N=N-1
N= S
FINE
SINO
inizioSomma di una sequenza di numeri
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
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
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
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)
Linguaggi
Il linguaggio è un sistema codificato di segni che consente la comunicazione, intesa come scambio di informazioni
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
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
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
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.
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
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)
Linguaggi di programmazione
Problema
Algoritmo
Programma sorgente
Programma traduttore
Programma oggetto
Elaborazione
Risultati
Dalla formulazione del problema
alla sua soluzione
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
Linguaggi di programmazione
Principali linguaggi
Fortran
Algol
Cobol
Basic
Logo
Lisp
PL1
Pascal C /C++Java
PHP
Cosa e' la programmazione?
La programmazione e' l'attivita' di sviluppare programmi per un calcolatore.Lo scopo della scrittura di un programma e' la risoluzione di un problema.Per risolvere un problema bisogna:
• Formulare il problema (specifica dei requisiti) in modo più o meno formale• Capire il problema e scomporlo in parti gestibili (analisi del problema)• Progettare una soluzione (algoritmo)• Implementare la soluzione (scrittura del codice)• Testare la soluzione e correggere eventuali errori (verifica del programma,
testing e debugging)• Tenere sempre aggiornato il programma (manutenzione)
L’ALGORITMOI DATI
LE ISTRUZIONI
LE STRUTTURE FONDAMENTALI
Informalmente, un algoritmo è una procedura ben definita che serve per risolvere un dato problema
E’ una sequenza di passi che prende dei valori come input e produce altri valori come output
Più precisamente, un algoritmo è un procedimento di calcolo , descrivibile con un numero finito di operazioni che conducono al risultato
30
IL PROGRAMMA
In ambito informatico, un algoritmo viene descritto tramite un programma, ossia un testo scritto in uno specifico linguaggio detto linguaggio di programmazione per essere eseguito da calcolatori elettronici
Gli algoritmi sono astratti e per controllarne il funzionamento devono essere realizzati con un qualche strumento concreto
• Ad esempio la descrizione di una ricetta di cucina è un algoritmo ma la preparazione della pietanza è la realizzazione della ricetta. E’ solo allora che si vede se la ricetta “funziona”
• Altro esempio può essere rappresentato da una qualsiasi formula matematica, che rappresenta, nel linguaggio matematico un procedimento. Ma la bontà di tale regola può essere verificata solo con dei veri e propri calcoli, sostituendo alle variabili dei veri numeri.
32
L’algoritmo e il programma
Invece:
Le proprietà degli algoritmi sono talmente fondamentali, generali e robuste, da essere indipendenti dalle caratteristiche di specifici linguaggi di programmazione o di particolari calcolatori elettronici
Quindi:
PER RISOLVERE UN PROBLEMA E’ ASSOLUTAMENTE NECESSARIO TROVARE UN PROCEDIMENTO RISOLUTIVO DESCRIVIBILE CON UN ALGORITMO, E SOLO DOPO SI PUO’ PASSARE A SCRIVERE IL PROGRAMMA
Ogni linguaggio di programmazione ha una sua sintassi ed una propria rappresentazioni dei dati, e utilizza le proprie operazioni di manipolazione dei dati
34
PROGRAMMA = ISTRUZIONI + DATIUn programma può essere visto come un manipolatore di dati:
a fronte di dati in ingresso che descrivono il problema producono dati in uscita come risultato del problema
INPUT (dati)
OUTPUT(dati)PROCESSO
(istruzioni)
Le operazioni sui dati sono le istruzioni.I dati sono gli oggetti su cui vengono eseguite le istruzioni.
Tutti i linguaggi di programmazione prevedono un insieme di dati e istruzioni
che il programmatore può utilizzare nella realizzazione dei propri programmi.
35
I DATII dati possono essere distinti in base a :
• Utilizzo all’interno del processo
INPUT
OUTPUT
LAVORO
• Formato NUMERICO
ALFANUMERICO
• Valore assunto durante il processo
INTERO
DECIMALE
VARIABILE
COSTANTE
Questi aspetti dei dati devono essere definiti già nell’algoritmo, in modo da poterli poi “tradurre” con la sintassi propria del linguaggio di programmazione
36
LE ISTRUZIONIAnche le istruzioni devono essere scritte rispettando la sintassi propria del linguaggio di programmazione
Ogni linguaggio di programmazione ha le proprie istruzioni, ma tutti i linguaggi devono possedere alcune istruzioni per compiere le azioni fondamentali
Acquisire i dati su cui attivare il processo di elaborazione input
• Comunicare all’esterno i risultati ottenuti output
Azioni di tipo aritmetico assegnazione - assegnare un valore ad una variabile - utilizzare gli operatori aritmetici (+, -, /, *, %)
Azioni di tipo logico confronto - Utilizzare gli operatori di relazione( =, <, >, <=, >=, <>) per confrontare il contenuto di due variabili - Utilizzare gli operatori logici (and, or, not)
Top Related