Algoritmica e Problem Solving, Linguaggi di programmazione

UNIVERSITÁ DEGLI STUDI PISA
DIPARTIMENTO DI INFORMATICA
PAS Toscana-Percorso abilitante speciale
Algoritmica e Problem Solving, Linguaggi di
programmazione, Laboratorio
Dott.ssa Lisa Bellanti
Classe di abilitazione A042- Informatica
Algoritmica e Problem Solving, Linguaggi di programmazione, Laboratorio
Questo corso ha l’ intenzione di mostrare ai ragazzi delle scuole superiori l’importanza del
pensiero algoritmico sia come strategia generale per affrontare i problemi sia come metodo per
ottenere una soluzione che come linguaggio universale per comunicare con gli altri. Un processo
cognitivo in cui prevale il pensare, l’immaginare, il ragionare, il fare ipotesi, favorendo c osì
l’acquisizione di competenze trasversali ai diversi contesti disciplinari. Uno tra gli obbiettivi
fondamentali sarà far capire ai ragazzi la potenza delle idee e la vanità di ogni pretesa di
prevedere dove ci porteranno. A volte la capacità di previsione della finzione e dell’
immaginazione indovina gli aspetti tecnologici, ma ignora in pieno altre rivoluzioni che
trasformano la società. L’ ottimismo che è alla base della ricerca scientifica promette che
supereremo le difficoltà e saremo in grado di risolvere e costruire algoritmi per quasi tutti i
problemi, sta a noi decidere come e dove applicarli se per scopi umanitari o per costruire robot
assassini e bombe atomiche ‘’Da un grande potere derivano grandi responsabilità,, Amazing
Fantasy. La teoria della complessità e calcolabilità essendo in bilico fra matematica, informatica,
ingegneria elettronica e filosofia non è semplice e vede la sua genesi addirittura tempi di Aristotele
con il tentativo di ridurre il ragionamento logico ad una serie di regole formali. Calcolo e
ragionamento logico sono facce della stessa medaglia, intuizione che dobbiamo ricordare non solo
nel programmare i calcolatori, ma anche per progettarli e costruirli. Da Aristotele a Leibniz, Boole,
Hilbert, Godel, Turing , nell’ arco di tre secoli si è prodotta una matrice intellettuale dalla quale è
uscito il calcolatore moderno. Solo Turing ha visto concretizzare la sua intuizione, Leibniz
guardava lontano, ma non fino a questo punto. Turing e von Newmann paragonarono il
calcolatore al cervello umano: la nostra capacità di fare più cose diverse poteva essere dovuta alla
presenza nel nostro cervello di un calcolatore universale. Non possiamo escludere questo a priori:
che il nostro cervello possa operare secondo processi algoritmici non è stato ancora dimostrato,
ma non è stato dimostrato neppure il suo contrario. Un approccio bottom-up potrebbe essere
quello realizzato con gli studi sull’ Intelligenza Artificiale, sulle Reti Neurali, sulle logiche Fuzzy, sui
Sistemi Intelligenti in cui si parte dall’ osservazione dei meccanismi di funzionamento naturali
(Neuroni, logiche di pensiero) e se riproduce il funzionamento, ovvero si costruisce un algoritmo
in grado di simulare l’ elemento: dal semplice neurone fino al funzionamento dell’ apparato.
Ritorna così il dualismo Cartesiano della ‘’res cogitans’’ e ‘’res extensa’’ anche lui aveva avuto un’
intuizione brillante…chissà fra quanto e se la sua idea troverà forma se ci sarà un algoritmo per la
mente e un algoritmo per la materialità dell’ uomo. Bisogna stimolare i ragazzi ad avere idee, a
ricercare, bisogna incuriosirli e fornirgli un metodo per organizzare le loro idee e progetti ed un
linguaggio universale per comunicarle. Non importa se oggi non le vedranno realizzate ma non
saranno certo i primi a volte ci vuole un po’ di tempo perché scienza e tecnologia recuperino il
ritardo rispetto all’ immaginazione. Forse Leibniz non immaginava tutto questo
https://www.youtube.com/watch?v=g1NJ9Vv-Y6Q
Algoritmica e Problem Solving, Linguaggi di programmazione, Laboratorio
Descrizione della classe:
La classe a cui ho proposto il seguente percorso didattico è una II Liceo Scientifico ad indirizzo
Scienze applicate che prevede nel piano di studi due ore settimanali di Informatica. Nel secondo
quadrimestre, nell’ ambito di un progetto con il Comune di Carrara, le ore da due sono salite a tre.
Al termine del percorso di studi delle Scienze Applicate l’alunno dovrà secondo le linee guida aver
raggiunto i seguenti obiettivi di apprendimento oltre a quelli di area comune:
“[…]
aver
appreso
concetti,
principi
e
teorie
scientifiche
anche
attraverso esemplificazioni operative di laboratorio; elaborare l'analisi critica dei fenomeni
considerati, la riflessione metodologica sulle procedure sperimentali e la ricerca di
strategie atte a favorire la scoperta scientifica; analizzare le strutture logiche coinvolte ed i
modelli utilizzati nella ricerca scientifica; individuare le caratteristiche e l'apporto dei vari
linguaggi;comprendere il ruolo della tecnologia come mediazione fra scienza e
vita quotidiana; saper utilizzare gli strumenti informatici in relazione all'analisi
dei
dati
e
alla
modellizzazione
di
specifici
problemi
scientifici
e
individuare
la
funzione
dell'informatica
nello
sviluppo
scientifico,,
Il livello della classe è medio alto e Il percorso didattico (in parte effettivamente realizzato) si
colloca nel secondo quadrimestre.
Prerequisiti :



Conoscenze elementari sugli insiemi numerici
Nozioni base di programmazione
Nozioni base di programmazione in C
Linee didattiche e metodologiche (piano di lavoro):
Nell'ottica di un approccio costruttivista e socio-costruttivista la situazione complessa viene
presentata agli studenti fin dall'inizio per stimolarne la motivazione, far emergere domande ed
attivare una proficua disposizione al lavoro di gruppo fra pari, in cui l'errore e gli ostacoli
divengono parte integrante del percorso didattico-educativo. Tutte le unità didattiche saranno
essenzialmente suddivise in tre parti una prima fase in cui si cerca di contestualizzare l’ argomento
e stimolare il ragazzo alla ricerca e al pensiero, una seconda fase teorica in cui vengono forniti ai
ragazzi materiali e metodi per poter operare ed una terza fase di verifica degli apprendimenti.
Algoritmica e Problem Solving, Linguaggi di programmazione, Laboratorio
Modulo calcolabilità e complessità:
Calcolabilità
•Nozione Intuitiva di algoritmo
•Metodo algoritmico
•Problemi Semiseri
U.D.1
Calcolabilità
•Macchine di Turing, computabilità effettiva
•Macchine di Turing Universali
U.D.2
•Limiti del modello di calcolo
•Problema della fermata
Crisi
U.D.3
Complessità
•Tempo e spazio, Complessità computazionale
•Classi di Complessità, problemi trattabili e intrattabili
U.D.4
Linguaggio di
programmazione : C
•Linee standard per la risoluzione degli algoritmi:
•Ricorsività
•Divide et impera
U.D.1 Calcolabilità:
Obiettivi specifici
Obiettivi cognitivi




Conoscere le principali tecniche e metodologie per progettare algoritmi
Conoscere cosa è un algoritmo e cosa è un programma
Conoscere le caratteristiche principali di un algoritmo
Conoscere le strutture di controllo fondamentali
Obiettivi operativi

Costruire semplici algoritmi
Contenuti
Nozione Intuitiva di Algoritmo, schemi di composizione degli algoritmi, dall’ algoritmo al
programma. Dagli algoritmi più moderni agli algoritmi più antichi, l’algoritmo di Euclide.Cenni agli
Algoritmica e Problem Solving, Linguaggi di programmazione, Laboratorio
algoritmi fondamentali: Ricerca, Ordinamento. Problema del fattoriale. Problemi del commesso
viaggiatore.
Metodologia:
Fase 1 : contestualizzazione e motivazione dei ragazzi. Esempi tratti dalla quotidianità. Riflessioni
su le analogie e le differenze tra questi algoritmi. Tutti lavorano su input e producono output,
input ed output vengono codificati alla stessa maniera come stringhe di bit ciò che cambia è l’
algoritmo che li processa…la back-box.
1. Ricette di cucina, programma della lavatrice
2. "What Makes an Image Popular?", Khosla ha analizzato oltre 2,3 milioni di fotografie
caricate da migliaia di utenti su Flickr. In seguito ha sviluppato un algoritmo che consente
di prevedere in modo affidabile il numero di visualizzazioni che riceverà un immagine
basandosi sul suo contenuto.
3. La compressione MP3 algoritmo lossy
4. ‘’Hummingbird’’ algoritmo di google che analizza parametri tra quelli provenienti dal
‘’Pagerank’’, con l’obiettivo di evolvere verso un web semantico con cui è possibile dare
risposte a ricerche più evolute.
Fase 2: Esposizione dei contenuti.
Fase 3: Verifiche Formative: Ricerche assegnate ai ragazzi suddivise per gruppi su algoritmi
attualmente in uso sul web. Progettazione di schemi di algoritmi (dal problema all’ algoritmo)
analisi di algoritmi in particolare gli algoritmi fondamentali. Progettazione dell’ algoritmo di
Euclide
U.D.2 Calcolabilità:
Obiettivi specifici
Obiettivi cognitivi



Conoscere la macchina di Turing e interpretarne le istruzioni in casi elementari
Conoscere la macchina di Turing per formalizzare il concetto di algoritmo
Capire cosa significa scomporre un processo di calcolo in passi elementari.
Obiettivi operativi

Costruire il processo di risoluzione di un problema semplice come un percorso a stati
successivi
Contenuti
Macchina di Turing: Nastro infinito diviso in celle, unità centrale, testina di lettura e scrittura,
insieme di istruzioni; Macchina di Turing funzionamento; Macchina di Turing come automa
teorico ; Ogni M.di T. è una macchina astratta poiché il suo nastro è infinito, ma è una macchina
logica che serve per evidenziare come ogni processo di calcolo sia scomponibile in passi
elementari. Dalla Macchina di Turing a Von Neumann fino ai moderni calcolatori. ( organizzazione
Algoritmica e Problem Solving, Linguaggi di programmazione, Laboratorio
logica del computer ALU-CU-Memoria). Macchina di Turing Universale macchina in grado di
risolvere qualsiasi problema risolvibile da qualsiasi altra macchine di Turing.
Metodologia:
Fase 1 : contestualizzazione e motivazione dei ragazzi.
Riflessione sulle operazioni fondamentali: addizione e sottrazione. Schematizzazione del processo
di calcolo sia per l’ addizione e la sottrazione che i loro derivati.
Eliza: analisi dell’algoritmo, simulazione in classe
http://www.conscious-robots.com/index.php?lang=en
Fase 2: Esposizione dei contenuti.
Fase 3: Verifiche Formative: semplici algoritmi da realizzare mediante
http://mdt.di.unipi.it/TMSimulatore/TMApplet.html
U.D.3 Crisi:
Obiettivi specifici
Obiettivi cognitivi



Conoscere i limiti e le potenzialità delle Macchine di Turing
Riconoscere il limite del procedimento algoritmico.
Conoscere l’ assolutezza della definizione di non risolubilità
Obiettivi operativi


Saper distinguere fra problemi risolvibili e non
Saper ragionare per assurdo
Contenuti
Esistono problemi che le Macchine di Turing non possono risolvere ma non esiste altra macchina
che possa risolverli; Il teorema di Godel: teorema fondamentale della matematica e della
informatica moderna ‘’ Per ogni sistema formale di regole ed assiomi è possibile arrivare a
proposizioni indecidibili, usando gli assiomi dello stesso sistema formale" il rapporto è come quello
fra numeri Naturali e Numeri Reali; Diagonalizzazione di Cantor; Teorema dell’ arresto
Metodologia:
Fase 1 : contestualizzazione e motivazione dei ragazzi.
Discussione sul test oggettivo di Turing: è possibile programmare un calcolatore in modo che
sappia conversare in modo da essere confuso con un essere umano?
Algoritmica e Problem Solving, Linguaggi di programmazione, Laboratorio
Problemi irresolubili, problema della fermata.
Fase 2: Esposizione dei contenuti.
Fase 3: Verifiche Formative: Interrogazioni; Elaborato scritto.
U.D.4 Complessità:
Obiettivi specifici
Obiettivi cognitivi


Conoscere i limiti fisici: spazio tempo
Riconoscere il limite del procedimento algoritmico.
Obiettivi operativi


Saper distinguere fra problemi risolvibili, irrisolvibili e non risolvibili per limiti fisici: spazio
e tempo.
Saper valutare la complessità di un algoritmo.
Contenuti
Definizione di complessità, nozione di costo, variabile a seconda dei valori in ingresso; complessità
polinomiale, complessità esponenziale, logaritmica. Problemi trattabili e problemi intrattabili.
Problemi NP-Completi (l’esperienza dice che non sono trattabili ma non ce ne è stata ancora la
risoluzione) Problemi P( risolvibili) problemi NP( mi serve un oracolo, sono polinomiali a patto che
esista l’oracolo)
Metodologia:
Fase 1 : contestualizzazione e motivazione dei ragazzi.
Problema delle Torri di Hanoi (complessità esponenziale in tempo) nei buddismo il simbolo dell’
infinito è una torre con 64 dischi,http://www.youtube.com/watch?v=Q4gTV4r0zRs
Problema del fattoriale (complessità esponenziale in spazio)
Problema del SudoKu (problemi NP-completi)
Problema della primalità
Riflessioni su tempo e spazio.
Fase 2: Esposizione dei contenuti.
Fase 3: Verifiche Formative: Interrogazioni; Elaborato scritto. In laboratorio misurazione dei tempi
di calcolo di programmi come il fattoriale di un numero.
Algoritmica e Problem Solving, Linguaggi di programmazione, Laboratorio
U.D. Linguaggi di programmazione: C
In questa sezione verranno tradotti qli algoritmi finora enunciati in linguaggio macchina in C.
Utilizzando un approccio Top-Down i problemi complessi vengono scomposti in problemi più
semplici. Come ogni linguaggio attuale il C consente di dichiarare sottoprogrammi che possono
essere invocati nel corso dell’ esecuzione di una sequenza di istruzioni a partire da una sequenza
principale (il corpo del programma). In genere distinguiamo due tipi di sottoprogrammi: le
procedure e le funzioni
Obiettivi specifici
Obiettivi cognitivi



Conoscere le strutture base del linguaggio di programmazione C
Tradurre un algoritmo in un programma C.
Conoscere la struttura di un programma in C
Obiettivi operativi


Saper realizzare semplici programmi
Saper utilizzare la ricorsività e il divide et impera.
Contenuti
Struttura di un programma C; Linee standard per la risoluzione di algoritmi: la ricorsività e Divide
et Impera; Traduzione in linguaggio C di Algoritmi ricorsivi e Algoritmi risolvibili con il divide et
Impera; traduzione dei programmi citati sopra.
Metodologia e Verifiche
Implementazione di alcuni degli Algoritmi citati nelle UD 1,2,3,4.
Ricorsività:
Problema del fattoriale di un numero, Problema della potenza di un numero. Realizzazione dei due
programmi in maniera ricorsiva.
Algoritmica e Problem Solving, Linguaggi di programmazione, Laboratorio
#include <stdio.h>
int pot(int *x,int *y) {
if (y==0) return 1;
else return x*pot(x,y-1);}
int main() {
int a=3;
int b=2;
a=pot(&a,&b);
printf("%d",a);
return 0;}
#include <stdio.h>
int pot(int *x,int *y) {
if (*y==0) return 1;
else return x*pot(x,y-1);}
int main() {
int a=3;
int b=2;
a=pot(&a,&b);
printf("%d",a);
return 0;}
Complessità algoritmica: Problema della primalità di un numero confronto computazionale tra due
algoritmi.(quello classico e quello che utilizza la radice quadrata)
Divide et Impera: Problema della ricerca; ricerca binaria applicazione del metodo della ricorsione
a sotto problemi. Confronto con l’algoritmo e il programma di ricerca classico.
int binaria( int A,[], int *i,int *j,int *x){
int m;
if (i>j) return -1;
m=(i+j)/2;
if (A[m]==x) return m;
else if (A[m]<x)
return binaria(A,m+1,j,x)
else
return binaria(A,i,m-1,x)}
int classica( int p[], int *min;){
int i;
int m=0;
for (i=1;i<10;i++) {
if (p[i]=*min) return i;
}
}
Verifiche sommative:
Le valutazioni realizzate tramite le verifiche formative avranno funzione sommativa, in quanto
sono state adottate per apprezzare se gli alunni sapevano utilizzare capacità e conoscenze
acquisite durante una parte significativa dell’ itinerario di apprendimento. La valutazione finale
dovrà tener conto,oltre che dei prograssi di ogni alunno rispetto al livello di partenza, dei risultati
raggiunti in ogni unità, di tutti gli elementi significativi della sua situazione scolastica ed umana, compresa
la sfera socio affettiva.
Algoritmica e Problem Solving, Linguaggi di programmazione, Laboratorio

Download Report