PLS
Programma Operativo Regionale 2007/2013
ALGO…DOG
(giochiamo con l’informatica)
RISOLUZIONE DI UN PROBLEMA
Vediamo due semplici esempi:
Piano Lauree Scientifiche - Liceo Scientifico
"Adriano Tilgher" - Ercolano (NA)
2
ESEMPIO 1
:
Cercare un nome e la sua posizione, all’interno di una
lista di n nomi ordinati.
I passi necessari alla risoluzione del problema sono:
1.Costruire un modello matematico che permetta di risolvere
il problema
2.Scomporre il modello in passi semplici e direttamente
eseguibili
3.Costruire l’algoritmo risolutivo
4.Tradurlo nel linguaggio di programmazione scelto
Piano Lauree Scientifiche - Liceo Scientifico
"Adriano Tilgher" - Ercolano (NA)
3
Il problema chiede di verificare che il nome sia nella lista ed in caso positivo di
darne la posizione. Si deve costruire un modello matematico che lo risolva:
Algoritmo 1 (ricerca sequenziale):
Si possono confrontare direttamente i nomi in modo sequenziale ma, se il
nome cercato è uno degli ultimi e la lista è molto lunga, ciò comporta un gran
numero di operazioni.
In alternativa
Algoritmo 2 (ricerca binaria):
Confrontando il nome da cercare con il termine centrale della lista, si possono
avere tre possibilità:
a) Il nome coincide con l’elemento centrale: si è trovata la posizione ed il
problema è risolto
b) Il nome precede l’elemento centrale: si elimina la seconda metà dei
nomi e si ripete la procedura
c) Il nome segue l’elemento centrale: si elimina la prima metà dei nomi e
si ripete la procedura
d) Si ripetono i punti a), b), c) fino a quando il nome cercato non coincide
con l’elemento centrale
Piano Lauree Scientifiche - Liceo Scientifico
"Adriano Tilgher" - Ercolano (NA)
4
ESEMPIO: Dato il seguente elenco: ADA; BARBARA; CARLO; DOMENICO; ELISA; LORENZA;
MARIA; NICOLA , si vuole sapere la posizione relativa al nome MARIA.
ALGORITMO SEQUENZIALE
ALGORITMO BINARIO
IL COMPUTER
IL COMPUTER
1. Prende il primo nome e lo confronta con
quello cercato: ADA≠MARIA
2. Prende il secondo nome e lo confronta con
quello cercato: BARBARA≠MARIA
Calcola la posizione centrale  4
1. Confronta il nome di posto 4 con il nome
cercato: DOMENICO≠MARIA e DOMENICO
precede MARIA
Elimina i primi quattro nomi ed a partire da 5 a
8 ricalcola la posizione centrale  6
………………………..
6. Prende il sesto nome e lo confronta con
quello cercato: LORENZA≠MARIA
7. Prende il settimo nome e lo confronta con
quello cercato: MARIA = MARIA
Comunica che il nome cercato occupa la
posizione 7 su 8
2. Confronta il nome di posto 6 con il nome
cercato: LORENZA≠MARIA e LORENZA precede
MARIA
Elimina i primi sei nomi ed a partire da 7 a 8
ricalcola la posizione centrale  7
3. Confronta il nome di posto 7 con il nome
cercato: MARIA = MARIA
Comunica che il nome cercato occupa la
posizione 7 su 8
Piano Lauree Scientifiche - Liceo Scientifico
"Adriano Tilgher" - Ercolano (NA)
5
Come si fa a scegliere tra i due algoritmi costruiti?
Uno dei parametri che permetterà di scegliere tra i due è l’EFFICIENZA .
L’EFFICIENZA di un algoritmo dipende dal numero di operazioni richieste per ottenere il risultato.
Dall’esempio fatto si può vedere che:
• l’algoritmo sequenziale prevede un numero di confronti della stessa grandezza del numero di
elementi dati (per avere la posizione occupata dal nome MARIA sono stati fatti 7 confronti avendo
in totale 8 elementi)
•L’algoritmo binario prevede un numero di confronti molto più piccolo (sono stati fatti solo 3
confronti)
Ripetendo l’operazione con l’aumentare dei numeri si vede che l’algoritmo binario ha un numero di
confronti pari a log2n. Dalla tabella seguente si evince quanto sia più efficiente l’algoritmo binario
n. elementi
8
16
32
64
128
…..
1024 2048 4096 8192 16384
n
ALG. SEQ.
8
16
32
64
128
…..
1024 2048 4096 8192 16384
n
ALG. BIN.
3
4
5
6
7
…..
10
11
Piano Lauree Scientifiche - Liceo Scientifico
"Adriano Tilgher" - Ercolano (NA)
12
13
14
log2n
6
Si è scelto di utilizzare la seconda tecnica e quindi si passa a costruire
l’algoritmo risolutivo, cioè in una serie finita di istruzioni non ambigue.
Una volta costruito, l’algoritmo risolverà non solo il problema di partenza
ma, al cambiare del nome e del numero di elementi della lista, tutte le
ricerche simili
Si devono perciò definire gli oggetti matematici da utilizzare:
1. l’elenco dei nomi è definito da una variabile con indice E(i) con
i=1,…,n
2. NOME indica l’elemento di cui si deve trovare la posizione
3. POS indica la posizione dell’elemento da cercare
4. Si ha poi bisogno di una serie di postazioni di memoria necessarie
per i calcoli e quindi si useranno le variabili: INIZIO, FINE, M.
Piano Lauree Scientifiche - Liceo Scientifico
"Adriano Tilgher" - Ercolano (NA)
7
Algoritmo Binario
leggi NOME, n
metti in i il valore 0
Ripeti n volte
metti in i il valore i +1
leggi ELENCO(i)
Fino a qua
metti in INIZIO il valore 1
metti in FINE il valore n
metti in POS il valore 0
Ripeti
metti in M il valore (INIZIO+FINE)/2
Se NOME = ELENCO(M) allora
metti in POS il valore M
stampa POS
fine
Altrimenti
Se NOME < ELENCO(M) allora
metti in FINE il valore M-1
Altrimenti
metti in INIZIO il valore M+1
Fino a quando INIZIO  FINE
Le istruzioni:
• leggi e stampa sono istruzioni di
ingresso e uscita dei dati
• metti in è un’istruzione di assegnazione
• Ripeti …. Fino a qua è un’istruzione che,
mediante un controllo, permette di
rifare le stesse operazioni un certo
numero di volte o fino a quando non si
verifica una certa condizione
• Se …. Allora …. Altrimenti è una
istruzione di scelta che permette di
effettuare operazioni diverse al
cambiare del verificarsi della condizione
Dopo aver costruito
l’algoritmo lo si dovrà provare
e poi tradurre in un
linguaggio di
programmazione per poterlo
far eseguire da un computer
Piano Lauree Scientifiche - Liceo Scientifico
"Adriano Tilgher" - Ercolano (NA)
8
ESEMPIO 2
:
Costruire un gioco che permetta di fare delle somme
con un aspetto grafico adatto a dei bambini
Il nostro piccolo animale:
•Si muoverà
•Ci chiederà i numeri
•Ci darà il risultato della somma
Risolviamo tale problema utilizzando il
linguaggio di programmazione didattico Scratch
Piano Lauree Scientifiche - Liceo Scientifico
"Adriano Tilgher" - Ercolano (NA)
9
SCRATCH: “immagina, programma, condividi”
É una piattaforma virtuale che offre la possibilità di emulare un
linguaggio di programmazione e che consente di elaborare storie
interattive, giochi, animazioni.
Scratch mette a disposizione
gli “Sprite”: personaggi che
svolgono le diverse
operazioni richieste.
Scratch offre diversi sfondi
dove ambientare le proprie
creazioni.
Piano Lauree Scientifiche - Liceo Scientifico
"Adriano Tilgher" - Ercolano (NA)
10
Queste sono tutte le categorie
presenti in scratch:
Ne osserveremo le più importanti.
Piano Lauree Scientifiche - Liceo Scientifico
"Adriano Tilgher" - Ercolano (NA)
11
Situazioni
Questi “mattoncini”, al verificarsi
della condizione definita, ci
permettono di iniziare una
determinata serie di operazioni.
Esempio:
Questo blocco consente di eseguire
alcune operazioni dopo aver
premuto il tasto spazio.
Piano Lauree Scientifiche - Liceo Scientifico
"Adriano Tilgher" - Ercolano (NA)
12
Controllo
Queste strutture consentono di
controllare e ripetere delle azioni.
Esempio:
Questo blocco permette di compiere
un’operazione solo se una
determinata condizione è
soddisfatta. La condizione andrà
inserita nell’esagono vuoto.
Piano Lauree Scientifiche - Liceo Scientifico
"Adriano Tilgher" - Ercolano (NA)
13
Movimento
Questi elementi permettono il
movimento del soggetto (sprite).
Esempio:
Questo blocco consente allo sprite di
avanzare di 10 passi.
Piano Lauree Scientifiche - Liceo Scientifico
"Adriano Tilgher" - Ercolano (NA)
14
Aspetto
Questi elementi permettono di
modificare l’aspetto degli sprite.
Esempio:
Questo blocco consente di
aumentare la dimensione dello
sprite.
Piano Lauree Scientifiche - Liceo Scientifico
"Adriano Tilgher" - Ercolano (NA)
15
Sensori
Definiscono delle condizioni che
consentono agli sprite di compiere
determinate azioni.
Esempio:
È una condizione che viene
soddisfatta quando lo sprite tocca
il bordo.
Piano Lauree Scientifiche - Liceo Scientifico
"Adriano Tilgher" - Ercolano (NA)
16
Operatori
Permettono di svolgere diverse
operazioni matematiche.
Esempio:
Questo blocco esegue la somma di
due numeri.
Video somma
Piano Lauree Scientifiche - Liceo Scientifico
"Adriano Tilgher" - Ercolano (NA)
17
Progetti realizzati con Scratch
NOME COGNOME
NICKNAME
PROGETTO/I
Ascione Antonio
ascio97
Star Wars
Piscinnis
Fisica
Liguoro Vincenzo
vizzforzanapoli
Gattino che fa goal!
Pignalosa Camillo
19max96
The last flight of IVB plane
Pinbal01
Planet Maze
Labirinto1
AlgoDog
Reccia Luca
lucareccia
Multiplayer race
hitTheBat
tennis con mario
AlgoDog
Scognamiglio Mauro
mauro24
fish war
MAURO’S FROGGER
CATEINSTEIN
Filosa Veronica
Veronica35
Questionario ;)
Piano Lauree Scientifiche - Liceo Scientifico
"Adriano Tilgher" - Ercolano (NA)
18
Piano Lauree Scientifiche - Liceo Scientifico
"Adriano Tilgher" - Ercolano (NA)
19
Partecipanti al PLS
ALUNNI
Giovanni ACAMPORA
Raffaella ACAMPORA
Antonio ASCIONE
Gennaro COLOMBA
Luciana COZZOLINO
Maria Rosaria D’AMBROSIO
Ilaria FALANGA
Veronica FILOSA
Francesco FORMISANO
Antonio GAMEN
Giulia GAMEN
Vincenzo LIGUORO
Vincenzo MAIELLO
Maria MARINO’
Emanuela MASUCCI
Camillo PIGNALOSA
Luca RECCIA
Luisabel ROTONDO
Gennaro RUSSO
Sergio SANNINO
Mauro SCOGNAMIGLIO
DOCENTI – Istituto Tilgher:
Prof.ssa Norina Di Fiore
Prof.ssa Rita Punzo
Piano Lauree Scientifiche - Liceo Scientifico
"Adriano Tilgher" - Ercolano (NA)
20