alunno Simone Pupino 4° A Programmatori ITCG “RUFFINI” Imperia
RELAZIONE RIGUARDANTE LO STAGE AL DIPARTIMENTO DI MATEMATICA E INFORMATICA DI GENOVA
2-3-4 FEBBRAIO 2010
N.B. alcuni disegni ed alcune nozioni sono tratti da Wikipedia
1_GRAFI E SCRATCH
GRAFI
Comincerò a parlare dei grafi; in questa parte i grafi saranno legati al problema del commesso viaggiatore, d’ora in poi lo abbrevierò con TSP (Traveling Salesman’s Problem). Prima detterò un pò di caratteristiche del TSP: innanzitutto è uno dei problemi matematici più studiati in informatica e appartiene alla classe dei problemi difficili; la sua forma generale considera forme geometriche di qualsiasi tipo e le distanze tra le varie città.
Esposizione del problema TSP: un commesso viaggiatore deve visitare un determinato numero di città conoscendone la loro distanza e vuole determinare il percorso più breve che gli permetta di partire da casa sua, attraversare una sola volta tutte le città e ritornare a casa sua. Modelliamo un TSP e quindi un grafo:
Come possiamo vedere i pallini neri sono i nodi, ovvero le città, le linee nere che uniscono un nodo all’altro sono le strade, ovvero i lati, e i numeri affianco sono i pesi, ovvero le distanze.
Questo è un tipico esempio di grafo, ma come facciamo a risolverlo?
Hamilton fu il primo matematico che studiò e risolvette i grafi. Dato un grafo G con nodi N e archi pesati, un ciclo si definisce Hamiltoniano (o tour) quando inizia e finisce nello stesso nodo e passa dagli stessi una sola volta con peso totale minimo.
Ad esempio, prendendo il grafo soprastante, se noi partissimo da Genova, andassimo a Torino, Aosta, Milano e quindi a Genova, faremmo un ciclo hamiltoniano; se facessimo un percorso del tipo Genova, Torino, Aosta, Genova non faremmo più un ciclo hamiltoniano perchè avremmo escluso un nodo, ovvero Milano.
Ma esistono soluzioni al TSP?
Si certo, e si possono classificare in 2 tipi: manuale o euristico. Una soluzione manuale vuol dire che noi andremo a trovare manualmente una soluzione esatta al problema TSP. Con un numero relativamente basso di nodi è possibile, ma, tenuto conto che le possibilità dal nodo di partenza sono n!, più aumentiamo i nodi e più sarà difficile (se non impossibile).
Per esempio, negli USA ci sono 49 stati; se noi dovessimo programmare un tour che percorra tutti gli stati avremmo dalla prima citta 49! possibilità per fissare la seconda città, alla seconda città avremmo 48! possibilità etc...Quindi per questo grafo ci sono 1062 possibilità! Un pò troppe per risolvere il grafo manualmente....
Infatti per questo motivo sono stati introdotti algoritmi Euristici. Che cos’è un algoritmo Euristico? Non è altro che una risoluzione al problema che fornisce soluzioni probabilmente buone ma non ottimali.
Un esempio di algoritmo Euristico è il NN, ovvero Nearest Neighbour; partendo da un nodo iniziale ci si muove verso il nodo a noi più vicino ancora non visitato e l’algoritmo termina quando abbiamo visitato tutte le città.
Ad esempio sul grafico di prima, partendo in tutti e due i casi da Genova, il percorso ottimale, trovato manualmente, è Torino-Aosta-Milano-Genova (169+115+186+140 =610) mentre utilizzando l’algoritmo NN il percorso sarà Milano-Torino-Aosta-Genova (140+142+115+246=643). Come si può vedere questo è un chiaro esempio che l’algoritmo NN non è ottimale e che manualmente si trova la soluzione esatta, ma come già spiegato non sempre è facile trovare una soluzione manuale al problema.
Esistono molti altri modi per risolvere un grafo, ma noi abbiamo preso in considerazione solo questi due.
SCRATCH
Scratch è un ambiente didattico che permette di imparare i concetti base della programmazione: sviluppato al MIT (Massachussets Institute of Technology), permette di costruire programmi interattivi imparando in modo naturale concetti complicati e importanti nella programmazione, come variabili, movimenti, temporizzazione, comunicazione, utilizzando semplici blocchi che si andranno ad incastrare fra loro, creando una specie di diagramma a blocchi.
2_GRAFI E MATEMATICA GENERALE
In mattinata ci è stato proposto di esaminare particolari quesiti matematici, oltre che a ragionare un pò sulla materia con l’aiuto di un docente universitario. Si è trattato in genere di dimostrazioni, come per esempio dimostrare che i numeri reali sono infiniti...
Nel pomeriggio ci è stato illustrato, sempre rimanendo nell’ambiente dei grafi, il problema di Eulero riguardante la città di Koningsberg.
Il problema dei sette ponti di Königsberg è un problema ispirato da una città reale e da una situazione concreta. La città di Königsberg, presenta due estese isole che sono connesse tra di loro e con le due aree principali della città da sette ponti.
Ci si pone la questione se sia possibile con una passeggiata seguire un percorso che attraversa ogni ponte una e una volta sola e tornare al punto di partenza. Nel 1736 Leonhard Euler lavorò sul problema e dimostrò che la passeggiata ipotizzata non era possibile.
L’immagine mostra la città con i suoi sette ponti. Eulero ha il merito di aver formulato il problema in termini di teoria dei grafi: rimpiazzò ogni area urbana con un punto, ora chiamato vertice o nodo e ogni ponte con un segmento, chiamato spigolo, arco o collegamento.
Eulero rappresentò la disposizione dei sette ponti congiungendo con altrettante linee le quattro grandi zone della città, come nella prima immagine. Si noti che dai nodi A, B e D partono (e arrivano) tre ponti; dal nodo C, invece, cinque ponti. Questi sono i gradi dei nodi: rispettivamente, 3, 3, 5, 3.
Prima di raggiungere una conclusione, Eulero ha ipotizzato delle situazioni diverse di zone e ponti (nodi e collegamenti): con quattro nodi e quattro ponti è possibile partire, ad esempio, da A, e tornarci passando per tutti i ponti una e una sola volta. Il grado di ciascun nodo è un numero pari. Dopo aver ragionato a lungo Eulero ha enunciato il seguente teorema: Un qualsiasi grafo è percorribile se e solo se ha tutti i nodi di grado pari, o due di essi sono di grado dispari; per percorrere un grafo "possibile" con due nodi di grado dispari, è necessario partire da uno di essi, e si terminerà sull’altro nodo dispari. Pertanto è impossibile percorrere Königsberg poiché tutti i nodi sono di grado dispari. Eulero ha inoltre dimostrato che per un grafo qualsiasi un cammino con le caratteristiche desiderate è possibile se e solo se il grafo non ha vertici (i punti nel grafo) che sono raggiunti da un numero dispari di spigoli. Un tale cammino è chiamato circuito euleriano. Dato che il grafo relativo a Königsberg ha quattro di tali vertici, il cammino non esiste.
3_SILLOGISMI E SARKOVSKY
Il sillogismo è un tipo di ragionamento dimostrativo che fu teorizzato per la prima volta da Aristotele. Egli ha cominciato un loro studio sistematico.
La logica è lo studio del pensiero e di come si espime nel linguaggio e fu “scoperto” 200.000 anni fa. Essa riguarda la connessione tra l'insieme delle premesse di un argomento e la sua conclusione, per esempio:
In tutte le materie scolastiche ho la sufficienza; matematica è una materia scolastica => In matematica ho la sufficienza.
Non è un sillogismo: In alcune materie ho la sufficienza; matematica è una materia => In matematica ho la sufficienza.
Il quadrato logico è un metodo di classificazione dei concetti legati ad una opposizione di concetti. È stato introdotto da Aristotele. A partire da un'opposizione data di concetti S1 e S2, il quadrato logico presuppone l'esistenza di altri due concetti, ossia ~S1 and ~S2, che stanno tra loro nelle seguenti relazioni:
….