Le scale pentatoniche

Se, un giorno, una parsona si mettesse a chiedere in giro: "Dimmi la prima scala musicale che ti viene in mente", molto probabilmente la risposta iù comune risulterà: "Do-Re-Mi-Fa-Sol-La-Si" ovvero la scala maggiore di Do.
é chiaro che questa è solo una delle tante scale musicali che si differenziano per gli intervalli che sussistono tra le note, la nota "di partenza" e anche dal numero di note. Esistono alcune scale, ad esempio, che hanno sette note, come la scala maggiore,  altre che ne hanno sei, come le scale blues, o altre ancora che ne hanno cinque, come le pentatoniche.
Una scala pentatonica è composta da cinque note. Nel caso della scala pentatonica maggiore, le note corrispondono alle note 1,2,3,5 e 6 della scala maggiori. Così, se la scala di Do maggiore é:
Do-Re-Mi-Fa-Sol-La-Si
allora la corrispondente pentatonica maggiore sarà:
Do-Re-Mi-Sol-La

In linea di massima nell'improvvisazione jazz e non solo, le scale pentatoniche maggiormente sfruttate sono quelle minori; per costruirle partiamo però dalle scale pentatoniche maggiori. Si consideri ad esempio la scala pentatonica maggiore di Mi (giusto per variare un po'): Mi-Fa#-Sol#-Si-Do#. Mantenendo le stesse note, ma partendo dalla sesta (nella scala maggiore), ovvero Do#-Mi-Fa#-Sol#-Si, otteniamo la scala pentatonica minore di Do.
In modo analogo si procede con le altre: i passo per "costruire" una scala pentatonica minore sono, quindi:

• capire la nota in questione di quale scala maggiore è sesta;
• si considera la scala maggiore trovata e si eliminano il IV e il VII grado (ovvero la quarta e la settima nota), ottenendo così la scala pentatonica maggiore;
• la scala pentatonica minore che si cercava usa le note della pentatonica maggiore trovata, partendo però dal VI grado (ovvero la nota di partenza della scala pentatonica minore).
  

Pdfnup: più pagine per foglio in un PDF

Chi stampa documenti in formato PDF aspira spesso a mettere sulla medesima facciata due o più pagine. I fogli sprecati e l'ingombro si riducono. Risulta spesso comodo creare un nuovo file PDF, con le pagine posizionate dove ognuno vuole, per poi poterlo portare in copisteria e non sperare che l'addetto alla stampa ottenga l'esatto risultato che si voleva.
I metodi per arrivare a stampare più pagine per foglio sono numerosi in particolare mi sono sempre trovato bene la funzione stampa su file offerta da ubuntu per tutti i file stampabili, oppure è comoda la stampante CUPS-pdf installabile tramite il fantastico gestore di pacchetti o il comando apt-get.
La faccenda si complica quando i files da modificare erano qualche decina. Il procedimento per usare la stampa su file è semplice, ma troppo lungo e ripetitivo se i files sono più di due o tre.
Siccome il comuter è tanto stupido - l'intelligenza artificiale non è un ossimoro, ma siamo noi umani che creiamo qualcosa che appare intelligente, non è l'agente di per se ad essere intelligente - dicevamo, il computer è tanto stupido, ma anche molto veloce, non è logico annoiarsi a fare sempre le stesse cose.
Curiosando sulla rete, allora, ho trovato un piccolo programmino utile proprio in queste situazioni: pdfnup. Questo fa parte di un insieme di programmi che va sotto il nome di pdfjam: tutti utilizzano pdfLatex per svolgere svariate operazioni con i pdf (vedere http://www2.warwick.ac.uk/fac/sci/statistics/staff/academic/firth/software/pdfjam).

Installazione
Per installare pdfnup bisogna installare il pacchetto pdfjam tramite il gestore di pacchetti o scrivendo a terminale (con Ubuntu):

sudo apt-get install pdfjam

e digitando in seguito la propria password.

Utilizzo
L'interazione con pdfnup avviene da terminale, ma questo non deve spaventare nessuno dato che i comandi da digitare sono davvero semplici. Se ad esempio, fossimo l'utente "nome_utente", e avessimo sulla scrivania (/home/nome_utente/Scrivania) una cartella "cartella_documenti" contenente i documenti pdf da usare come sorgenti per creare i nuovi pdf con più pagine per foglio, allora digiteremo il comando:

cd /home/nome_utente/Scrivania/cartella_documenti

per spostarci nella cartella con i documenti; successivamente usiamo il comando

pdfnup nome_file.pdf --nup 2x2

per creare un file nome_file-2x2.pdf che conterrà le pagine di nome_file.pdf disposte 2x2 per ogni foglio.

se invece volessimo modificare tutti i files della cartella si devono digitare i comandi.

cd /home/nome_utente/Scrivania/

pdfnup *.pdf --nup 2x2

per vedere le altre opzioni disponibili per usare il programma basta digitare:
pdfunp --help
e scorrere la guida con le frecce direzionali. Una volta conclusa la consultazione basta premere "q" per tornare al terminale.

Agenti risolutori di problemi: eliminazione degli stati ripetuti

Le strategie di ricerca presentate scelgono un nodo da espandere nella frontiera, senza tener conto di quelli espansi in precedenza. Quando l'algoritmo espande un nodo corrispondente ad uno stato A, potrebbe capitare che un nodo corrispondente al medesimo stato sia stato già espanso nell'albero di ricerca. In un caso di questo tipo risulta ridondante espandere il nodo corrispondente allo stato A poichè non porterebbe nessuna informazione aggiuntiva, e se tramite questo nodo si riesce ad arrivare alla soluzione, ci si arriva ugualmente tramite il nodo già espanso.
Risulta quindi opportuno modificare l'algoritmo di ricerca in modo che tenga conto degli stati visitati e non espanda più di un nodo corrispondente al medesimo stato. Si può creare una lista di questi stati; essa va sotto il nome di lista chiusa; prima di espandere un nodo viene controllato che lo stato a cui corrisponde non sia presente nella lista.
Ogni strategia di ricerca vista ha un suo corrispondente algoritmo con eliminazione degli stati ripetuti.

Agenti risolutori di problemi: ricerca informata

Un agente che ricerca una soluzione nell'albero di ricerca, non è detto che debba limitarsi a considerare i dati del problema; in astratto, può infatti valutare quanto è promettente un nodo e basarsi anche su questa informazione per scegliere i nodi da estrarre ed espandere nella frontiera. Le strategia di ricerca che utilizzano questa logica si chiamano informate o euristiche: in generale, viene valutata la "bontà" di un nodo tramite una funzione f(n) detta funzione di valutazione.

Ricerca greedy best-first
Questa ricerca espande sempre il nodo che è più vicino all'obiettivo, ipotizzando che in questo modo è probabile arrivare rapidamente ad una soluzione. Analiticamente si dice che f(n) = h(n), dove h(n) è una funzione, solitamente definita sullo stato corrispondente al nodo, detta euristica; la funzione euristica stima il costo per arrivare da n al nodo di goal. L'algoritmo sceglie dalla frontiera il nodo con la f(n) inferiore. La ricerca non è completa nei casi in cui espando stati già visitati, dato che possono continuare ad essere espansi nodi corrispondenti allo stesso gruppo di  stati; non considerando i  nodi i cui stati sono già stati espansi (vedere eliminazione stati ripetuti), la ricerca risulta completa ma non ottima. Le complessità temporale e spaziale sono  O(b^m).

Ricerca A*
La ricerca A*, a differenza di quella greedy, tiene conto del costo complessivo del cammino per arrivare dal nodo di partenza a quello di goal. Quanto detto si traduce in una funzione di valutazione f(n) = g(n)+h(n), dove g(n) è il costo di cammino del nodo n e h(n) è la funzione euristica vista per la ricerca greedy. Questa ricerca è molto importante e come tale merita di essere analizzata più in profondità di quanto fatto con gli altri metodi di ricerca visti finora.

Agenti risolutori di problemi: ricerca non informata

Si è visto che l'aspetto fondamentale per risolvere i problemi tramite l'albero di ricerca, consiste nella ricerca del nodo da espandere nella frontiera dell'albero stesso. Questa può essere effettuata utilizzando solo le informazioni contenute nella formulazione del problema (ricerca non informata) oppure tramite l'utilizzo di altre informazioni (ricerca informata).
Si illustrano ora alcune metodologie di ricerca non informata, mettendo in luce le caratteristiche di prestazione.

Ricerca in ampiezza.
In base a questo metodo si sceglie sempre il nodo meno profondo; ciò corrisponde a trattare la frontiera come una "coda" ovvero una insieme ordinato dal quale si preleva il primo elemento aggiunto (si parla di logica FIFO: First In First Out). Considerando l'albero, verranno espansi i nodi per livelli di profondità.
La ricerca in ampiezza è completa se il branching factor b non è infinito; non è ottimale dato che la ricerca non tiene conto dei costi dei cammini; ha complessità temporale e spaziale uguale poichè tutti i nodi analizzati devono rimanere comunque in memoria, e pari a O(b^(D+1)).

Ricerca a costo uniforme
La ricerca a costo uniforme sceglie dalla frontiera il nodo a minor costo di cammino. Questo garantisce ottimalità e completezza escludendo i casi in cui esistono costi di passo nulli;  la complessità temporale e spaziale dell'operazione sono uguali per un motivo analogo a prima, e sono pari a O(b^[C*/epsilon]) dove [C*/epsilon] corrisponde al valore intero maggiore e più vicino a C*/epsilon, che significa il numero di livelli che scendo nel caso peggiore (quando la soluzione è a livello epsilon).

Ricerca in profondità
A differenza dei due metodi visti, la ricerca in profondità tende a ricercare la soluzione esplorando l'albero appunto in profondità: viene scelto dalla frontiera il nodo a profondità maggiore. Si nota subito come questo tipo di ricerca potrebbe non terminare e quindi non è completa, dato che non garantisce che venga trovata una soluzione se esiste, e a maggior ragione non è ottima; la complessità temporale è O(b^m), mentre la complessità spaziale, in questo caso, è differente dato che i nodi appartenenti a cammini sondati fino in fondo possono essere eliminati dalla memoria ed è pari a O(bm).

Ricerca a profondità limitata
Un modo per far terminare il metodo di ricerca in profondità consiste nel fissare un valore naturale l e confrontare questo valore con la profondità dei nodi; i nodi che hanno profondità maggire di l non vengono espansi. Anche in questo caso la ricerca non è completa e la complessità temporale è O(b^l) mentre quella spazioale è O(bl).

Ricerca ad approfondimento iterativo
Affrontando il problema di ricerca con l'ultimo metodo visto, non è possibile raggiungere la soluzione se questa è situata a profondità maggiore del valore fissato l. Per ovviare a questo problema si può pensare dunque di provare ad aumentare il valore di l di una unità ogni volta che completiamo la ricerca con un fallimento. Quindi partendo con l=0 si procede cone nella ricerca a profondità limitata; se non viene raggiunto il nodo corrispondente allo stato di goal, si incrementa l di 1 e si continua questa procedura in modo iterativo fino a trovare il nodo corrispondente allo stato di goal. In questo modo, se la soluzione eseiste la troviamo, quindi è un algoritmo completo, ma non ottimo se i costi di passo non sono unitari, dato che non vengono considerati nella scelta del nodo da espandere. La complessità temporale risulta O(b^D) e quella spaziale O(bD).

Agenti risolutori di problemi: soluzione del problema

La fase successiva alla formulazione del problema è la ricerca della soluzione dello stesso. Per fare ciò si parte dallo spazio degli stati dal quale si costruisce l'albero di ricerca. Il procedimento è iterativo: si considera in prima istanza lo stato iniziale e si crea un nodo corrispondente, detto radice, si applica il test obiettivo al nodo in analisi, si espande il nodo se non soddisfa il test e si sceglie un altro nodo e si continua dall'applicazione del test obiettivo.
Un nodo è una struttura dati formata da cinque elementi:

• stato dello spazio degli stati a cui il nodo è associato, da notare che ad uno stesso stato possono corrispondere più nodi;
• puntatore al padre, ovvero al nodo da cui è stato generato; questo servirà per ricostruire a ritroso il cammino dal goal raggiunto fino allo stato iniziale;
• azione che porta al nodo;
• costo del cammino che porta dalla radice al nodo (questo compo si chiama g(n));
• profondità del nodo.

Per creare l'albero di ricerca è utile definire un insieme, che viene detto frontiera, dei nodi generati nell'albero stesso ma non ancora espansi. Il problema principale risulta allora ordinare l'insieme in modo che l'algoritmo di creazione dell'albero estrarrà ad ogni passo il nodo opportuno.

Agente come risolutore di problemi

Si considera inizialmente un agente che opera in ambiente statico, osservabile, discreto e deterministico. Esso deve massimizzare la sua misura di prestazione e questo viene reso più semplice se fissiamo un obiettivo da raggiungere, che consiste in un insieme di stati del mondo. L'agente allora dovrà ricercare una sequenza di stati, detti soluzione, che lo portino a soddisfare l'obiettivo. Per trovare la soluzione bisogna formulare in modo corretto il problema considerato dall'agente intelligente definendo:

• lo spazio degli stati il quale consiste in un grafo i cui nodi sono gli stati e gli archi sono le azioni. Lo spazion degli stati è a sua volta definito da:
• lo stato iniziale in cui si trova l'agente;
• la funzione successore: funzione che dato uno stato del problema, restituisce un insieme di coppie {, };
• il test obiettivo distingue gli stati di goal (o stati obiettivo) elencandoli esplicitamente o esprimendo una condizione che deve valere per tali stati;
• il costo di cammino: funzione che dato un cammino restituisce il costo associato, sommando il costo di passo relativo ad  ogni azione eseguita

 In questa ottica la soluzione è vista come un cammino dallo stato iniziale allo stato obiettivo, e la soluzione ottima è quella a costo di cammino minore.

Si nota come, la formulazione di un problema  è il risultato di un processo di astrazione tramite il quale vengono tralasciati dettagli non necessari per il raggiungimento dell'obiettivo. Più in generale un problema può essere descritto in modi differenti; per ottenere una buona formulazione si deve limitare il numero degli stati cercando di includere per quanto possibile, le regole dell'ambiente, nella funzione successore.