• Non ci sono risultati.

Il concetto intuitivo di calcolatore

N/A
N/A
Protected

Academic year: 2021

Condividi "Il concetto intuitivo di calcolatore"

Copied!
7
0
0

Testo completo

(1)

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 = ?

(2)

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 2

b

oppure Soggetto 1

b

Problema

Analisi 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

(3)

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

(4)

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

(5)

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

(6)

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

(7)

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

Riferimenti

Documenti correlati

2) Sul dischetto devono essere scritte le classi Funzione e ProvaFunzione. 3) Meglio indicare il proprio nome e cognome, oltre che su questo foglio, anche come commento in testa

Dire, motivando la risposta, quale è la complessità asintotica del metodo, espressa con notazione O(.) rispetto ad M, N ed S, con la migliore approssimazione possibile..

Motivare adeguatamente

Motivare

Motivare adeguatamente

Dire inoltre quale è la complessità di tale metodo nel caso peggiore e la complessità nel caso migliore, precisando anche in quale circostanza si verifica il

Sussiste il delitto di tentata concussione quando venga posta in essere da parte del pubblico ufficiale una condotta prevaricatrice senz’altro idonea ed inequivocabilmente

Musica, Storia, Scienze, Italiano, Geografia, Educazione civica, Attività alternativa all’IRC, Arte e immagine. Di