SaloonSoft

SaloonSoft si sposta!

2012-07-29T14:57:00.002-07:00

SaloonSoft entra a far parte di HackersTribe! Ancora per qualche giorno saranno disponibili articoli e informazioni sul nostro blog, ma a trasferimento completato sarà tutto su HackersTribe. Il motivo del trasferimento è semplice: l'unione fa la forza. Il sito hackerstribe è specializzato nel settore informatico (e tecnologico in generale) quindi è con grande piacere che faccio questo annuncio. Ovviamente tutta la nostra disponibilità e (si spera) simpatia la ritroverete lì, assieme ad altri collaboratori, altre notizie, altro codice, una community più ampia e tanto altro. Iniziate a farvi un giro su HackersTribe!

Tecniche di Programmazione : Backtracking

2012-05-30T02:26:00.002-07:00

In questo post ho cercato di scrivere quello che avevo capito di una delle tecniche di programmazione più usate, il backtracking, basandomi sugli appunti presi a lezione, informazioni sul web e alcuni libri di testo. Scusatemi per la formattazione, ma ho copiato e incollato da un documento di testo che avevo scritto e sono troppo pigro per riformattarlo a regola d'arte. Per qualsiasi suggerimento o altro lasciate un commento o contattateci!

Principio:

La tecnica del backtracking è, per certi versi, un’ottimizzazione della ricerca esaustiva (o brute force) che prova tutte le possibili soluzioni “sensate” di un problema. Proprio il termine “sensate” fa la differenza con la tecnica di brute force: il backtracking pone dei vincoli in ogni suo passo, così da far diminuire i tempi della brute force. Dunque il backtracking elimina le strade che nel loro stato presentano già una scorrettezza, mentre la brute force esamina ogni combinazione possibile e verifica la sua esattezza solo dopo aver generato la pseudo-soluzione. Questa tecnica intraprende una strada che sembra corretta, non appena si rende conto che la soluzione diventa scorretta, l'algoritmo smette di andare avanti e torna in uno stato precedente, quando la soluzione era ancora giusta. Per capire bene il funzionamento del backtracking si ci può riferire a un albero, visitato in profondità per arrivare alla soluzione, dove a ogni livello corrispondono X nodi interni che rappresentano i valori delle sotto soluzioni: se si arriva ad una foglia significa che si è trovata la soluzione; se, nell'andare avanti nei nodi, i vincoli imposti risultano violati o non si può più procedere, si ritorna al nodo padre per poter scegliere un altro figlio e quindi intraprendere una nuova strada. Il processo si blocca se si trova una soluzione o si provano tutte le strade disponibili senza arrivare alla soluzione.

Per poter applicare il backtracking si devono verificare delle condizioni:

Lo spazio delle soluzioni dev’essere finito
La soluzione può essere rappresentata mediante soluzioni parziali
La dimensione della soluzione finale S è nota
Il valore di ogni sotto soluzione dev’essere finito

Introduciamo lo pseudo-codice per il backtracking (versione ricorsiva)

E' utile definire un tipo enumerativo per elencare i valori delle sotto-soluzioni:

enum valori { MIN_VAL, MED_VAL, […] , MAX_VAL}

Lista che salva le sotto-soluzioni che assieme daranno la soluzione finale:

lista sottoSoluzioni { }

bool solve ( lista sottoSoluzioni )

x ß minVal

while (x <= MAX_VAL) {

if (canAdd (x,sottoSoluzioni) ) {

add (x,sottoSoluzioni) )

if ( isComplete (sottoSoluzioni) )

return true

else

if ( solve(sottoSoluzioni) )

return true

remove(x,sottoSoluzioni)

x = next(x)
}

else

x = next(x)
}

return false

La funzione solve rappresenta il backtracking: parte con il primo valore del nostro insieme che aggiunge alla lista di sotto-soluzioni se è conforme ai nostri vincoli (dettati dalla funzione canAdd). La funzione add ha il compito di aggiungere il nostro x alla lista delle sotto-soluzioni. isComplete ci informa se la lista di sotto-soluzioni è completa, dunque se abbiamo raggiunto la soluzione finale, se ciò non dovesse accadere viene richiamata la funzione solve ricorsivamente con la nuova lista di sotto-soluzioni aggiornata al valore x appena aggiunto. Se ci accorgessimo che nessun valore di x è in grado di soddisfare i vincoli e che quindi non possiamo più continuare con questa strada, ritorniamo false che fa fallire la condizione if (solve) e che dunque provvederà a rimuovere la x prima inserita, dato che i suoi nodi figli non permettono di continuare verso la soluzione (passo di backtrack, torniamo indietro modificando l'ultimo valore inserito). Il ciclo si ripete fin quando non abbiamo provato tutti i valori possibili di x e le varie strade senza trovare una soluzione (quindi restituendo false) o trovando una strada che ci conduce alla risoluzione del problema(quindi restituendo true in un qualsiasi punto del programma in cui tutte le chiamate ricorsive su solve restituiranno true o sarà soddisfatta la chiamata a isComplete).

Esempio: Problema delle otto regine

Animazione presa da Wikipedia

Il problema ci chiede di sistemare otto regine in una scacchiera 8x8. La posizione delle otto regine dev'essere tale da non permettere a nessuna regina di "attaccarne" un'altra.

Si può notare che possiamo risolvere il problema provando tutte le combinazioni possibili delle regine, ma si può ottimizzare usando il backtracking, posizionando, cioè, le regine in modo "intelligente" e non in tutti i modi possibili. Qualora una posizione non dovesse andare più bene si torna indietro e si modifica la regina precedente.

Usiamo un array di interi per rappresentare la soluzione, che avrà esattamente 8 indici di colonna (assumiamo che gli indici di riga siano uguali al numero della regina: regina 1 -> riga 1 ecc, dato che le regine sulla stessa riga possono attaccarsi).

Le nostre sotto soluzioni varieranno da 1 a 8 (indici di colonna).

Utilizziamo un indice (ultimaPosValida) facente parte dell' array di sotto-soluzioni che ci tiene traccia dell'ultima regina posizionata correttamente.

Applichimo lo pseudo-codice del backtracking:

bool isComplete ( sottoSoluzioni )

return sottoSoluzioni.ultimaPosValida == numeroRegine;

int next ( x )

return x+1;

void remove ( x, sottoSoluzioni)

sottoSoluzioni.ultimaPosValida --;

void add (x, sottoSoluzioni)

sol.ultimaPosValida ++;

sol.valori[sol.ultimaPosValida] = x;

bool canAdd (x,sol)

int currRig = sol.ultimaPosValida +1;

int currCol = x;

for ( int precRig = 1; precRig < currRig; precRig ++)

int precCol = sol.valori[precRig];

if ( currCol == precCol OR currRig - precRig == abs ( currCol - precCol) ) return false

return true

La funzione canAdd memorizza su currRig la riga della regina che si vuole posizionare, che sarà uguale alla riga della regina precedente già posizionata più uno (essendo le righe uguali al numero delle regine come detto sopra). currCol invece memorizzerà l'indice della colonna che dobbiamo "verificare". Il for cicla tutte le righe precedenti all'attuale e memorizza di volta in volta le colonne ad esse associate (in sostanza ad ogni ciclo abbiamo riga e colonna della regina memorizzata nel nostro array di sotto-soluzioni). Con il controllo if che segue, verifichiamo che la regina che stiamo inserendo non sia sulla stessa colonna o su una diagonale della regina precedente in esame ( precRig e precCol -> posizione regina precedente). La formula currRig - precRig == abs (currCol - precCol) indica proprio il controllo atto a verificare se le regine R1(precRig,precCol) ed R2(currRig,currCol) si possono attaccare diagonalmente. La funzione abs restituisce il valore assoluto: essa è applicata in currCol - precCol perché non sappiamo quale delle due colonne sia la maggiore, cosa che non si verifica per precRig e currRig dato che sappiamo che la regina Ri avrà numero di riga maggiore ad Ri-1 per convenzione.

[Ubuntu] Aggiungere icone sulle applicazioni

2012-03-15T11:43:00.002-07:00

In questo breve tutorial vedremo come impostare un accesso "grafico" alle nostre applicazioni eseguibili solo mediante terminale.

[NOTA: uso ubuntu 10.04, qualcosa potrebbe cambiare con le nuove versioni]

A volte è noioso lanciare una applicazione da terminale tutte le volte o vorremmo semplicemente lanciarla via "Icona" dal menù Applicazioni. In meno di 5 minuti questo diventa fattibile.

Per prima cosa rechiamoci in Sistema > Preferenze > Menù Principale. Da qui possiamo scegliere dal menù a sinistra, la nostra sezione per l'applicazione che vogliamo aggiungere. Cliccate su "Nuova Voce" e inserite i nei vari campi le informazioni opportune. Nel campo "Comando" va inserito esattamente il comando usato per lanciare l'applicazione quando aprite il terminale (partendo dalla directory ~/ in genere). Cliccate sull'immagine della molla per aggiungere l'icona del programma, infine confermate tutto ed il gioco è fatto.

Esempio installazione Eclipse

[Saltate al punto 2) se vi interessa solo l'esempio di come aggiungere l'icona nel menù)

1) Eclipse è un IDE per linguaggi come C++ e Java. Scarichiamo il pacchetto dal sito ufficiale e usiamo il comando tar zxvf per scompattarlo. Ora notiamo che dentro la cartella Eclipse c'è l'eseguibile omonimo. Con un semplice doppio click o con ./eclipse nel terminale il programma parte.

2) Sistema > Preferenze > Menù Principale. Clicchiamo la '+' su 'Applicazioni', qualora la lista fosse nascosta, e clicchiamo su programmazione (o qualunque altra categoria preferite). Click su "Nuova Voce"

Ora nella nuova finestra inseriamo:

Tipo: Applicazione

Nome: Eclipse

Comando: /home/vostroNome/eclipse/./eclipse

Commento: (potete lasciarlo vuoto)

[vostroNome -> Nome utente che usate nel sistema].

Ovviamente se la cartella di eclipse si trova in "Documenti" il comando sarebbe:

/home/vostroNome/Documenti/eclipse/./eclipse

Clicchiamo ora sull'immagine della molla e carichiamo il file "icon.xpm" presente nella cartella di Eclipse.

Ecco qui la nostra nuova icona che richiamerà il comando e quindi lancerà l'applicazione senza nessuno sforzo.

Tecniche di Programmazione: Divide et Impera

2012-03-07T08:00:00.000-08:00

In questo post l'intenzione è quella di scrivere uno schema della tecnica divide et impera, basandomi sugli appunti presi a lezione e sul libro di testo (Algoritmi e Strutture Dati di Demetrescu, Italiano, Finocchi edito dalla McGraw Hill). Per qualsiasi suggerimento o altro lasciate un commento o contattateci!

Principio: Principalmente si compone di due passi:
Passo Divide: Dividere i dati in ingresso in due o più sottoinsiemi tramite la ricorsione.
Passo Impera: Risolvere il problema sui sottoinsiemi e ricombinare le varie soluzioni per ottenere la soluzione globale. Considera il problema con un approccio top-down.

Punti di forza: l'efficacia aumenta se il problema è facilmente scomponibile.
Punti di debolezza: Richiede uno sforzo per individuare tecniche per la decomposizione e la ricombinazione: non è immediato e banale trovare il passo Divide e il passo Impera.

Esempio: QuickSort
Il quick sort è un algoritmo di ordinamento. Il suo funzionamento applicato ad un array è il seguente:
Divide: Sceglie a caso un indice x (la scelta casuale dell'indice diminuisce la complessità dell'algoritmo) e partiziona la sequenza in modo tale che una sequenza contenga elementi <= ad Array[x] e l'altra contenga elementi >Array[x]. (questo processo è ricorsivo)
Impera: unisce la sottosequenze ordinate.

Procedura partition (array A, indici i, f ) → indice
x ← A[i]

inf ← i
sup ← f +1
stop = false
while ( !stop ) do
do inf ← inf + 1
while ( inf <= f and A[inf] <= x )
do sup ← sup – 1
while ( A[sup] > x )
if ( inf < sup )
scambia ( inf , sup ) // scambia A[inf] con A[sup]
else
stop = true
scambia (i , sup ) // scambia A[i] con A[sup]
return sup

Esempio di procedura Partition [Wikipedia]

algoritmo quicksort (array A, indici i, f )
if ( i >= f )
return
m ← partition (A,i,f)
quicksort (A,i,m-1)
quicksort (A,m+1,f)

Praticamente l'algoritmo si può sintetizzare così:

Dato un array in input e due indici i ed f, rispettivamente la posizione iniziale e la posizione finale dell'array (nella prima chiamata), esegui quicksort: se abbiamo più di un elemento (la condizione dell'if) salvami in m il risultato della partizione del mio array attuale (l'indice posizionato correttamente dopo l'esecuzione di partition) e chiama la funzione quicksort (ricorsione) sulle due parti prima di m e dopo di m (le parti ancora “in dubbio”, quindi da ordinare).

La funzione partition funziona così:

Metti in inf l'indice i e in sup l'indice f; inizializza a falso la variabile booleana stop che ci dirà quando abbiamo finito la chiamata di funzione; ora:
→ scorri verso destra l'array tramite l'indice inf e fermati solo quando trovi un elemento più grande di x ( che ricordiamo è ora A[i] ) oppure se con l'indice inferiore hai sorpassato ( o sei sulla stessa posizione) l'indice superiore ( ho visitato tutti gli elementi ).
→ scorri verso sinistra l'array tramite l'indice sup e fermati solo quando trovi un elemento più piccolo o uguale a x. (in questo caso è ridondante inserire un controllo che si ferma se arriva all'indice inf o lo supera, dato che, in caso li scorre tutti da destra, si fermerà sicuramente alla posizione i, dato che A[i] è sicuramente = ad x e ciò fa interrompere il ciclo).
In questo modo ci fermiamo quando A[inf] sarà maggiore di x e A[sup] sarà minore o uguale ad x. A questo punto li scambiamo, così avremo nella parte destra tutti i numeri maggiori di x e nella parte sinistra tutti i numeri minori.

Quando l'indice inf avrà superato (o raggiunto) l'indice sup, significa che ho fatto tutti i confronti e dunque poniamo stop = true, che farà fermare il ciclo. L'ultimo passo è quello di scambiare l'elemento perno, A[i], con A[sup], il che porterà l'elemento A[i] nella sua posizione finale e avrà alla sua sinistra i numeri minori o uguali e alla sua destra i numeri maggiori.

Se come perno usiamo ogni volta il primo elemento nell'array (quindi come i usiamo 0) potremmo avere il caso peggiore che A[0] sia l'elemento più piccolo o più grande dell'array e dunque la complessità dell'algoritmo sarà O(n^2). Per rendere più efficiente la complessità, scegliamo come indice i, un numero casuale, portandola a O (n log n).

Quicksort. Le linee orizzontali sono gli indici scelti (pivot) [Wikipedia]

Tecniche di Programmazione: Programmazione Dinamica

2012-03-05T02:20:00.000-08:00

In questo post ho cercato di scrivere quello che avevo capito di una delle tecniche di programmazione più note, la programmazione dinamica, basandomi sugli appunti presi a lezione e sul libro di testo (Algoritmi e Strutture Dati di Demetrescu, Italiano, Finocchi edito dalla McGraw Hill). Per qualsiasi suggerimento o altro lasciate un commento o contattateci!

Principio:

Utilizzare una struttura di supporto per memorizzare alcune soluzioni parziali, mediante le quali giungeremo alla soluzione del nostro problema. L'uso di "tabelle" di supporto è utile per evitare di ricalcolare informazioni più volte. Il nome di questa tecnica deriva proprio dalla struttura di supporto: si programma dinamicamente la soluzione finale mediante alcuni passi intermedi presenti nella tabella delle soluzioni. Un approccio che utilizza la programmazione dinamica segue alcuni passi:

Identificare i sottoproblemi e il criterio di scomposizione delle varie soluzioni
Creare una tabella di supporto che conterrà le soluzioni dei sottoproblemi e alcuni valori di “default”, cioè le soluzioni dei sottoproblemi minimi (in genere i sottoproblemi unitari o comunque i più immediati, di cui si dispone già la soluzione)
Utilizzare le soluzioni memorizzate in precedenza per generare la soluzione i-esima, sino ad arrivare alla posizione/soluzione voluta.

Il problema viene scomposto in modo bottom-up, ovvero partiamo dalle soluzioni dei sottoproblemi unitari per calcolare le partizioni del problema più complesse che a loro volta ci serviranno per ottenere la soluzione al problema stesso.

Esempio: Minimizzare il prodotto tra matrici

I metodi per moltiplicare 3 o più matrici sono più di uno e tutti si basano sulla “parentesizzazione” che adottiamo, cioè la priorità che diamo alle varie moltiplicazioni.

Moltiplicare (M1*M2) * M3, in genere, ha un costo diverso che moltiplicare M1*(M2*M3).

Innanzitutto analizziamo il costo di moltiplicazione tra due matrici:

algoritmo MoltiplicaMatrici ( matrice M1, matrice M2 ) → matrice

assert (M1.colonne == M2.righe )

Matrice M3 {vuota};

k, i, j ← 0

for ( i= 0; i < M1.righe; i++)

for ( j=0; j < M2.colonne; j++)

for ( k = 0, k < M1.colonne, k++)

M3 [i] [j] += M1[i] [k] * M2 [k] [j]

return M3;

(Nota: Due matrici si possono moltiplicare solo se il numero di colonne della prima è uguale al numero delle righe della seconda).
Questo semplice algoritmo agisce così:

>>Definisci 3 indici k, i e j e inizializzali a 0. L'indice i serve a scandire le righe di M1, l'indice j scandisce le colonne di M2 e l'indice K ci fa da contatore per far compiere esattamente M1.colonne volte (o M2.righe, che è uguale) l'operazione di moltiplicazione nelle posizioni corrette delle matrici M1 ed M2.

>> Posizionati sulla riga i-esima della matrice M1; posizionati sulla colonna j-esima della matrice M2; esegui la sommatoria della moltiplicazione degli elementi M1[i][k] e M2[k][j] che di fatto significa moltiplicare, due per volta, gli elementi della riga i di M1 e gli elementi della colonna J di M2 e addizionare il loro risultato alla posizione della matrice risultato M3 nella posizione (i,j).P

>>Risulterà che l'elemento M3[i][j] è stato prodotto dalla sommatoria di tutti gli elementi M1[i][k] e M2[k][j] moltiplicati fra loro.

Moltiplicazione tra due matrici. [Wikipedia]

La complessità è di O(n^3) essendoci 3 for innestati. Dunque se L1 ed L2 sono rispettivamente il numero delle righe e il numero delle colonne di una matrice M1, L3 ed L4 indicano la stessa cosa ma su una matrice M2 con il vincolo che L2 sia uguale ad L3, avremo un costo di moltiplicazione pari a:
L1 x L2 x L4
Possiamo notare che, avendo tre matrici o più, il costo varia a seconda dell'ordine di moltiplicazioni che facciamo. Ad esempio:
[ formato : nRighe x nColonne ]

M1 [100 x 300 ]

M2 [300 x 1000]

M3 [1000 x 5]

Analizziamo i costi:

(M1 x M2 ) x M3 = M1/2 x M3;
Ricordiamo che la matrice risultante M1/2 avrà L1 righe ed L3 colonne.
costoTot = costo (M1 x M2) + costo (M1/2 x M3);
costo (M1 x M2 ) = 100 x 300 x 1000 = 30.000.000
costo (M1/2 x M3) = 100 x 1000 x 5 = 500.000

>>costoTot = 30.500.000 operazioni.

Analogamente:
M1 x ( M2 x M3 ) =
M1 x M2/3;
costoTot = costo (M2 x M3 ) + costo (M1 x M2/3)
costo (M2 x M3) = 300 x 1000 x 5 = 1.500.000
costo (M1 x M2/3) = 100 x 300 x 5 = 150.000

>>costoTot = 1.650.000 operazioni

La variazione dei costi dipende proprio dalle dimensioni della matrice risultato delle prime moltiplicazioni: nel primo caso abbiamo a che fare con una matrice M1/2 che ha 100 righe e 1000 colonne; nel secondo caso la matrice M2/3 ha 300 righe e 5 colonne!
Applichiamo una idea che segue la programmazione dinamica per calcolare il costo minore per effettuare le moltiplicazioni e quindi la giusta priorità da dare alle moltiplicazioni delle matrici.
Date un numero di matrici n superiore a 3, i sottoproblemi possono riguardare la moltiplicazione di una parte di questo blocco intero di matrici, ad esempio dalla matrice i alla matrice j. Come problema base, notiamo che se i fosse uguale a j, il costo sarebbe unitario e proprio uguale a 0. Dunque abbiamo trovato i valori da assegnare alla nostra struttura appoggio di programmazione dinamica: tutte le operazioni che coinvolgono la stessa matrice avranno costo 0. Ma, allargando il nostro orizzonte in vista della soluzione finale, avremo bisogno di tutti i costi per poter scegliere il migliore. Adottiamo dunque come struttura dati supporto, una matrice quadrata avente numero di righe/colonne uguale al numero di matrici che vogliamo moltiplicare. La matrice così creata avrà la diagonale principale nulla, dato che i costi di moltiplicazione delle matrici Mi e Mi è 0. In ogni altra casella (i, j) avremo la soluzione OTTIMA del problema adattato alle matrici Mi x Mi+1 x.....x Mj. Infine il passo di avanzamento nella nostra matrice di programmazione dinamica è il seguente:

M [i,j] = M[i,r] + M[r+1,j] + Li * Lr+1 * Lj+1

Ovvero:
Il costo della moltiplicazione fra le matrici [Mi x … x Mj] è uguale al costo della moltiplicazione delle matrici [Mi x …. Mr] sommato al costo della moltiplicazione delle matrici [Mr+1 x …. Mj ] sommato al costo di moltiplicazione di questi due blocchi di matrici che è appunto Li x Lr+1 x Lj+1. Spieghiamo meglio questo svolgimento: noi spezziamo il costo di moltiplicazione tra le matrici (i,j) in 2 tronconi, divisi dall'indice r. Questo indice r, compreso tra i e j-1, fa sì che noi dividiamo il problema in modo tale che possiamo sommare i costi dei due pezzi ( il costo da Mi ad Mr e il costo da Mr+1 ad Mj). Infine dobbiamo sommare il costo della moltiplicazione di questi due pezzi, che è la formula detta in precedenza. (si noti che la matrice risultato del primo blocco avrà righe pari alle righe di Mi e colonne pari alle colonne della matrice Mr ; la matrice risultato del secondo blocco avrà righe pari alle righe della matrice Mr+1 e colonne pari alle colonne della matrice Mj)

Nel nostro algoritmo dobbiamo cercare tutti i possibili valori di r, che fungerà da separatore delle moltiplicazioni; servirà, cioè, a stabilire il vero costo ottimo della moltiplicazioni delle matrici. (per capirci nell'esempio precedente r valeva “2”, dato che M1 x (M2 x M3) era meglio di (M1 x M2) x M3 e dunque poniamo la separazione sulla seconda moltiplicazione).
R sarà calcolato trovando il minimo dei vari costi.

Algoritmo moltiplicazioneOttima ( array InfoMatrici ) → intero

n ← size (InfoMatrici)

matrice M di n x n

for ( i = 1 to n ) do M[i,i] ← 0

for ( d = 1 to ( n-1) do

for ( i = 1; to (n-d) do

j ← d +1

M[i,j] ← MAX_INT

for r = i to (j-1) do

M[i,j] ← min ( M[i,j], M[i,r] + M [r+1,j] + InfoMatrici[i] * InfoMatrici[r+1] * InfoMatrici[j+1]}

return M[1,n]

Ricevuto un array con le informazioni sulle matrici (nRigheM1,nColonneM1,nColonneM2,nColonneM3 […] ) l'algoritmo crea la matrice M che servirà da supporto e mette a 0 i costi unitari ( M1 x M1, M2 x M2 […] quindi azzera M[i,i]). Una volta fatto questo si pone un indice d, che segnerà la diagonale, che parte da 1 e arriva ad n-1 (ad n c'è uno 0, è inutile). Ad ogni ciclo di d viene fatto partire un indice i che segnerà la nostra riga corrente ed andrà da 1 fino ad n-d, cioé fino alla fine della matrice senza sforarla. L'indice j parte invece dalla prima posizione utile della matrice supporto, cioè da una posizione dopo la diagonale azzerata, e sarà il nostro indice di colonna. Mettiamo il massimo intero rappresentabile ( per simboleggiare infinito) nella posizione i,j della matrice M e procediamo provando tutti gli r: così facendo calcoliamo tutti i costi partizionando l'espressione in tutti i modi possibili e sovrascrivendo la cella i,j con il minore tra questi valori (quello già precedente e quello calcolato nel generico passo i).

Per esempio nella prima chiamata:

i = 1, d = 1, j = 2, r = i = 1.
Stiamo guardando la cella M[1][2] che rappresenta il costo della moltiplicazione tra le matrici M1 x M2. Dato che c'è un unico modo per moltiplicare queste matrici, il ciclo che vede r “protagonista” ciclerà una sola volta: r è uguale ad i ed è già j-1 dato che i è 1 e j è 2. Dunque verrà posizionato nella posizione M[i,j] il valore M[i,i] + M[r+1][j] + Li * Lr+1 * Lj+1, dato che è sicuramente minore di MAX_INT. Il valore sarà M[1,1] (che è zero) + M[1,1] (che è 0 dato che r=i) + M[2,2] ( che è uguale a 0 anch'esso) + il costo di queste due matrici: nRigheM1 x nColonneM1 x nColonneM2, che si possono trovare nell'array contenente le info delle matrici, alle rispettive posizioni ( i, r+1 e j+1 cioé 1,2,3).

In un generico passo l'algoritmo si troverà sulla riga i e confronterà i vari costi della moltiplicazione delle matrici spezzettandole su r; il costo minore rimarrà memorizzato sulla cella opportuna. Da notare che la matrice si crea dinamicamente e che tutte le informazioni utili non vengono ricalcolate, ma vengono “prelevate” dalla matrice dato che essa contiene di volta in volta i costi ottimi. Quindi se per calcolare il costo ottimo del passo i, spezzo le matrici nel punto r, cercherò i costi minimi di quelle due matrici nella tabella.

Foto post: IBM

C++11 il nuovo standard ISO C++

2012-03-04T04:31:00.000-08:00

Il 12 Agosto 2011 è stato approvato il nuovo standard ISO C++, C++11 (C++0x). L'autore del linguaggio, Bjarne Stroustrup, considera le novità introdotte molto più significative di quelle presenti nei precedenti standard.

Le novità toccano sia il core del linguaggio che la libreria standard, vediamo schematicamente le novità introdotte:

CORE:
-espressioni lambda
-auto e decltype
-nuova sintassi di inizializzazione degli oggetti
-costruttori delega
-funzioni di default e deleted
-nullptr
-riferimenti rvalue

Libreria Standard:
-nuovi algoritmi
-nuove classi contenitore
-operazioni atomiche
-type traits
-espressioni regolari
-nuovi smart pointers
-async()
-una libreria multithread

Per una completa visione delle novità, con relativi esempi, vi rimando all'ottimo sito HTML.it .

Lucidchart, diagrammi di flusso per tutti

2012-02-28T05:57:00.000-08:00

Lucidchart è un ottimo tool online per la creazione di diagrammi di flusso, di ogni tipo e con molte funzionalità, tra cui la condivisione, che sta prendendo sempre più piede in questo periodo.

Come ho anticipato prima Lucidchart è un sito che offre un tool online di sviluppo di diagrammi di flusso, e mette a disposizione una miriade di forme e di strumenti.
Una delle funzionalità più interessanti è la condivisione, cioè dopo aver creato la mia "mappa" io potrei invitare altre persone per fargliela consultare e potrei anche dare il permesso di modificarla arrivando ad avere un vero e proprio tavolo di lavoro su cui più persone possono intervenire allo stesso momento.

Però ci sono delle piccole limitazioni in quanto questo strumento è a pagamento, ma si può creare liberamente un account free, che permette di suo di accedere a moltissime forme, ma ha una limitazione sul numero, infatti questo tipo di account permette di creare al massimo 60 oggetti, che a mio parere non sono nemmeno pochi e non permette l'utilizzo di alcuni simboli un pò più particolari.

Un'altra nota positiva sta nel fatto che in teoria si potrebbe fare una richiesta al sito per avere un account professional gratis in quanto studenti, ma purtroppo per usufruire di questa promozione bisogna avere un account mail .edu, in alternativa un professore può mandare una richiesta, direttamente dal sito, in cui chiede delle licenze gratuite per tutto il suo corso e queste avranno durata di un anno.

Il link per accedere è questo Lucidchart
Basta una registrazione veloce e la tavola di lavoro sarà subito pronta per essere usata.

Il Windows delle mie brame 2 - Le icone

2012-02-08T13:26:00.000-08:00

Con il Windows delle mie brame parte 1 abbiamo visto brevemente come migliorare in modo sostanzioso l'aspetto della nostra scrivania grazie ai temi della comunità. In questo secondo post di una guida per puri narcisisti vedremo invece come personalizzare le singole icone del nostro Windows.

Questa guida ha scopi decisamente modesti ma malgrado le basse aspettative dovremo avvalerci dell'aiuto di due software: l'ormai famosissimo Photoshop {o un qualsiasi programma di grafica ai suoi livelli} e il piccolo ToyCon {qui il link per scaricare questo tool decisamente minuto}. Una volta che avete tutto il necessario non rimane che iniziare.
Per prima cosa, decidete quale icona volete modificare e reperite il file immagine nella cartella del programma

{un piccolo consiglio spesso le icone essendo già pronte per essere usate non sono un ottimo materiale per una sessione di Photoshop... per questo motivo vi consiglio caldamente di trovare un buon sostituto sul web. Solitamente basta cercare il nome del programma scelto su google e non preoccupatevi se ha uno sfondo, a fine guida avremo eliminato anche quello} quindi apritela con il vostro programma di grafica. Ora lo strumento che ci aiuterà è il lazo magnetico questo perché l'occhio della mia icona non è a tinta unita, in caso contrario avrei potuto usare il tool bacchetta magica, pazienza occasione in più per impratichirsi. Come si può ve

dere dallo sfondo a scacchi la mia icona è priva di sfondo{questo è il vantaggio di prenderle direttamente dalla cartella del programma}

Facendo molta attenzione selezionate la parte che volete modificare {più la selezione è precisa più il risultato sarà apprezzabile!}.Per icone più complesse potete benissimo avanzare per piccole porzioni ma ricordate bene ogni valore che assegnerete alla nuova tonalità cosi da non avere discrepanze nel colore. Ed eccola qui la nostra porzione selezionata{non badate troppo alla sbavatura me ne sono accorto in un secondo momento ed è stata subito corretta!}

Ora clicchiamo sulla voce Immagini e scorrete su regolazioni, quindi cliccate sulla penultima voce: Sostituisci colore

Ormai il più è fatto, con il primo dei tre contagocce che vi ritroverete nella schermata selezionate l'area da modificare che immediatamente verrà imbiancata nell'anteprima, usate gli altri due strumenti per aggiungere{il contagocce con il +} e rimuovere{il contagocce con il -} aree alla prima in fine regolate il tutto modificando il valore di tolleranza fino a selezionare tutta l'area interessata.A questo punto non rimane che modificare i valori di tonalità saturazione e luminosità fino a che non troverete la tinta che più vi aggrada{come si vede dalla prima immagine io ho una predilezione per il verde acceso}

Non rimane che confermare con il tasto ok deselezionare l'immagine e salvare il tutto con l'estensione .png in una qualsiasi cartella. Vediamo ora come far funzionare il piccolo ToyCon., una volta spacchettato salvato ed avviato {è un semplice eseguibile, niente noiose installazioni!} dobbiamo solo preoccuparci di trascinare l'immagine dell'icona appena salvata nel piccolo box come nell'immgine

il programma si preoccuperà di fare il resto, una volta trascinato il file nella cartella in cui risiede troverete un file con lo stesso nome ma finalmente con l'estensione che cerchiamo: l'estensione di tipo icona! Quindi torniamo sul desktop, tasto destro sul l'icona da modificare, clicchiamo su proprietà e dopo aver cliccato su cambia icona non rimane altro che cercare tramite il menù sfoglia l'icona precedentemente modificata.

Sublime Text 2 ... L'evoluzione di Gedit

2012-02-08T13:13:00.000-08:00

Se anche tu non puoi fare a meno di programmare con Gedit ma vorresti che in quella semplice schermata bianca ci sia giusto quel qualcosa in più che potrebbe rendere il tuo lavoro più leggero, Sublime text 2 è il sofware giusto per le tue esigenze.

Sublime Text 2 è un editor di testo, che può sembrare un semplice editor ma non lo è. Tutto quello che manca a Gedit lui lo ha.
Dotato di un'interfaccia asciutta e dark, questo programma rende più piacevole il lavoro, in quanto non affatica molto la vista ed è dotato di piccole migliorie che lo rendono un programma assolutamente da avere per chi è abituato a programmare in questa maniera.
Comnciando dalla panoramica laterale, questa è molto utile per trovare, alla buona ,parti di codice che altrimenti sarebbero nascoste chissà in quale riga.

Un'altra caratteristica interessante è quella di poter avere più colonne o più righe o tutte e due in cui poter aprire i nostri file e quindi poter avere magari su una colonna il nostro file .ccp e nell'altra il corpo dell'header cioè il .h ,o semplicemente avere due esercizi contemporaneamente aperti per prendere spunto.

Ovviamente sono molti i punti a favore di questo programma, ma una cosa molto interessante è che lo si può trovare per tutte le piattaforme più importanti e quindi sia per Linux,Windows e Mac a questo indirizzo: www.sublimetext.com/2

Qui sotto un piccolo video che mostra la multiselezione, e cioè selezionare più parti del file e cambiarle tutte in una volta:

&lt;p&gt;&amp;amp;amp;amp;lt;p&amp;amp;amp;amp;gt;&amp;amp;amp;amp;amp;lt;/div&amp;amp;amp;amp;amp;gt; &amp;amp;amp;amp;lt;/p&amp;amp;amp;amp;gt;&lt;/p&gt;

Il Windows delle mie brame 1 - I temi

2012-02-05T02:58:00.000-08:00

Quando si passano ore davanti un monitor è opinione generale che rendere confortevole e soprattutto piacevole alla vista ciò che ci circonda può incrementare la concentrazione e rendere il lavoro meno stressante.

Bhe non essendo un designer d'interni o un esperto di taichi non posso darvi una mano su come arredare la vostra stanza di lavoro ma per quanto riguarda la scrivania del vostro Windows qualcosina si può fare:

Parte 1: I temi

Partiamo dal basso, chi ha detto che le cose semplici non sono efficaci? Che frase poco pensata, infatti basta davvero poco per rendere il vostro pc più accattivante una di queste idee sono appunto i temi.

La comunità di Seven ha creato una miriade di temi per tutti i gusti ma se non si sa come agire il semplice file "Theme pack per Windows" diventa utile quanto un soprammobile di pessimo gusto.

La prima fonte di temi che vi propongo è proprio il sito di Microsoft che offre una vasta gamma di temi ufficiali: :http://windows.microsoft.com/it-IT/windows/downloads/personalize/themes

tutti i file scaricati non vanno registrati e per applicarli basta semplicemente cliccarli una volta terminato il download.

Ma cosa succede se un tema scaricato da una comunità di artisti{vedi DeviantArt e siti simili} non è riconosciuto automaticamente da Windows?

Nessun problema, come spesso succede la comunità ha risolto anche questo piccolo intoppo: si ricorre ad una patch che permette la registrazione di temi creati da terze parti il cui nome è Uxstyle Core {qui c'è il link softonic per chi volesse scaricarla cliccami!}.

Una volta eseguita la patch possiamo comodamente scaricare i nostri temi e installarli, dopo aver spacchettato il tema l'unica operazione che dobbiamo eseguire è spostare il file o i file .theme nella cartella C:\Windows\Resources\Themes. Una volta spostato nella giusta cartella basterà un click con il tasto destro su un punto vuoto della scrivania e dopo aver selezionato personalizza basterà scegliere il tema installato dalla lista che Windows ci propone, semplice vero?

Tuttavia molti artisti rilasciano anche degli stili di scrittura {i classici fonts} che se non presenti di base nel nostro pc vanno aggiunti manualmente, nulla di più facile!

Basta entrare nel pannello di controllo cliccare sulla voce Aspetto e Personalizzazione e quindi su caratteri, fatto questo rimane solo una cosa da fare: trascinare l'eventuale file .tff del tema nella finestra.

E dopo questo "duro" lavoro potete comodamente godervi la vostra nuova veste grafica.

Come registrare una DLL

2012-01-29T04:13:00.000-08:00

Almeno una volta per quasi tutti i Windows User si sono ritrovati ad armeggiare con questi strani ma essenziali file di sistema, sto parlando delle ormai famosissime DLL. Certo aprire uno di questi file e magari modificarne il contenuto non ha mai portato nulla di buono allo sfortunato utente tuttavia imparare come e dove registrarle è una conoscenza di cui non si può fare a meno.

In sistemi datati come XP e Vista registrare queste librerie dinamiche era decisamente facile, bastava ricorrere infatti ai semplici comandi

Start, Esegui

e successivamente scrivere nella finestra di comando la stringa:

Regsvr32"C:\Windows\System32\nomedll.dll

Poter dire lo stesso sull'ultimo prodotto di casa Microsoft non è cosi semplice invece, in ambiente seven la registrazione di una Dll è ormai una di quelle operazioni soggette a richiesta di autorizzazione quindi la lista di comandi necessari si allunga un pò:

Start, Accessori, Tasto destro su Prompt dei comandi e selezioniamo Esegui come admin . Dopo che sarà comparso l'ormai quasi sconosciuto terminale registriamo la Dll:

per sistemi a 32bit Regsvr32"C:\Windows\System32\nomedll.dl

per sistemi a 64bit Cd\Windows\Syswow64 successivamente ricorriamo al comando registra

Regsvr32 C:\nomedll.dll

In tutti i casi elencati è fortemente consigliato di riavviare il sistema.

End Piracy Not Liberty - contro PIPA e SOPA

2012-01-18T12:27:00.000-08:00

PIPA e SOPA,
Due acronimi che stanno per "Stop Online Piracy Act" e "Protect Intellectual Property Act", nomi che sembrano far sperare a qualcosa di buono. Sembrano.
Ma andiamo con ordine: come recita Wikipedia Italia, il 26 Ottobre 2011 è stata proposta alla camera dei rappresentanti degli Stati Uniti d'America una legge chiamata proprio Stop Online Piracy Act e, parallelamente, giorno 24 Gennaio 2012 è prevista la discussione sulla Protect IP Act, una seconda legge. Queste leggi hanno come argomento i diritti d'autore sul web, avendo come obiettivo lo smantellamento della pirateria informatica e le violazioni del diritto d'autore introducendo sanzioni a chi non le dovesse seguire. Tali norme, però, sono state considerate nocive per la libertà sul web, uno dei punti di forza di colossi quali Wikipedia, Creative Commons e i blog in generale (quindi piattaforme come WordPress/Blogger ecc). L'iniziativa parte con una ideologia che dovrebbe essere corretta quella, cioè, di distruggere la pirateria informatica e in generale la gente che danneggia sul web materiale altrui, ma praticamente potrebbe sfociare nel danneggiamento di qualunque cosa violasse un diritto d'autore o qualunque contenuto ritenuto inadatto. Che sia Google, Yahoo o il nostro blog, se i materiali veicolati sono protetti da copyright, si è a rischio. Pensate a Youtube e ai numerosi servizi usati quotidianamente, soprattutto a gente che ha passato degli anni a cercare di creare una sorta di sapere "universale", utile alla comunità qual'è il progetto che si è reso tangibile con Wikipedia.
Siamo sicuri che è una lotta alla pirateria e non un altro modo per controllare l'informazione? Siamo sicuri che questa iniziativa non degenererà in qualcosa come il regime Cinese che controlla (anche) l'informazione sul web? O è come dice Massimo Gaggi (corriere.it):
"Il braccio di ferro sulla protezione del copyright è, insomma, diventato una guerra a tutto campo tra Hollywood e la Silicon Valley[...]"?

Ho riportato solo una sintesi di tutto questo fenomeno, ma vi invito a documentarvi ulteriormente sui siti in fondo a questo articolo.
Io non sono uno scrittore e neanche un blogger accanito, amo solamente l'informatica e tutto ciò che la riguarda, ma sento che, se le ripercussioni saranno simili a quanto detto e a quanto si può trovare in rete, questo passo cambierà il web. E, se pensiamo alla miriade di programmi TV, giornali e quant'altro che fanno tutto tranne essere imparziali, penso che il web sia una delle poche cose rimaste pure e libere. Personalmente mi associo con Google e con lo slogan della sua raccolta firme:
End Piracy, Not Liberty.

Ecco un paio di link utili:

Raccolta firme Google contro le leggi PIPA e SOPA

Wikipedia PIPA e SOPA in dettaglio [ita]

Come SOPA/PIPA possono cambiare la nostra vita quotidiana (sul web) [eng]

Il Sistema Dual-Channel...questo sconosciuto

2012-01-04T08:00:00.001-08:00

Vi è mai capitato di leggere la scheda tecnica di un pc ,che magari siete interessati ad acquistare, senza riuscire a dare un senso a tutte quelle sigle e numeri che la seguono? Senza contare quella stranissima parola che ormai affligge la maggioranza dei pc in commercio...Dual Channel... vediamo di capire e di conoscere almeno per grandi linee il vantaggio di questa "nuova" {ormai esiste da un pochetto} caratteristica!
Per capire come funziona il canale RAM in Dual Channel è necessario capire come funzioni un normalissimo canale singolo, quello che i pc hanno comunemente sfruttato e che continuano tutt'ora a fare. La ram è la memoria su cui opera il pc direttamente {ad esempio i dati che servono all'esecuzione di un programma vengono trasportati sulla ram} e fino all'avvento del Dual Channel poteva "comunicare" con i vari componenti con un singolo "canale". Fin qui tutto bene certo, ma con l'avvento di memorie RAM sempre più capienti e veloci si è riscontrato quello che viene volgarmente definito collo di bottiglia: I dati affluiscono dalla CPU con velocità e mole crescenti ma non vengono sfruttati in tempo utile, come un ingorgo autostradale ai pressi di uno svincolo... che gran felicità ehh?
Citazioni automobilistiche a parte, la soluzione a questo problema è stata l'aggiunta di un secondo canale di comunicazione tra CPU e RAM che permetteva di avere prestazioni migliori con costi decisamente contenuti. Per ottenere un collegamento in Dual-Channel non è sufficiente pero' avere un controller memoria abilitato. Per essere applicato correttamente dobbiamo prima di tutto assicurarci che la nostra mobo supporti la tecnologia e successivamente collocare i moduli di RAM in particolari slot, solitamente colorati in modo differente{Nella nostra foto sono i banchi arancioni}. Tuttavia non basta controllare di aver allocato la memoria nel posto giusto ma bisogna controllare che le barre di memoria siano compatibili{molti sostengono addirittura identiche} tra loro in fatto di latenza.
Naturalmente i pc adesso hanno un minimo di tolleranza riguardo certi aspetti{possiamo dire meno "schizzinosi" se mi concedete il termine} e adesso non è raro trovare sistemi Dual Channel con banchi di RAM differenti tra loro, tuttavia il pc sfrutterà le caratteristiche di latenza peggiori su entrambi i banchi di memoria.

Code Search Engine

2012-01-02T03:56:00.000-08:00

Per una ricerca ottimale di classi, algoritmi, funzioni e codice sorgente in generale, esistono dei motori di ricerca sviluppati appositamente per questo scopo.

Molte volte un programmatore potrebbe cercare del codice sorgente, per confrontarsi con frammenti di codice scritti da altre persone, per vedere l'implementazione, per necessità o semplicemente per servirsene in modo veloce. Esistono motori di ricerca che cercano tra molti file scritti in vari linguaggi di programmazione per trovare il codice che cerchiamo. Uno di questi è Google Code Search, che offre un'ottima interfaccia per l'utente e molti campi per ottimizzare la ricerca.

I vari campi di ottimizzazione della nostra query su Google Code Search

Un esempio di risultato

Purtoppo Google Code Search è un servizio che verrà chiuso tra un pò di tempo. Ma Google non è la sola soluzione per le nostre ricerche in ambito di programmazione: Koders e Krugle sono valide alternative.

Koders si presenta con un'interfaccia più semplice rispetto a quella di Google Code Search. Funziona egregiamente e attualmente cerca tra 3,338,449,289 righe di codice open source, come recita il sito stesso.

Il motore di ricerca Krugle ha caratteristiche peculiari quali inserire dei frammenti di codice ("snippets"), data di scrittura del codice ecc. Il sito presenta anche delle versioni software (divise in Basic, Enterprise..) da poter scaricare.

Link:

Google Code Search

Koders

Krugle [sito]

Krugle openSearch [motore di ricerca]

Fonte

Cercare i contatti tramite numero [iDevice]

2012-01-02T03:23:00.000-08:00

A volte è abbastanza scomodo cercare il possessore di un numero di telefono che non abbiamo memorizzato sul nostro telefono. Magari vogliamo sapere a chi corrisponde un determinato numero e abbiamo tutti i contatti salvati sull'iPad o sull iPod Touch ecc..Per questo ci viene incontro l'applicazione....

Contact By Number, sviluppata da Peter Breitling e disponibile gratuitamente sullo store di Apple. L'applicazione è semplicissima da usare e molto semplice anche come interfaccia: basterà iniziare a scrivere il numero per vedere la corrispondenza con il nostro contatto, preso direttamente dalla applicazione "Contatti" messa a disposizione sugli iDevice. Ho trovato questa applicazione molto utile, in quanto ho vari cellulari con varie schede e ho deciso di salvarmi tutti i numeri su "contatti" di Apple, aggiornando così anche il Mac. Ora anziché girarmi 2/3 telefoni in cerca del numero, posso tranquillamente usare questa applicazione. Davvero utile per chi non ha tutti i contatti memorizzati su un unico telefonino.

L'applicazione è progettata per iPhone/iPod Touch e la potete trovare qui.

SaloonSoft vi augura buone feste!

2011-12-25T05:10:00.001-08:00

Clicca per vedere l'immagine animata!

Creare una matrice dinamica velocemente [c++]

2011-12-22T07:43:00.000-08:00

Diciamoci la verità, le matrici dinamiche sono utilissime, e su questo non c'è dubbio, ma implementarle nel c++ non viene così naturale come per i vettori.
E' per questo motivo che in questo articolo, tratteremo un modo semplice e veloce per creare e riempire una matrice totalmente dinamica senza mai toccare un puntatore direttamente.

Ovviamente per far si che il nostro codice sia più semplice possibile ci avvaleremo di una libreria standard che è il Vector.
Questa libreria, come annuncia anche il nome, ci permette di creare un vettore facilmente e senza toccare nessun puntatore, a questo penserà tutto lui.
Ora, ragionando, cos'è una matrice? La matrice ovviamente può essere intesa come un vettore che all'interno di una sua cella ha un altro vettore, quindi aiutandoci con la struttura citata sopra, potremmo usare un Vector di Vector per avere così la nostra matrice (ovviamente dinamica) e senza aver toccato nessun puntatore direttamente.

Passiamo ora alla pratica, di seguito è riportato il codice di questa struttura opportunamente commentato per non destare altri dubbi.

Codice:

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int r, c;

    cout<<"inserisci righe e colonne"<<endl;
    cin>>r>>c;

    vector<int> riga(c);
    vector<vector<int> > matrice;

    for(int i=0; i< r; i++)
    {
        for(int j=0; j< c; j++)
            cin>> riga[j];

        matrice.push_back(riga);
    }

   //funzione di stampa
    for(int i=0; i< r; i++)
    {
        for(int j=0; j< c; j++)
            cout<<matrice[i][j];

        cout<<endl;
    }

return 0;
}

Spiegazione:

    vector<int> riga(c);
    vector<vector<int> > matrice;

In questo pezzo noi stiamo dichiarando un vettore chiamato riga e abbiamo allocato c posizioni vuote dove c è il numero di colonne lette da input.
Il secondo invece è proprio la nostra matrice che quindi sarà un vector di vector di interi (in questo esempio) e che quindi dovrà contenere un numero n di righe.

    for(int i=0; i< r; i++)
    {
        for(int j=0; j< c; j++)
            cin>> riga[j];

        matrice.push_back(riga);
    }

Questo pezzo invece è la vera e proprio lettura della matrice che viene eseguita con 2 indici, ovviamente, e nel ciclo più interno, noi leggiamo una a una le posizioni della nostra riga che abbiamo dichiarato prima.
Quando questo ciclo sarà terminato avremo quindi una riga letta e quindi pronta per diventare la prima (oppure la ennesima) riga della nostra matrice.
Per inserire quindi la nostra riga nella matrice basta usare la funzione di questa libreria che si chiama .push_back( <tipo di dato scritto nella dichiarazione>) ,questa funzione viene invocata sull'oggetto in cui dobiamo inserire un elemento, nel nostro caso la invochiamo sulla nostra matrice che a come abbiamo dichiarato prima è un vettore che accetta vettori e quindi questo inserimento andrà a buon fine inserendo tra le parentesi il nome dell'oggetto da aggiungere, nel nostro caso riga.

Ecco fatto dopo aver creato la nostra matrice questa potrà essere usata come una normale matrice statica con l'accesso per doppie parentesi quadre [n][m] , quindi l'utilizzo verrà più che immediato.

OverWolf - Stay in the game

2011-12-22T05:35:00.000-08:00

Killstreak negli FpS, Drop Epici nei Mmorpg, Livello degli fps di gioco... bhè se capite almeno una di queste frasi siete un giocatore Pc proprio come il sottoscritto.

Quante volte vi è capitato, magari durante una partita, di voler controllare la mail o magari una semplice occhiata al socialnetwork di fiducia e quindi di dover ricorrere al fastidiosissimo Alt+Tab?

Milioni di volte... questo comando tuttavia alla lunga può risultare scomodo visto che molti pc impiegano molto tempo a riaprire la finestra di gioco una volta messa in background.

Ma ecco che ci viene in aiuto un piccolo programmino[davvero minuto... pensate l'istaller pesa appena 50 Mb] dal nome intrigante: OverWolf, pensato apposta per giocatori accaniti che non possono fare a meno della loro partita quotidiana.

Lo scopo del programma altro non è che riunire in un interfaccia intuitiva e piacevole alla vista tutti i comandi sopracitati e molto altro ancora. Essendo ancora un programma in betatesting devo dire che dopo una piccola esperienza personale il programma risponde egregiamente a quasi tutte le richieste, che sia la semplice gestione di Teamspeak [indispensabile per coordinare gilde clan e tutto quello che riguarda il multiplayer] o la più complicata registrazione di gameplay che impone il più delle volte un programma esterno.

Il piccolo lupacchiotto rosso è predisposto per essere collegato a quasi tutto il mondo dei videogiochi pensati per pc include:

- un piccolo browser

- una app per i principali socialnetwork [facebook, twitter e Msn ad esempio]

- un collegamento diretto con Skype

- un pratico indicatore per gli fps [ottimo per chi ricerca il classico compromesso tra potenza e grafica]

- un collegamento con la chat della piattaforma Steam

- una app per Youtube

- una funzione di registrazione di video [postabili immediatamente sul web]

e molto altro ancora ancora tra cui la gestione di mail.

Unico neo? ancora non tutti i giochi supportano il comodissimo OverWolf tuttavia il sito degli sviluppatori [http://www.overwolf.com/] ha messo a disposizione un post dove i giocatori più fedeli possono richiedere una versione del programma adatta al gioco dei loro sogni.

Eliminare pubblicità su YouTube

2011-12-17T13:25:00.000-08:00

stanchi delle noiose pubblicità su youtube?? Volete vedere i vostri video preferiti in santa pace??

Da oggi si può con adBlock!

Basta infatti scaricare gratuitamente questo semplice addon che salterà automaticamente tutte le noiose pubblicità. AdBlock è disponibile sia per google chrome che per firefox in versione plus è semplicissimo da installare e non ha bisogno di alcuna modifica una volta installato infatti si avvierà da solo in automatico e eliminerà tutti gli annunci pubblicitari contenuti in molte pagine web con conseguente risparmio di banda.

Link del download per FireFox: qui
Link del download per Chrome: qui

Il primo bug

2011-12-12T11:46:00.001-08:00

Il noto termine 'bug' in informatica indica un comportamento non previsto di un programma, che porta ad errori e malfunzionamenti del software. Ma come si spiega l'uso di questo termine? 'Bug' in inglese significa insetto, ed è proprio questo termine che sta alla base di questa curiosità: si dice che nel 1947 nell' università di Harvard, fu trovato il motivo del malfunzionamento del computer Mark II: era proprio un insetto che si era incastrato tra i circuiti. Così, nel registro del computer fu annotata la frase

«1545. Relay #70 Panel F (moth) in relay. First actual case of bug being found»

Da queste parole, però, si può comprendere che il termine bug era probabilmente già stato usato per indicare un problema tecnico, si dice che fu Edison, intorno al 1870, a farne il primo uso.

Fonti : wikipedia, c++ for everyone (Cay Horstmann)

Malato... Terminale [Parte 4]

2011-12-08T03:35:00.001-08:00

Nella quarta parte di "Malato...Terminale" vedremo come utilizzare il simbolo di pipe, gestire l'input e l'output e ordinare semplici file.

Nel terminale una pipe è rappresentata dal simbolo " | ", che funge da collegamento tra due istruzioni, precisamente serve per collegare il risultato dell'espressione precedente, con quella che la segue. Un utilizzo immediato della pipe è il contatore di file presenti in una directory. Creiamo una directory Prova e popoliamola con 3 file mediante il comando Touch. Dopodiché digitiamo:

ls | wc -l

Il comando wc sta per word counter e, come potrete vedere dal risultato di questo comando, restituisce il numero dei file contenuti nella nostra cartella. Praticamente il comando ls "restituisce" i file che, mediante la pipe, vengono "passati" al comando wc, che li conta.

Nell'immagine vengono usati più comandi legati da &&: questo simbolo, in programmazione, corrisponde all'operatore logico "AND". L'operazione che segue la prima viene effettuata se e solo se la prima ha avuto successo. Un'altro simbolo è rappresentato con due pipe "||", che nel terminale è usato per generare la seconda istruzione se la prima non ha avuto successo .

Ora vediamo come utilizzare gli input e gli output nel terminale.
Esaminiamo il comando cat: questo comando serve per mostrare sullo schermo il contenuto di un determinato file.

Questo avviene perché l'output di default del terminale è lo schermo stesso, così come l'input standard è la tastiera. Proviamo a modificare l'output: scriviamo il comando cat seguito dal segno > e dal nome di un file. Nel mio esempio

cat > KnightMovesBFSGrafi.cpp

Nel prompt che vi si presenterà dovreste scrivere qualsiasi cosa vogliate, terminando con control-c.
Se ora provate a leggere quel file, tramite cat NomeFile, ritroverete quello che avete scritto.
Notate che il contenuto primordiale del file è stato cancellato, quindi usate questo comando per scrivere in un file vuoto non per aggiungere nuove righe!!

Dalla foto notate che la riga in cui compare il control-c non viene scritta, quindi il comando per uscire va scritto in una riga vuota.
Per poter scrivere stringhe in modo tale che siano "appese" al nostro file, senza cancellare nulla, basta usare il comando >> anziché >.

Anche l'operatore di input può essere cambiato (ridirezionato) mediante l'operatore <. Possiamo creare uno stream di input che proviene da un file scelto da noi. Proviamo un esempio molto semplice ed efficace: vogliamo scrivere tutte le nostre spese in un file con i prezzi e i nomi degli oggetti comprati. Di volta in volta immettiamo nuovi prezzi con a fianco il nome del prodotto mediante l'uso di cat > nomeFile. Ora vogliamo ordinare il tutto per prezzo minore, controllando quali sono state le nostre spese meno care. Bene ora possiamo utilizzare il comando:

sort < ProvaA > ProvaB

Dove il file ProvaA contiene tutte le nostre spese alla rinfusa, così come sono state immesse e ProvaB è un file vuoto. Quando la shell ci restituisce il prompt dei comandi, digitiamo
cat ProvaB
Ecco qui tutte le nostre spese ordinate in modo crescente!

Il terminale ordina prova A (comando sort < ProvaA) dato che l'input non è più la tastiera ma il file nominato "ProvaA". Dopodiché tutto il file, ordinato, va come output in ProvaB e dunque viene scritto lì. Se digitate su terminale "man sort" si aprirà la pagina del manuale integrato UNIX che vi spiegherà la sintassi del comando e le varie opzioni applicabili.
Ad esempio se vogliamo partire da un campo (in questo caso un campo corrisponde ad una colonna), anziché dal primo campo scritto, basta far seguire il sort da due numeri:
+n -m;
n >> verrà preso il primo carattere della n+1 colonna (o campo);
m >> determina il carattere finale, preso alla m-esima colonna (o campo);
Nel nostro esempio, ordiniamo gli acquisti per nome. Basterà fare:

sort +1 -2 < ProvaB > ProvaC

+1 --> Dato che la prima colonna del nome è il secondo campo (dunque con il nostro +1 il terminale si prende il primo carattere della colonna numero n+1 = 2)
-2 --> L'ultimo carattere è quello dalla seconda colonna, dunque -2.
Il terminale ordinerà in base all'ordine comune delle lettere, dalla a alla z, partendo dal primo carattere della seconda colonna (indicato con il +1) e finendo all'ultimo della stessa (indicato come -2).

Se volessimo raggruppare i campi in base a delimitatori diversi dallo spazio, che è il delimitatore di default, basta aggiungere il flag "-t[delim]" ad esempio creiamo un file con dei dipendenti nel formato descritto in foto;

scrivendo:
sort -t: +1 -2 ProvaD
avremo gli impiegati ordinati per matricola, dato che ora il terminale non conta più gli spazi come campi ma li dividerà con il delimitatore inserito. (nel nostro caso ':').

Link delle parti precedenti:

Malato...Terminale parte prima: qui

Malato...Terminale parte seconda: qui

Malato...Terminale parte terza: qui

Nella quinta parte vedremo l'uso del comando grep e un'anteprima sui permessi.

Codice Sorgente di Doom 3

2011-11-25T13:04:00.001-08:00

E' da un paio di giorni che circola in rete il codice scritto in C++ di questo famosissimo gioco...
Infatti la id Software ha rilasciato il codice sorgente in rete, permettendo agli utenti di compilarlo e "analizzarlo" a proprio piacimento. Seguono il link per scaricare il codice sorgente (1) e un sito che ho trovato, forse un pò datato, con varie informazioni sullo sviluppo di Doom 3 e Quake 4 (le loro SDK per la precisione) (2).

(1) Download Source Code

(2)SDK info

Filesharing senza limiti con Wetransfer

2011-11-01T05:00:00.000-07:00

Da sempre la condivisione di file (specialmente di grosse dimensioni) è stato un problema per tutti coloro che non avendo la possibilità di scambiarsi file manualmente avevano la necessità di farlo via internet.
Fino ad oggi servizi di file hosting come Megaupload (www.megaupload.com), SkyDrive (skydrive.live.com) o Dropbox (www.dropbox.com) hanno permesso (parzialmente) di risolvere tale problema. molte però, ad oggi, le limitazioni di tali servizi; esempi sono i prezzi e le limitazioni per inviare file a più utenti ed in particolar modo il fatto che tutti avessero un tetto massimo per le dimensioni dei file... Ebbene molti hanno pensato di usare programmi come hjsplit per dividere i file in parti più piccole e consentite dal servizio di file sharing ma pensate alla scomodita di caricare singoli pacchetti ad uno ad uno nel caso di un file di oltre 1GB.

Wetranfer (www.wetransfer.com) è un servizio internet TOTALMENTE GRATUITO che non necessita neppure di registrazione (e che nonostante tutto ciò è sicurissiomo grazie all'adozione del protocollo HTTPS) che ci permette di inviare (anche ad utenti multipli) file di dimensioni fino a 2GB... Come?
Semplice: il sito web è composto di un unica semplice ed intuitiva schermata dove basterà inserire il file da inviare (o i file grazie all'opzione di inserimento multiplo), l'indirizzo e-mail del destinatario (o dei destinatari, distanziando i vari indirizzi con uno spazio), la nostra e-mail e volendo anche un messaggio opzionale, et voilà il gioco è fatto :)

Cosa aspettate a provarlo??

Tecnica dell'Hashing Doppio

2011-10-29T07:23:00.000-07:00

L'hashing doppio fa parte dei tipi di funzione che possiamo usare per gestire una tabella hash con indirizzamento aperto..
Una delle tante tecniche di per gestire le collisioni in delle tabelle hash prevede l'utilizzo dell'indirizzamento aperto, che si basa su un'idea molto semplice: occupare i posti rimasti vuoti. Mentre con le liste di collisione gestiamo le chiavi che mirano ad una stessa cella dell'array aggiungendole in una opportuna lista (di chiavi) corrispondete alla cella in questione, la tecnica dell'indirizzamento aperto mira a fare occupare una cella del nostro array non ancora occupata da un'altra chiave, anche se non è la cella che spetta alla chiave inserita. Il tutto non viene fatto in modo casuale, ma secondo un preciso algoritmo(presente nei metodi di inserimento e di ricerca) che fa spostare la destinazione della nostra chiave, in un'altra; se quest'altra è vuota allora la chiave viene memorizzata, altrimenti il processo reitera fin quando non si memorizza la chiave o si ispeziona tutto l'array, scoprendo che è pieno (per andare all'articolo dell'indirizzamento aperto clicca QUI)
Tra le varie tecniche dell'indirizzamento aperto vi è l'hashing doppio, che fa dipendere l'algoritmo che genera la nuova posizione della chiave da una funzione hash. Viene denominato hashing doppio dato che, se usiamo tabelle hash, si sottintende che stiamo usando una funzione hash per smistare la nostra chiave e dato che facciamo dipendere il riallocamento in caso di collisione da un'altra funzione hash, le funzioni diventano due.
Passiamo ad un esempio: h(f) è la nostra chiave hash applicata su f, una parola. Definiamo la funzione hash:

La funzione in pratica somma il valore ascii di ogni lettera che forma la parola f e poi ne fa il modulo m, dove m è la dimensione della tabella. Nella formula X sono le lettere che vanno dalla posizione 0 alla posizione dim-1 della nostra parola.
Ad esempio con m=11 e f = ANNA avremo:
A=65 +
N=78 +
N=78 +
A=65
= 286 = 0 (mod 11)

Questa funzione hash ha restituito 0 così potremo assegnare la voce "ANNA" nella posizione 0 della nostra tabella hash. Ora se volessimo inserire NANA, avremo lo stesso risultato. Se le collisioni vengono gestite mediante liste di collisione metteremo semplicemente NANA in coda nella lista presente nella tabella hash alla posizione 0.
Proviamo a gestire la collisione con l'indirizzamento aperto e in modo particolare con l'hashing doppio. Un doppio hashing è definito in genere da questa formula:

mod m

Ho indicato con H la funzione di hashing doppio che, come vedete, opera sia su f che sull'indice i. Essa è composta dalle due funzioni hash h1 e h2. In questo modo, se due chiavi collidono si andrà ad occupare un posto libero nella struttura, andando a scandirla. Ora definiamo le chiavi hash h1 e h2:

Cambiamo la dimensione a 21 o qualsiasi numero che preferite, proporzionato in modo opportuno alla quantità di dati da inserire, e facciamo dipendere la funzione hash h2 dalla prima, cambiando il modulo (da modulo m andiamo a modulo m-1) e addizionando 1 al risultato finale di questa funzione.

Inserendo la parola ANNA:

(286 = 13 mod 21)

Dato che all'inserimento di NANA, il posto è già occupato da ANNA, viene incrementato l'indice i della funzione hashing doppio che da 0 passa a 1 (controlla l'algoritmo dell'indirizzamento aperto QUI) avendo così:

h1=13 (286 = 13 (mod 21) );

h2=14 (13 (mod 20) + 1);

H=6 (13+14 = 27 = 6 (mod 21) );
nella chiamata di funzione con i che vale 1.

E' stato, così, assegnato un nuovo posto alla parola NANA, passando in rassegna le celle ancora disponibili risultanti dalla funzione Hashing Doppio.

Metodo dell'indirizzamento aperto per le Tabelle Hash

2011-10-29T07:01:00.000-07:00

Un metodo per gestire le collisioni quando si ha a che fare con le tabelle hash è chiamato indirizzamento aperto. Al contrario delle liste di collisioni che mirano a memorizzare più oggetti aventi le stesse celle di destinazione in un'unica cella mediante delle liste, il metodo dell'indirizzamento aperto, in caso di collisione di due oggetti, scansisce la tabella mediante un indice i...
La scansione dipende dal metodo utilizzato, come vedremo in seguito. Un algoritmo generico per le Tabelle Hash implementate con l'indirizzamento aperto è il seguente:

classe TabellaHashAperta
dati:
vettore v di dimensione dim in cui ogni cella contiene una coppia (dato,chiave)
da implementare:
funzione f che determina il tipo di indirizzamento usato
operazioni elementari:
insert(elemento e,chiave k)
for i=0 to dim-1 do
if(v[f(k,i)].elemento=null) then
v[f(k,i)]<-----(e,k)
return
errore tabella piena //se non esco mai con return

search(chiave k)----->elemento
for i=0 to m-1 do
if(v[f(k,i)].chiave=k)then
return v[f(k,i)].elemento
return null //non ho trovato l'elemento con la chiave k

L'indirizzamento aperto (e quindi la funzione f(k,i) ) può essere di vari tipi:

Scansione lineare: definita da tale che i sia compresa tra 0 e minore di dim.
Scansione quadratica: definita datale che i sia compresa tra 0 e minore di dim.
Hashing doppio: definito da mod dim. Con h1 e h2 due funzioni hash.