Il Concetto Intuitivo di Calcolatore

(1)

Il Concetto Intuitivo di Calcolatore

Fondamenti di Informatica A

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) Soluzione

Classe di domande omogenee

(2)

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

Fondamenti di Informatica A – Università di Brescia 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 = ?

Variabili ingresso e uscita = ?

(3)

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

Docente: A.Gerevini

Processo di Risoluzione

Soggetto 2

Soggetto 1

Problema

Analisi Individuazione soluzione

Descrizione soluzione Formulazione

descrizione

Interpretazione descrizione

Attuazione soluzione

Descrizione interpretata Soluzione

(4)

Un esempio di problema e di soluzione (esecutore umano)

• Problema: come si fa una telefonata?

• Soluzione:

1. Solleva il ricevitore 2. Componi il numero

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

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 solo operazioni aritmetiche e confronti tra numeri

(5)

Soluzioni e Algoritmi…

• La soluzione è quindi espressa come sequenza di operazioni la cui esecuzione porta alla soluzione del problema ALGORITMO RISOLUTIVO

ALGORITMO

DATI SOLUZIONE

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)

(6)

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!

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?

(7)

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”

Docente: A.Gerevini

Elaborazione di Informazione

• Siamo interessati ai problemi che possono essere risolti attraverso elaborazione di informazione

• Problema di elaborazione dell’informazione: insieme di dati di partenza e risultato ricercato

• Ogni soluzione di un problema è una procedura che genera un risultato sulla base dei dati di partenza

Elaborazione

dati risultato

(8)

Soggetto Esecutore

• Il soggetto esecutore (soggetto 2) deve essere in grado di interpretare la descrizione della soluzione

• Deve inoltre essere in grado di eseguire le azioni presenti nella descrizione interpretata

• Il calcolatore è un esecutore di soluzioni identificate e descritte da esseri umani (in genere un team di progettisti, programmatori e utenti)

• Caratteristiche di un calcolatore: linguaggio che è in grado di interpretare e istruzioni che è in grado di eseguire

• Quando/perchè usare un calcolatore come esecutore?

Docente: A.Gerevini

Il Calcolatore come Esecutore (una prima definizione)

CALCOLATORE

Metodo di soluzione di un

problema (programma -descrizione di un algoritmo -)

Dati iniziali (assegnati a variabili di input)

Risultati dell’esecuzione in corrispondenza dei dati iniziali

(assegnati a variabili di output)

(9)

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

Docente: A.Gerevini

Risolvere le ambiguità…

Caratteristiche di un esecutore (in modo più formale) 1. Il linguaggio che l’esecutore è in grado di interpretare

deve essere definito in termini formali: caratterizzazione sintattica dell’esecutore

2. L’insieme delle azioni che l’esecutore è in grado di compiere deve essere univocamente definito, e tali azioni devono essere deterministiche

3. L’insieme delle regole di associazione tra costrutti del linguaggio e azioni deve essere univocamente definito:

caratterizzazione semantica dell’esecutore

(10)

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

Docente: A.Gerevini

Algoritmi e Programmi

• Algoritmo: una sequenza di azioni (istruzioni) che, operando sui dati iniziali, consentono di ottenere i risultati che costituiscono la soluzione dell’istanza del problema in esame

• Ogni azione è detta passo (step) dell’algoritmo

(11)

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 l’esecuzione di un algoritmo

• 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

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

(12)

Proprietà di un Algoritmo (cont.)

• Funzione rappresentata: un algoritmo associa ai valori per le variabili di input valori per le variabili di uscita (i risultati).

• Correttezza: l’algoritmo perviene alla soluzione del compito cui è preposto (calcola correttamente la funzione rappresentata)

• Efficienza: l’algoritmo perviene alla soluzione del compito impiegando il numero minimo di risorse fisiche

– Risorse fisiche: tempo, memoria, ….

• Terminazione: l’esecuzione di un algoritmo deve terminare in un numero finito di passi

FINE LEZIONE 27/9/04

(13)

Algoritmi, Programmi e Calcolatore

• Un algoritmo deve essere comprensibile al suo esecutore

• 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

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

(14)

“Linguaggio Macchina”

• I circuiti elettronici di un calcolatore sono in grado di riconoscere ed eseguire un numero limitato di istruzioni

• L’insieme di queste istruzioni costituisce il linguaggio macchina

• I programmi eseguibili da un calcolatore sono sequenze finite di istruzioni in linguaggio macchina (che descrivono algoritmi, descritti attraverso programmi…)

Docente: A.Gerevini

Linguaggi di Programmazione

• In generale, oggi i programmatori usano linguaggi di programmazione di alto livello

• Questi linguaggi:

– hanno costrutti più vicini al ragionamento umano

– consentono al programmatore di descrivere i problemi a un livello di astrazione di poco inferiore a quello degli algoritmi

– permettono di ragionare secondo una logica vicina al problema piuttosto che alle caratteristiche fisiche del calcolatore

• I programmi scritti in questi linguaggi devono subire un processo di traduzione per essere comprensibili da parte del calcolatore: un calcolatore “capisce” solo la sua lingua (il linguaggio macchina)

(15)

Il Calcolatore come Esecutore (una definizione rivisitata)

• Un calcolatore è un sistema che, ricevendo in ingresso la descrizione, in un opportuno

linguaggio, di un algoritmo risolvente A[In,Out]

(cioè un programma) per un certo problema P[In,Out] e un dato In, produce un risultato Out, ovvero la soluzione Out dell’istanza P[In,Out]

• Un calcolatore è un esecutore universale di programmi

Docente: A.Gerevini

Esempio

CALCOLATORE

Programma per il calcolo della potenza n-esima di x: P[x, n, y]

dati iniziali x = 2, n = 5

Risultati dell’esecuzione in corrispondenza dei dati iniziali

y = 32

input output

Istanza del problema = P[2,5,y]

(16)

Esercizio

Scrivere un algoritmo che risolve il seguente problema: determinare il valore Y della 7ma potenza di X.

E se anche l’ordine della potenza è una variabile di ingresso?

1 Docente: A.Gerevini