mercoledì 25 agosto 2010

L'orario scolastico - FET: un esempio, attività e subattività

Riprendo l'esempio sul funzionamento di FET che ho preparato e che è scaricabile cliccando sul seguente link:
In questo articolo voglio parlare di attività e subattività, ovvero le ore di lezione che il software dovrà assegnare.

Dopo aver spiegato come inserire i dati principali e prima di discutere di come inserire i vincoli mi sembra opportuno parlare di attività e subattività. Attività e subattività sono le ore di lezione che il software dovrà piazzare per trovare l'orario, cioè quando si deve svolgere una determinata lezione.


Dalla scheda Dati, che ho riportato qui sopra, se si clicca su Attività si apre la seguente finestra:

Nella colonna di sinistra è riportato l'elenco (numerato in ordine crescente di inserimento) di tutte le attività e subattività fin qui inserito, nella colonna di destra è possibile vedere un riepilogo dei dati dell'attività selezionata nelle colonna di sinistra e, mediante i campi filtro, è possibile visualizzare invece che tutte le attività, le attività di un determinato insegnante, o di un determinato gruppo di studenti, o quelle relative ad una determinata materia o ad una determinata chiave. I filtri possono anche essere utilizzati contemporaneamente. 

Ok, direte voi, ma esattamente cosa sono le attività? e le subattività? Perché nella colonna di sinistra alcune righe sono rientrate rispetto ad altre? Per comprendere clicchiamo sul pulsante Aggiungi, si apre la seguente finestra:

Un'attività sarà tenuta da uno o più docenti (in caso di copresenze) selezionabili dalla lista insegnanti, riguarderà una data materia, la dovranno seguire una o più classi, selezionabili dalla lista studenti, avrà eventuali chiavi di attività e potrà essere suddivisa in una o più subattività. Spieghiamo questo concetto. Supponiamo che il piano di studi preveda che una determinata classe faccia sei ore a settimana con il professore di matematica. Posso immaginare l'insieme delle sei ore come un'unica attività suddivisa in sei subattività. Non solo, ma posso imporre la durata delle subattività, e allora preferisco fare cinque subattività di cui una di durata due ore e le altre di durata un'ora così da permettere eventuali compiti in classe. Non solo, ma posso anche vincolare quanti giorni far passare da una attività all'altra, così da garantire un orario uniforme spalmato su tutta la settimana, così come, al contrario, potrei permettere che le subattività si svolgano nello stesso giorno. 

Certo, avrei anche potuto definire sei attività di durata un'ora, ma sarebbe stato molto più inefficiente. 

Un'osservazione importante. Supponiamo che stiamo parlando del professore di lettere che fa 10 ore in una determinata classe (senza contare le copresenze). Potrei introdurre un'attività composta da 9 subattività, 8 di un'ora e una di due ore per i compiti in classe. E magari vorrei anche che le 9 subattività fossero spalmate nella settimana introducendo un vincolo sui giorni minimi delle subattività. Beh, se mettete a questo vincolo il 100% di peso, cioè imponete che debba essere rispettato senza se e senza ma, il software ci dirà che abbiamo sbagliato ad inserire i dati. Perché? Se la settimana dura cinque giorni come posso suddividere un'attività in 8 giorni distinti? Certo, potrei anche mettere un peso non del 100%, magari 95%. Forse funzionerebbe, ma è sconsigliato lo stesso, fareste lavorare l'algoritmo per cercare una soluzione che non può esistere; alla fine rinuncerebbe a soddisfare il vincolo, ma dopo tanti, tanti, tanti calcoli inutili. Io faccio così, suddivido le ore di italiano in due attività, una da 5 subattività (con 4 subattività da un'ora e una da due ore) e un'altra attività da 4 subattività da un'ora. In tutto 10 ore. Le subattività delle singole attività le vincolo ad essere in giorni distinti, ma nulla vieta che una subattività della seconda attività capiti nello stesso giorno di una subattività della prima. Non so se è la soluzione migliore, ma è la mia.

In linea di principio potrei anche definire attività senza studenti, o senza professori. Per esempio è quello che in questo caso faccio con le Disponibilità: sono attività che alcuni docenti devono svolgere ma che non coinvolgono alcun gruppo di studenti.

Ora è anche possibile comprendere perché alcune righe della lista delle attività hanno un rientro: per distinguere fra loro le varie attività dalle varie subattività si è deciso che solo la prima subattività di un'attività è incolonnata a sinistra, tutte le altre hanno un piccolo rientro.

Dalla lista delle attività, se si clicca su Modifica, è possibile modificare l'attività precedentemente inserita e selezionata in quel momento. Si apre la seguente finestra:

molto simile a quella che permette di aggiungere le attività. L'unico dato che non può essere modificato è il numero di subattività nei quali è suddivisa l'attività. Per modificare quello l'attività va eliminata e ricreata ex novo. Per eliminare un'attività è sufficiente cliccare su elimina dalla finestra Lista delle attività: l'attività corrente (cioè selezionata nella colonna di sinistra) verrà eliminata.

Per concludere l'articolo vediamo che succede se si clicca su subattività dalla scheda Dati. Si apre la seguente finiestra:

dalla quale è possibile selezionare e modificare una singola subattività. Se si clicca su modifica si apre la seguente finestra:

dalla quale è possibile modificare alcune caratteristiche della singola subattività. Non può essere eliminata ma può essere disattivata, in questo caso FET non cercherà di allocarla durante la generazione dell'orario.

Concluderei con una cosa che avevo già descritto nell'articolo precedente: se dalla scheda Dati si clicca su Avanzate e poi su Statistica attività è possibile fare un riepilogo di tutte le ore e le attività assegnate, o meglio, impostate come dati. Perché ovviamente ancora nulla è stato assegnato, per ora stiamo ancora inserendo i dati. Ovviamente durata e numero delle attività non sempre coincidono perché alcune attività potrebbero durare più di un'ora.



LEGGI TUTTO...

mercoledì 7 luglio 2010

Come farai l'orario scolastico?

Se ti va di discutere su questo argomento lascia un commento.



LEGGI TUTTO...

Risultato del sondaggio: pensate che le LIM, Lavagne Interattive Multimediali, siano veramente utili?

Direi che la maggioranza ritiene che le LIM siano utili solo se installate in classe e se usate ogni giorno.

Non posso che essere d'accordo!!!


Che ne pensate? Come? Non vi tornano le percentuali? Chiedete a googlo come calcola i risultati dei sondaggi!!!

LEGGI TUTTO...

giovedì 1 luglio 2010

L'orario scolastico - FET: un esempio, l'inserimento dei dati principali

Per spiegare meglio il funzionamento di FET ho preparato un esempio scaricabile cliccando sul seguente link:
La versione di FET che ho usato è stata la 5.13.3, quindi l'esempio funzionerà sicuramente con quella e con tutte le successive.
E' mia intenzione nei prossimi articoli descrivere passo passo quello che ho fatto. In questo articolo indicherò come inserire i dati principali.

L'esempio, del tutto inventato, si riferisce ad una scuola media di tre sezioni su due sedi (A e B in Centrale, C in Succursale). Le lezioni si svolgono cinque giorni a settimana, sei ore al giorno, per un totale di 30 ore settimanali. Il piano di studi è relativo alla struttura in vigore fino al 2009. Sono presenti due ore di copresenza per ogni classe, e alcuni professori di lettere hanno tre ore settimanali di disponibilità.

Nella figura seguente potete vedere la schermata principale di FET. E' suddivisa in un menù superiore e in una serie di schede. Nell'immagine è selezionata la scheda File, dalla quale è possibile salvare il file con i dati inseriti o caricarne uno già creato. I dati sono salvati in formato xml, da File nella barra del menù è, inoltre, possibile esportare ed importare il file dati in formato testo scegliendo il separatore tra i dati, in questo modo è anche possibile importare i dati in Microsoft Excel.


In questo articolo analizzeremo la scheda Dati, grazie alla quale è possibile inserire i dati principali del nostro problema. I vincoli verranno invece inseriti nelle schede Tempo e Spazio


Se si clicca su Base compare un menù grazie al quale possiamo inserire il nome della scuola, alcuni commenti, il numero di giorni a settimana e le ore giornaliere. Possono essere immaginati orari su più settimane. Se i giorni non sono tutti sulle stesse ore, basterà inserire dei vincoli nelle apposite schede per specificare in quel determinato giorno quando si fa lezione.



Cliccando su Insegnati è possibile aggiungere/rimuovere/modificare gli insegnanti. L'esempio è stato immaginato con insegnanti che completano l'orario in altre scuole, o che hanno un orario parziale. Non ho usato nomi, bensì un codice che mi indica la materia insegnata e le classi/sezioni nelle quali il professore insegna. Ar (A-B-C) è il professore di Arte delle sezioni A, B, C. EF sta per Educazione Fisica, In per Inglese, Le per Lettere, Ma per Matematica, Mu per Musica, Re per Religione, Sp per Spagnolo, Te per Tecnologia. I professori di lettere sono di due tipi: Le (1x-2x) e Le (1x - 3x). I primi fanno 7 ore (cioè Italiano) in prima e 11 in seconda. Gli altri fanno 4 ore (Storia e Geografia) in prima, 11 in terza e hanno 3 ore di disponibilità.

Per comprendere il significato di Abilita/Disabilita tutte le attività legate all'insegnante selezionato è necessario introdurre il concetto di attività. Le attività possono essere viste come le lezioni che devono essere svolte, sono le entità che il software deve piazzare. Delle attività parlerò in uno dei prossimi articoli. In pratica questi due pulsanti permettono di trascurare tutte le attività legate a quel docente.

La finestra è formata da due colonne, in quella di destra è riportato l'elenco dei docenti, in quella di sinistra tutti i vincoli assegnati. Vedremo come aggiungere i vincoli in un altro articolo, nel file dati sono comunque già presenti.


Se dalla scheda Dati si clicca su Avanzate e poi su Statistica insegnanti è possibile vedere quante attività e quante ore fanno tutti i docenti. Appare subito chiaro quali sono i docenti che non fanno 18 ore nella scuola. Questi dati vengono aggiornati mano a mano che vengono inserite le attività. Dato che un'attività può anche durare due ore (magari per i compiti in classe) le due colonne non sempre coincidono.

Le statistiche aiutano anche nella ricerca di eventuali errori di inserimento.


Se dalla scheda Dati si clicca su Studenti è possibile inserire il numero di anni (ho messo 3 anni perché è una scuola media), il numero di gruppi per anni (ho messo le 3 sezioni), eventuali sottogruppi per classe (ad esempio ragazzi e ragazze). E' possibile anche inserire il numero di studenti o far generare le sezioni alla finestra Anni, ma io preferisco inserire questi dati manualmente. Il numero di alunni può essere utile se si devono gestire aule o attività con un numero massimo di studenti ammissibili. A me non è mai capitato.



Se dalla scheda Dati si clicca su Avanzate e poi su Statistica studenti è possibile vedere numero delle attività e durata totale delle lezioni settimanali per ogni gruppo di studenti. Utile per ricontrollare di non aver commesso errore.


Se dalla scheda Dati si clicca su Materie si apre una finestra che permette la  gestione delle materie. Le ricapitolo aggiungendo come informazione il numero di ore settimanali. Questo dato viene inserito collateralmente all'inserimento delle attività.

Ar: Arte, 2 ore
EF: Educazione Fisica, 2 ore
In: Inglese, 3 ore
It: Italiano, nelle prime, 7 ore
Le: Lettere, solo nelle seconde e nelle terze, 10 ore
Ma: Matematica e Scienze, 5 ore
Mu: Musica, nelle prime 2 ore, nelle seconde e nelle terze un'ora
Re: Religione, un'ora
SG: Storia e Geografia, nelle prime, 4 ore
Sp: Spagnolo, 2 ore
Te: Tecnologia, 2 ore
Ma/Te: Copresenza Matematica - Tecnologia, un'ora
Le/Mu: Copresenza Lettere - Musica, nelle seconde e nelle terze, un'ora
It/Ge: Copresenza Italiano - Geografia, nelle prime, un'ora
Dis: Disponibilità (lo so, non è una materia, ma mi serve per assegnarla ai docenti che ce l'hanno)


Se dalla scheda Dati si clicca su Avanzate e poi su Statistica attività è possibile fare un riepilogo di tutte le ore e le attività assegnate.



Se dalla scheda Dati si clicca su Spazio è possibile definire gli Edifici, in questo caso Centrale e Succursale, e le Aule.



Per quanto riguarda le aule è possibile inserire la capienza massima. Io ho creato un aula per ogni gruppo di studenti, con lo stesso nome. In pratica esiste un gruppo 1A di studenti e un'aula 1A, poi vincolerò gli studenti a fare quasi tutte le lezioni in quell'aula. Le aule possono avere nomi diversi dai gruppi di studenti e gli studenti possono anche spostarsi da un aula all'altra. FET è molto flessibile, funziona con la scuola italiana, ma anche con scuole di altri paesi e università. Per ogni aula devo anche indicare l'Edificio.

Ho definito anche le palestre PC1, PC2 e PS. Le prime due sono in centrale, la terza in succursale. Educazione Fisica sarà vincolata ad essere svolta in palestra. Definire due palestre in centrale, oltre ad essere una possibilità, quella scuola ha due palestre effettivamente, è un trucco per poter permettere a due gruppi di studenti di usare contemporaneamente la palestra. Con così poche classi non era necessario, ma per scuole molto grandi definire più palestre virtuali permette a più gruppi di studenti di usare la risorsa contemporaneamente.
Infine ho definito anche SPC e SPS, la sala professori in Centrale e Succursale, nelle quali farò svolgere le disponibilità. E' chiaro che i professori non saranno obbligati a stare nella sala professori, ma a me serviva definire un luogo dove mettere i professori durante queste ore.


A conclusione vorrei aggiungere che queste sono state le mie scelte, ma che magari era possibile fare anche scelte differenti. Se avreste operato scelte diverse condividetele, se volete, con un commento.

Per maggiori informazioni su FET:

Post Scrittum del giorno dopo.
Rileggendo l'articolo mi rendo conto di aver saltato nella scheda Dati i tre pulsanti Chiavi, Attività e Subattività. Di questi ultimi due ho già detto che parlerò in uno dei prossimi articoli. Invece Chiavi me lo sono proprio dimenticato. Il motivo è semplice, non l'ho mai usato. Se ci cliccate sopra si apre una finestra simile a quella che si apre cliccando su Materie. Le Chiavi sono informazioni aggiuntive e opzionali che possono essere utilizzate per caratterizzate delle attività. Citando dal sito di Marco Barsotti (http://ilpassodellupo.it.gg/):

Sono chiavi della materia, ad esempio, l'esercitazione, la lettura, il laboratorio, la teoria, la pratica ecc. Se una attività deve iniziare alla prima, terza o quinta ora, la proprietà dell'attività può definirsi dispari. Se una attività deve essere svolta di mattina piuttosto che di pomeriggio, la proprietà relativa potrebbe dirsi mattino.
L'uso di queste chiavi (proprietà o caratteristiche) dell'attività è strettamente legato ai vincoli, alla loro definizione e in particolare all'uso degli orari preferenziali.

LEGGI TUTTO...

venerdì 18 giugno 2010

L'orario scolastico - FET: Free Timetabling Software, un programma molto efficiente per trovare l'orario

Ho parlato tanto dell'orario scolastico, ma ancora non ho detto nulla su come fare a trovarlo. E' ora di cominciare ad affrontare questo problema.

Cominciamo col dire che io non lo faccio a mano, bensì uso un software. Mi piacerebbe saperlo fare a mano, ma quando mi hanno proposto la prima volta di fare un orario scolastico non sapevo da che parte iniziare, e la prima cosa che ho pensato è stata quella di cercare qualche software gratuito che potesse aiutarmi.

E l'ho trovato.

Il software si chiama FET: Free Timetabling Software. L'autore si chiama Liviu Lalescu, e cliccando sul seguente collegamento potete accedere alla pagina web del programma: http://lalescu.ro/liviu/fet/.

Come vedete la pagina è in inglese. Niente paura, il software è stato tradotto in italiano da Marco Barsotti, che gestisce anche un sito in italiano dedicato a FET: http://ilpassodellupo.it.gg/

Un software per fare l'orario deve avere due caratteristiche:
  1. un sistema efficiente per inserire le migliaia di vincoli necessari
  2. un buon algoritmo per la ricerca della soluzione
Direi che FET ha entrambe questa caratteristiche.
L'interfaccia è semplice e potente, permette con pochi click di inserire intere serie di vincoli e ll programma usa un algoritmo euristico, basato sullo scambio ricorsivo di attività per fare spazio a nuove attività.

FET ha varie caratteristiche che trovo molto interessanti:
  • E' gratuito ed è distribuito secondo i termini della licenza GNU GPL
  • E' multipiattaforma, per Windows viene fornito già compilato, per linux e Mac deve essere compilato
  • La generazione dell'orario può essere fatta in modo completamente automatico, ma è possibile anche piazzare attività manualmente
  • Permette di visualizzare l'orario durante la generazione
  • Permette, dopo aver trovato un orario, di sbloccare aolo alcune attività per cercare di piazzarle in modo più ottimale o secondo nuovi vincoli
  • Permette di inserire una quantità notevole di vincoli
  • E' in continua evoluzione: con scadenze ravvicinate escono nuove versioni, compatibili con le precedenti, ma che permettono di aggiungere nuove tipologie di vincoli
  • Contattando l'autore è possibile chiedere/consigliare nuova caratteristiche per il programma
  • Si può imporre quanto deve essere soddisfatto un vincolo, se al 100% oppure se può essere rilassato.
Non riporto qui tutti i vincoli supportati da FET, anche perché come ho detto se ne aggiungono sempre di nuovi. Per tutte le info ricordate questi due siti:
Nei prossimi articoli metterò un po' di screenshot e scriverò qualcosa su come si usa.

Qualcuno di voi già conosceva FET? Lo avete mai usato?

LEGGI TUTTO...

giovedì 10 giugno 2010

Dal sito della BBC

Se in Italia si stanno muovendo i primi passi nella produzione di learning objects e di giochi didattici, nell'ambito anglosassone si è già iniziato da qualche anno, e sono già a disposizione tutta una serie di interessanti CDD - Contenuti Didattici Digitali. Unico limite, che poi un limite non è, è necessaria una discreta conoscenza della lingua inglese.


Qualche tempo fa stavo cercando qualche gioco didattico sulle trasformazioni e mi sono imbattuto nell'oggetto che ho incorporato qui sopra. Mi sembrava ben fatto e ho deciso di esplorare un po' il sito. Con mia sorpresa ho scoperto che si trattava del sito della BBC (http://www.bbc.co.uk/)

Se cliccate su more e poi su Learning si accede alla sezione dedicata all'apprendimento: http://www.bbc.co.uk/learning/

Da qui è possibile accedere a tutta una serie di categorie:
Fermo restando che mi sembrano tutte interessanti e degne almeno di un'esplorazione (in Languages potete anche trovare un corso di italiano in inglese), io mi sono concentrato soprattutto sulla prima: Bitesize (http://www.bbc.co.uk/schools/bitesize/).

Anche in questo caso avete a disposizione varie categorie: KS1 (per bambini dai 5 ai 7 anni), KS2 (8-11 anni), KS3 (11-14 anni) e GCSE (14-17 anni). E non mancano altre categorie per gli ordini di studi delle varie nazioni che compongono il regno unito.

E per ogni categoria trovate varie materie, scientifiche e letterarie, lezioni, esercizi, test. Veramente tantissimo materiale. Complimenti. Mi sa che veramente noi italiani siamo un "po'" indietro.

Ora vi chiedo un aiutino. Cerco, quando possibile di essere preciso e di non scrivere castronerie, anzi, se l'ho fatto perdonatemi e correggetemi. Quindi cerco sempre di documentarmi un po'. Cosa vuol dire KS1, KS2... con un po' di impegno l'ho più o meno capito. Ma c'è una cosa che proprio non sono riuscito ad interpretare: cliccando su Bitesize TGAU (http://www.bbc.co.uk/cymru/tgau/) si finisce su una pagina di risorse didattiche per me incomprensibile. Con buona probabilità è tipo Gallese... ma proprio perché l'unica parola che ho compreso e Wales. Qualcuno può confermare questa mia ipotesi. Grazieeee!!!

LEGGI TUTTO...

lunedì 7 giugno 2010

L'orario scolastico - Un problema intelligente adatto all'intelligenza

Che titolo per un articolo!?!?
Il primo anno che ho fatto l'orario in una scuola tutti mi dicevano che non poteva esistere un software per trovare un buon orario scolastico, che non poteva esistere un software che tenesse conto di tutti i vincoli, che non poteva esistere un software che ragionasse come un essere umano e che tenesse conto di tutti i fattori in gioco. Beh, dopo un po' di anni ho scoperto che non avevano così tanto torto.

Però prima di continuare sgombriamo il campo da dubbi: io uso un software per trovare l'orario scolastico, a mano non saprei da che parte iniziare e, soprattutto, mi farebbe impazzire l'idea che qualche specifica o qualche vincoli cambi all'ultimo minuto - e capita, ve l'assicuro - così da obbligarmi a rifare parte o tutto l'orario il giorno prima dell'inizio dell'anno scolastico.

D'altra parte, prima di scrivere questi articoli, ed in particolare proprio questo, mi sono voluto un po' documentare. Abbiamo già detto che il problema della ricerca di un orario scolastico è un problema che appartiene alla classe dei problemi detti Problemi di Soddisfacimento di Vincoli o CSP

Purtroppo non esiste una tecnica che dato questo tipo di problemi trova una soluzione tramite un calcolo più o meno complicato. Esistono, viceversa, algoritmi ricorsivi per la ricerca della soluzione. Uno di questi è ad esempio l'algoritmo Backtracking. Si cominciano ad assegnare le variabili in gioco in modo più o meno casuale (oppure seguendo euristiche di qualche genere) in modo tale che rispettino tutti i vincoli finché non si arriva ad una variabile che non si riesce ad assegnare, perché a prescindere da quale valore le diamo un vincolo non viene soddisfatto. Allora si va all'ultima variabile assegnata e che non ha infranto vincoli e le si dà un altro valore sempre con la condizione che rispetti i vincoli e si continua la ricerca. Le scelte vengono immagazzinate in un albero che tiene conto di tutte le opzioni visitate.

Per come è fatto l'algoritmo è però possibile imboccare vie sbagliate che obbligano a risalire l'albero anche più volte. Per esempio se la prima variabile che si assegna la si assegna in modo tale che non esiste alcuna soluzione con quel valore (e io a priori non lo posso sapere) l'algoritmo dovrà fare molte esplorazioni e ricorsioni prima di arrivare alla conclusione che quell'assegnazione è sbagliata. So di non essere precisissimo, però come più volte ho accennato l'obiettivo di questi miei articoli è di far comprendere appieno le problematiche.

E qui il problema è grande: gli algoritmi che permettono di trovare l'orario scolastico sono ricorsivi, cioè devono fare tanti tentativi prima di trovare una soluzione ed il numero di tentativi cresce in modo esponenziale al crescere dei vincoli.

Ho trovato un esempio per farsi un'idea di quanto tempo potrebbe volerci per trovare un orario scolastico (http://it.wikibooks.org/wiki/Costruire_un_orario_scolastico):
Supponiamo di avere una scuola con 40 classi, e con 30 ore settimanali ciascuna, un programma per generare l’orario scolastico attraverso una tecnica ricorsiva dovrebbe esaminare ogni disposizione di 30 ore su 40 classi e su un buon comupter ci metterebbe circa 1000000000000000000000000000000000000000000 anni!!!

Ed eccoci arrivati alla conclusione da cui scaturisce il titolo dell'articolo: è dimostrato che le tecniche informatiche migliori per affrontare questo tipo di problemi sono tecniche che richiedono l'impiego dell'intelligenza artificiale, cioè tecniche che emulano le capacità di ragionamento e di sintesi del cervello umano.

Un po' di link per approfondire:
http://it.wikibooks.org/wiki/Costruire_un_orario_scolastico
http://it.wikipedia.org/wiki/Backtracking

LEGGI TUTTO...

giovedì 27 maggio 2010

L'orario scolastico - Tutti i vincoli hanno la stessa importanza?

Dopo aver formulato il problema, sia a parole, sia eventualmente matematicamente, ci si deve porre una questione fondamentale: tutti i vincoli sono uguali? Ce ne è qualcuno più importante?

La risposta è sì, ma non sta a me rispondere a quali siano quelli più importanti. Certo è che alcuni vincoli devono essere soddisfatti, se non lo sono viene un orario incoerente, sbagliato o inaccettabile. Un professore non può fare due lezioni contemporaneamente, e nemmeno possiamo fargli fare 3 giorni da 6 ore e poi a casa. Insomma, esistono tutta una serie di vincoli che il buon senso e il dirigente scolastico ci dicono che devono essere soddisfatti.

Qualche volta, però, ci viene detto: "beh, vedi se riesci a fare una determinata cosa," che per chi fa l'orario vuol dire "vedi se riesci ad imporre un certo vincolo, altrimenti va bene lo stesso."

Potremmo aggiungere anche questo alla lista dei nostri vincoli che devono essere soddisfatti, ma come ho già detto qualche articolo fa, aggiungi di qua, aggiungi di là... alla fine potrebbe non esistere più una soluzione possibile.

Oppure a prescindere, il dirigente scolastico ci dà un insieme di vincoli, ma dopo ore e ore di lavoro non si riesce a trovare un orario. Magari non esiste proprio un orario ammissibile. In questo caso siamo noi a dover andare dal dirigente scolastico e dirgli: "non è possibile rispettare tutti i vincoli dati."

Sia che sia il preside a dirvi di vedere se riuscite ad imporre un determinato vincolo, sia che siate voi a convincerlo che non tutti i vincoli sono soddisfacibili, quello che dovete fare si chiama in gergo rilassare un vincolo.

In pratica avrete una serie di vincoli obbligatori che dovete rispettare, ed un'altra serie di vincoli (detti appunto rilassati) che potete anche non soddisfare.

La prima scelta possibile per affrontare i vincoli rilassati è prima provare ad imporli e poi, se non si trova un orario, eleminarli. Certo, così facendo sicuramente non li imporrete nemmeno un pochino. Ora, cosa vuol dire imporre un pochino un vincolo è un concetto che potrebbe far rizzare i capelli ad un matematico, ma per noi vuol dire che se non riusciamo ad imporlo al 100% magari riusciamo ad imporlo al 75%.

Un esempio. Il dirigente magari ci chiede di far in modo che alle prime ore gli studenti abbiano matematica perché più pesante. Imporre il vincolo vorrebbe dire forzare questo eventi, eliminare il vincolo vorrebbe dire non provarci proprio, cercare di imporlo in forma rilassata vuol dire che magari in tre giorni su sei ci riusciamo.

Come si fa a rilassare un vincolo dipende dalla tecnica di risoluzione che si sceglie per l'orario. Se lo si fa a mano vorrà dire che si deciderà se soddisfarlo o meno quando il problema si porrà. Se si usa un software bisogna vedere se il software mette a disposizione sistemi per rilassare vincoli e non imporli al 100%. E sicuramente sarà così, altrimenti non è un buon software.

Dal punto di vista matematico quello che si può fare è introdurre una funzione obiettivo nella quale in qualche modo facciamo rientrare i vincoli che abbiamo rilassato. Questa funzione, ad esempio, può essere tale che il suo valore è tanto più grande quanto più ci allontaniamo dai vincoli. Se poi introduciamo dei pesi possiamo fare in modo che allontanarsi da certi vincoli generi un valore più grande che allontanarsi da altri. A questo punto il problema si trasforma in un problema di Ricerca Operativa e di ottimizzazione: va cercata la soluzione che soddisfa i vincoli obbligatori e che minimizza la funzione obiettivo, cioè che si discosta meno dai vincoli rilassati.

Clicca su questo collegamento per saperne di più sulla Ricerca Operativa.

LEGGI TUTTO...

mercoledì 26 maggio 2010

L'orario scolastico - La formulazione matematica

Ora la questione si fa complicata. Ci tengo però a precisare che per fare un orario scolastico non serve necessariamente sapere quello che vi sto per raccontare, d'altra parte penso che chiunque affronti un problema possa chiedersi  la natura del problema e se è noto e studiato in letteratura.

Il problema della redazione dell'orario scolastico appartiene alla classe dei Problemi di Soddisfacimento di Vincoli (Constraint Satisfaction Problem o CSP).

Darò dei piccoli spunti per capire come può essere formulato matematicamente. Vi ricordo che il mio obiettivo è far capire ciò di cui stiamo parlando, non scrivere un manuale scientifico.

Il problema è un problema decisionale, nel quale le variabili possono assumere valere 0 o 1.

Innanzitutto quali sono le variabili. Definiamo con I l'insieme dei professori, J l'insieme delle classi, K l'insieme delle ore giornaliere, L l'insieme dei giorni della settimana, ed associamo ad ognuno di questi elementi un numero univoco nell'insieme.

I = {1,2, ... Ni}, con Ni il numero totale dei docenti
J = {1,2, ... Nj}, con Nj il numero totale delle classi
K = {1,2, ... Nk}, con Nk il numero totale delle ore giornaliere
L = {1,2, ... Nl}, con Nl il numero totale dei giorni

Quindi avremo il professore 1, il professore 2, il professore 3, fino al professore Ni

Avremo la classe 1, la classe 2, la classe 3, la classe 4, fino alla classe Nj

Possiamo quindi definire la variabile Xijkl che vale 1 se il professore i fa lezione nella classe j all'ora k del giorno l, 0 altrimenti.

Definite le variabili dobbiamo chiederci come trasformare in equazioni o disequazioni i vincoli che abbiamo espresso a parole. Lo farò solo per un vincolo, quello che mi interessa è mostrare il procedimento.

Prendiamo per esempio il numero massimo di ore giornaliere di un professore e supponiamo che questo sia uguale a Oi.

Si fissa i (il professore), si fissa l (il giorno della settimana) e il vincolo si ottiene sommando tutte le Xijkl con quei determinati valori di i e l e imponendo che questa somma sia minore o uguale a Oi. E  si fa questo per tutte le possibili combinazioni di i e l.

Tradotto in un linquaggio più semplice... preso un professore e preso un giorno della settimana, imponiamo che per quel professore e quel giorno della settimana al più Oi variabili possano essere uguali a 1, cioè che faccia al più Oi ore di lezione.

Questo funziona se c'è anche un altro vincolo che ci dice che fissata un ora, fissato un professore e fissato un giorno, la somma di tutte le relative variabili di decisioni deve essere minore o uguale ad 1, cioè se un professore fa lezione lo fa in una sola classe alla volta (e sì, dobbiamo dirgli anche quello).

Questo giochino può essere fatto in modo più o meno complicato per tutti i vincoli tenendo conto che esistono regole per trasformare in equazioni e disequazioni vincoli condizionali (del tipo se... allora...) e vincoli logici (ad esempio un vincolo che viene soddisfatto se sono soddisfatti contemporaneamente due condizioni, cioè un vincolo AND, o similmente un vincolo OR)

La formulazione matematica coincide quindi con l'introdurre delle variabili decisionali e con il trasformare tutti i vincoli in un immenso insieme di equazioni e disequazioni.

Non credo che nessuno approcci in questo modo al problema, ma questo è la sua formulazione rigorosa.

In uno dei prossimi articoli vedremo come si risolvono problemi del genere, ma già vi preannuncio che sono considerati problemi difficili.

Un riferimento sitografico:

LEGGI TUTTO...

lunedì 10 maggio 2010

Sussidi didattici per la scuola

SONO ENTUSIASTA!!!
E' stato amore a prima vista tra me e il sito Sussidi didattici per la scuola. Questo è l'indirizzo:

Qualche tempo fa stavo cercando dei learning object sulle frazioni, e per puro caso mi sono imbattuto in queste pagine web. Sulle frazioni ho trovato un interssantissimo oggetto in flash (http://digilander.libero.it/sussidi.didattici/matematica/frazionihtml/frazioni.html), ma è stato solo l'inizio della mia espolazione delle pagine di Sussidi didattici per la scuola.

Ho trovato un'inifinità di oggetti. che spaziano dalla matematica alla storia, passando per la geografia e, udite udite,  per l'analisi logica. Oggetti che possono aiutare nello studio individuale a casa, ma che possono anche essere utilizzati a scuola e in classe con o senza una Lavagna Interattiva Multimediale. Unico requisito: disporre di una connessione ad internet.

Sui vari argomenti sono presenti schede teoriche ed esercizi. Sul sito ci sono anche giochi didattici e due pacchetti chiamati VerificheMachine e Libri Parlanti, il primo per creare verifiche interattive a risposta chiusa, il secondo per creare presentazioni multimediali interattive.

Nel tempo cercherò di commentare e descrivere i vari oggetti presenti nel sito, per ora mi sono limitato a segnalarlo.

Penso sia doveroso riportare gli autori e i collaboratori di cotanto capolavoro. Dalla pagina http://digilander.libero.it/sussidi.didattici/collaboratori.html:
I lavori presenti nel sito http://digilander.libero.it/sussidi.didattici/, sotto i profili della progettazione e della realizzazione informatica, sono opera di Giuseppe Bettati, insegnante di scuola media. Altri insegnanti hanno collaborato, in vario modo, all'elaborazione di contenuti specifici:


Lalla Attolini
  • Materiale linguistico (Giocare con le parole: Cambi)
  • Clicca la risposta (vari questionari di Scienze)
  • Linea del tempo 1500-2000: Scienza e tecnica (testi e disegni)
  • Viaggio nell'Antico Egitto (partecipazione alle fasi di progettazione, contributo determinante alla grafica)
  • Divinità egizie (Lalla Attolini, G.B.)
  • Le Grandi navigazioni oceaniche (partecipazione alle fasi di ideazione, contributo determinante alla grafica)
  • Via della seta (Lalla Attolini, G.B., A. P.)
  • Produzione di "libri" (Libri Parlanti on line)
  • Consulenza per quanto riguarda i programmi di Matematica e Geometria
Cristina Brighenti
  • Materiale linguistico (alcune esercitazioni di analisi logica e grammaticale)
Cristina Cavalca, Paola Guareschi
  • Materiale linguistico (alcune esercitazioni di analisi grammaticale)
Daniele De Stefano
  • Con i suoi alunni: Giochi di giovani programmatori (Scuola media di San Pietro al Natisone, Cividale, UD)
  • Linea del tempo 1900-1945 (G. B., Daniele De Stefano)
Elisabetta Mangi
  • Materiale linguistico (esercitazione di analisi logica)
Antonella Pulvirenti
  • Materiale linguistico (esercitazione di analisi grammaticale, rebus)
  • Le Grandi Navigazioni Oceaniche (partecipazione alle fasi di ideazione e di elaborazione grafica e testuale)
  • Via della seta (L. A., G. B., Antonella Pulvirenti)
  • Preziosa collaborazione per quanto riguarda i programmi verficheMachine e Libri Parlanti
  • Produzione di "libri" (Libri parlanti online)
Ivana Sacchi
  • Viaggio nell'Antico Egitto (partecipazione alle fasi di progettazione)
  • Le Grandi Navigazioni Oceaniche (partecipazione alle fasi di ideazione e di elaborazione grafica e testuale)

Insomma, un sito che mi ha subito conquistato per la sua accuratezza e per la sua ricchezza dei contenuti. Voi che ne pensate?

LEGGI TUTTO...