Saturday, March 31, 2012

baby problem solving

L'altro giorno al CNR un prof propose a me e colleghi un problema di conteggio assegnato al test di ammissione alla triennale in Matematica della Normale di Pisa:
Dato l'alfabeto {A,B,C,D,E,F}, quante sono le stringhe di 6 lettere contenenti due A consecutive?
La prima soluzione che mi venne presto in mente fu di usare una catena di Markov a tre stati:

  • non ho ancora scritto due A consecutive e l'ultima lettera scritta non è A;
  • non ho ancora scritto due A consecutive e l'ultima lettera scritta è A;
  • ho già scritto due A consecutive.
Scritta la matrice di transizione $T$ e calcolata $T^6$ si ottiene in entrata $T(1,3)$ la probabilità di $\phi$ avere una stringa contenente due A consecutive. Aver capito che cosa significa che "la probabilità è una misura" significa trovare ovvio che il numero cercato è $\phi \times 6^6$. Problem? :)

Il problema era che si stava evidentemente usando un cannone per ammazzare mosche, e con fatica dato che c'erano un pochetto di conti in più di quanto ci si aspetterebbe da un test di problem solving, e non di brute-computing. In metro chiacchierando con l'amico polacco arriva il "ma che idiota!": basta usare il principio di inclusione-esclusione con gli eventi:

  • "la prima e seconda lettera sono due A"
  • "la prima e terza lettera sono due A"
  • blablabla
  • "la quinta e sesta lettera sono due A"
Concettualmente ora era quasi ammissibile per un buon cervello fresco di liceo, ma ancora c'era la puzza di "calculemus!".

Poi la sera, leggendo la soluzione di un problemino di Teoria dei Codici anch'esso assegnato alla Normale di recente, mi viene in mente una soluzione ricorsiva:

$\\ \text{Indicando con } a_n \text{ le stringhe di } n \text{ lettere NON contenenti due A consecutive,} \\ \text{e con } a_n^A \text{ e } a_n^{\neg A}\text{ le stringhe NON contenenti due A consecutive che } \\ \text{rispettivamente terminano per A e non terminano per A, è facile vedere che:} \\ a_n=a_n^A+a_n^{\neg A} \\ a_n^A=a_{n-1}^{\neg A} \\ a_n^{\neg A}=5a_{n-1} \\ \text{Da cui si ricava immediatamente che } a_n= 5(a_{n-1}+a_{n-2}) \\ \text{e ''srotolando'' la ricorsione ad albero si ottiene facilmente } \\ a_6=5^4(a_2+a_1)+5^3(3a_2+2a_1)+5^2a_2$

Non ho ancora avuto la spigrizia di cercare la soluzione ufficiale al problema tra i test passati.

Tuesday, March 27, 2012

La probabilità è un'intuizione (solitamente sbagliata)


Dal Mitzenmacher:
Exercise 1.6: Consider the following balls-and-bin game. We start with one black balland one white ball in a bin. We repeatedly do the following: choose one ball from thebin uniformly at random, and then put the ball back in the bin with another ball of thesame color. We repeat until there are n balls in the bin. Show that the number of whiteballs is equally likely to be any number between 1 and n-1.
Facile coi conti, molto meno con la fantasia.

Wednesday, March 21, 2012

Prima vera...

Domenica il prof mi manda una mail e il giorno dopo, lunedì, mi invita a chiarirmi un po' le idee: il tempo vola e non è il caso di andare a zonzo. 
Il corso di Sistemi di Agenti lo saluto in virtù di un più costruttivo Algoritmi e Strutture Dati 2, e rinuncio a seguire Information Retrieval abbandonando l'indirizzo di data mining per farmi le ossa di un algoritmista che sa il fatto suo. 

Dunque, le mie bibbie attuali: 
  • Algorithm Design - Eva Tardos, Jon. Klemberg;
  • Probability and Computing: Randomized Algorithms and Probabilistic Analysis -Michael Mitzenmacher, Eli Upfal;
  • EXPANDER GRAPHS AND THEIR APPLICATIONS - SHLOMO HOORY, NATHAN LINIAL, AND AVI WIGDERSON.

Monday, March 19, 2012

Dovrei ragionare in modo booleano. Forse.

La seconda settimana di lezione è andata.
Sto seguendo i seguenti corsi:

  • Sistemi di agenti (multiagent systems)
  • Analisi di reti
  • Teoria della sicurezza e crittografia
  • Inferenza statistica e teoria dell'informazione
  • Information mining
Che nel gergo locale sono SA, AR, TSC, ISTI e IM. 
Un piatto prelibato. 


Saturday, March 17, 2012

bit generation

Molto tempo che non scrivo, ma non si pensi che sia stato un blogger negligente.
Ho accumulato tanta roba di cui parlare.
Nel mentre, il mio primo semestre da "computer scientist" è cominciato, portando conferme di gioia alla mia scelta eretica.
Forse la prima cosa che sto avendo a cuore è di colmare la profonda ignoranza cui da anni desidero rimediare, ovvero saper esaustivamente rispondermi alla domanda "che cos'è Internet?".
Finito poco fa di leggere la pagina sull'OSI model di Wikipedia (che sotto saggio consiglio è ottimo libro di testo per capirci qualcosa), con una dantesca visione dei livelli della rete in testa, posto qui una snapshot del web dal progetto Opte.