Il Concetto Intuitivo di Calcolatore
Elementi di Informatica e
Programmazione
Ingegneria Gestionale
Università degli Studi di Brescia
Docente: Prof. Alfonso Gerevini
Il Problemi e la loro Soluzione
(esempio)
Quanto vale la radice quadrata Y di un numero naturale X ? Problema Variabile di ingresso Variabile di uscita Istanza Quanto vale la radice quadrata intera Y di 49?
Dati= N (numeri naturali)
Risultati= R (numeri reali)
Soluzione dell’istanza= 7
Classe di domande omogenee
Elementi di Informatica e Programmazione U. Brescia 2 Docente: A.Gerevini
I Problemi e la loro Soluzione…
• Problema: classe di domande omogenee alle quali è possibile dare
risposta mediante una procedura uniforme
• Istanza del problema: ogni specifica domanda della classe
• Variabili di ingresso: termini variabili che caratterizzano la
formulazione di un problema
• Variabili di uscita: termini variabili che caratterizzano le soluzioni
attese di un problema
• Dati: valori che possono assumere le variabili d’ingresso
• Risultati: valori che possono assumere le variabili d’uscita
• Soluzione di un’istanza di un problema: risposta alla specifica
domanda che l’istanza rappresenta
3 Docente: A.Gerevini
Esercizio
Quanto vale la radice quadrata intera Z di un numero naturale
W (con approssimazione per difetto)
?
Problema Istanza = ? Dati= ? Risultati= ? Soluzione dell’istanza= ? 4 Docente: A.Gerevini Variabili ingresso e uscita = ?Risoluzione di un Problema
(
come
trovare soluzioni per le istanze)
Procedimento di risoluzione di un problema
1. Analisi del problema e individuazione di una
soluzione del problema (non è la soluzione
delle istanze!)
2. Descrizione della soluzione
3. Interpretazione della soluzione
4. Attuazione della soluzione da parte di un
esecutore
Fondamenti di Informatica A – Università di Brescia 5 Docente: A.Gerevini
Processo di Risoluzione
Soggetto 2b
oppure Soggetto 1b
ProblemaAnalisi Individuazione soluzione
Descrizione soluzione Formulazione descrizione Interpretazione descrizione Attuazione soluzione Descrizione interpretata Soluzione
Fondamenti di Informatica A – Università di Brescia 6 Docente: A.Gerevini
Un esempio di problema e di
soluzione
(esecutore umano)
•
Problema: come si fa una telefonata a X?
•
Soluzione:
1. Solleva il ricevitore 2. Componi il numero X 3. Attendi il segnale di libero
4. Se arriva il segnale di libero allora attendi che venga qualcuno a rispondere altrimenti riaggancia 5. Se dopo un po’ non arriva nessuno a rispondere
allora riaggancia altrimenti fai la tua conversazione
Fondamenti di Informatica A – Università di Brescia 10 Docente: A.Gerevini
Un altro esempio
•
Problema: qual è il numero più piccolo Y
(variabile di uscita) tra tre numeri
(variabili di ingresso) X1, X2, X3 ???
•
Soluzione: ???
Assumere di poter svolgere solo - confronti (<, >, =) tra numeri - istruzioni di tipo “Se … Allora …” - istruzioni del tipo “Y = …” e “STOP”
Fondamenti di Informatica A – Università di Brescia 10 Docente: A.Gerevini
Un altro esempio
•
Problema: qual è la radice quadrata intera
Y di un numero naturale X (approssimata
per difetto)?
•
Soluzione: ???
Assumere di poter svolgere anche operazioni aritmetiche
Per semplicità assumere X minore di 20 e maggiore di uno.
Fondamenti di Informatica A – Università di Brescia 10 Docente: A.Gerevini
Una possibile soluzione
1. Se 2*2 = X allora Y = 2 e STOP
2. Se 2*2 > X allora Y = 1 e STOP
3. Se 3*3 = X allora Y = 3 e STOP
4. Se 3*3 > X allora Y = 2 e STOP
5. Se 4*4 = X allora Y = 4 e STOP
6. Se 4*4 > X allora Y = 3 e STOP
7. Y = 4 e STOP
Una soluzione migliore quando X è
molto grande…
1. Per ogni valore della variabile di lavoro I
che va da 2 a X
2.
Se I*I > X allora Y=I-1 e STOP
3.
Se I*I = X allora Y=I e STOP
Ma mi serve una istruzione di tipo “iterativo”
per il passo 1
Soluzioni e Algoritmi…
• La soluzione è quindi espressa come
sequenza di operazioni la cui esecuzione
porta alla soluzione del problema Î
ALGORITMO RISOLUTIVO
ALGORITMO
DATI SOLUZIONE
11 Docente: A.Gerevini
Problema: Richiesta di un Libro
•
Come procedo?
1. Decido quale libro richiedere 2. Prelevo il libro
•
Il secondo passo va dettagliato, ovvero va
scomposto in sotto-problemi (
procedura
per raffinamenti successivi o top-down
)
Fondamenti di Informatica A – Università di Brescia 14 Docente: A.Gerevini
Il problema diventa…
1. Decido quale libro richiedere
2. Cerco la scheda del libro nello schedario
3. Mi segno numero dello scaffale e
posizione nello scaffale
4. Cerco lo scaffale
5. Cerco il libro nella sua posizione
all’interno dello scaffale
6. Prelevo il libro
Non è un problema elementare! Fondamenti di Informatica A – Università di Brescia 15 Docente: A.Gerevini
Cercare la scheda…
•
Scompongo in sotto-sotto-problemi:
1. Prendo la prima scheda
2. Il titolo, l’autore e la data corrispondono a quelli del libro che sto cercando? Se sì allora ho
individuato la scheda, altrimenti passo alla scheda successiva e ripeto il controllo
3. Se le schede sono esaurite, allora il libro non esiste
•
Esistono metodi più efficienti per risolvere
lo stesso problema… come fareste voi?
Fondamenti di Informatica A – Università di Brescia 16 Docente: A.Gerevini
Un metodo più efficiente…
(se lo schedario è ordinato!)
1. Esamino la scheda centrale dello schedario
2. Se la scheda corrisponde al libro cercato allora termino la ricerca
3. Altrimenti cerco (con lo stesso metodo) nella metà inferiore o superiore dello schedario, a seconda che il libro cercato preceda o segua il libro indicato sulla scheda
NB: il passo 2 deve “accorgersi” anche se il libro non esiste, diventa:
“se la scheda corrisponde al libro cercato oppure se la parte di schedario da esaminare è vuota allora termino la ricerca”
Fondamenti di Informatica A – Università di Brescia 17 Docente: A.Gerevini
Soggetto Esecutore
• Il soggetto esecutore (soggetto 2) deve essere in grado di
interpretarela descrizione della soluzione
• Deve inoltre essere in grado di eseguirele azioni presenti nella descrizione interpretata
• Il calcolatoreè un esecutore di soluzioniidentificate e descritte da esseri umani (in genere un team di progettisti, programmatori e utenti)
• Caratteristiche di un calcolatore: linguaggioche è in grado di interpretare e istruzioniche è in grado di eseguire • Quando/perchè usare un calcolatore come esecutore?
Fondamenti di Informatica A – Università di Brescia 19 Docente: A.Gerevini
Il Calcolatore come Esecutore
(una prima definizione)
CALCOLATORE Soluzione di un problema (programma-descrizione di un algoritmo -) Dati iniziali (assegnati a variabili di input) Risultatidell’esecuzione in corrispondenza dei dati iniziali
(assegnati a variabili di output)
Fondamenti di Informatica A – Università di Brescia 20 Docente: A.Gerevini
Caratteristiche di un Esecutore
1.
Il
linguaggio
che è in grado di interpretare
Un linguaggio si fonda su un certo numero di simboli di un certo alfabeto A. Con i simboli si formano le parole; tra le parole si inseriscono connettivi a formare frasi
2.
L’insieme delle
azioni
che è in grado di compiere
3.
L’insieme delle
regole
che a ogni frase del
linguaggio associano le relative azioni da
compiere
21 Docente: A.Gerevini
Sintassi e Semantica
• Sintassi di un linguaggio:
insieme delle regole che specificano la scrittura di istruzioni formalmente corrette (ben formate),
indipendentemente dal loro significato
• Semantica di un linguaggio:
insieme delle regole che specificano il significato di ciascuna istruzione, cioè l’azione che viene compiuta quando l’istruzione viene eseguita
La struttura
Il significato
23 Docente: A.Gerevini
Algoritmi e Programmi
• Algoritmo: una
sequenza di azioni (istruzioni)
che, operando sui dati iniziali, consentono di
ottenere la soluzione dell’istanza del problema in
esame
• Ogni azione della sequenza è detta passo (step)
dell’algoritmo
• Per essere eseguito l’algoritmo deve essere
descritto con il linguaggio del suo esecutore
Fondamenti di Informatica A – Università di Brescia 24 Docente: A.Gerevini
Computazione: definizioni
• Computazione: esecuzione di un algoritmo in corrispondenza di certi dati iniziali
• Passo di computazione: ogni singolo passo elementare che l’esecutore compie durante una computazione
• Sequenza computazione: sequenza di passi elementari che l’esecutore compie in corrispondenza di certi dati iniziali durante l’esecuzione di un algoritmo
Algoritmo = concetto statico Computazione = concetto dinamico
Fondamenti di Informatica A – Università di Brescia 25 Docente: A.Gerevini
Algoritmi, Programmi e
Calcolatore
• Programma
: descrizione formale di un algoritmo
attraverso un linguaggio di programmazione
• Un programma è una
sequenza di istruzioni
scritte in un opportuno linguaggio comprensibile
al calcolatore
• Il
calcolatore
è un
esecutore di programmi
• Il
compito di un esperto informatico
consiste nel
produrre algoritmi e codificarli in programmi
Fondamenti di Informatica A – Università di Brescia 27 Docente: A.Gerevini
Il Calcolatore come Esecutore di
Istruzioni
• L’insieme di istruzioni più complesso può essere
riscritto in un
linguaggio elementare
basato su un
alfabeto binario
(composto dei soli simboli 0 e 1)
ed un insieme di
poche distinte operazioni
per la
manipolazione del sequenze di 0 e 1
• Il
calcolatore digitale
è un dispositivo che è in
grado di interpretare ed eseguire le istruzioni
scritte in questo linguaggio elementare
Fondamenti di Informatica A – Università di Brescia 29 Docente: A.Gerevini
Proprietà di un Algoritmo
• Finitezza: un algoritmo deve essere costituito da un numero finito di istruzioni
• Univocità: ogni istruzione deve essere univocamente interpretabile ed eseguibile
• Effettività: deve esistere un esecutore in grado di eseguire ogni istruzione dell’algoritmo in un tempo finito
• Determinismo: per qualunque dato di ingresso, a ogni passo della computazione, esiste al più un passo successivo. Ovvero:
assegnato un dato di ingresso, esiste una e una sola
sequenza di computazione possibile dell’algoritmo
Fondamenti di Informatica A – Università di Brescia 26 Docente: A.Gerevini
Proprietà di un Algoritmo (cont.)
• Funzione rappresentata: un algoritmo associa ai valori per le variabili di input valori per le variabili di uscita. • Correttezza: calcola correttamente la funzione
rappresentata (associata al problema da risolvere)
• Efficienza: l’algoritmo perviene alla soluzione del compito impiegando una certa quantità di risorse fisiche
– Risorse fisiche: tempo, memoria, ….
• Terminazione: l’esecuzione di un algoritmo deve terminare in un numero finito di passi di computazione