Activity Log Manager for Zeitgeist released!

On behalf of the Activity Log Manager team and the Zeitgeist Project, I am happy to announce the first release of Activity Log Manager (0.8.0), a user interface for managing Zeitgeist blacklists, deleting recent events as well as temporarily pausing the logging.

Grab it while it's hot. Note that you'll need Zeitgeist 0.8.0 (or later) for it to work. If you're an Ubuntu user you can get packages from our PPA; I've also uploaded it to Debian.

I'd also like to use this chance to thank Collabora for sponsoring my (and Seif's) work on Zeitgeist!

Zeitgeist 0.7.1 “Made in Aarhus” released!

On behalf of the Zeitgeist team I am proud to announce the release of Zeitgeist 0.7.1 "Made in Aarhus". This is a minor release before 0.8.0 (which will be the first one introducing storage awareness).

What is Zeitgeist?

Zeitgeist is a service which logs the users's activities and events, anywhere from files opened to websites visited and conversations, and makes this information readily available for other applications to use. It is also able to establish relationships between items based on similarity and usage patterns.

The Zeitgeist engine is a user-level service and does not provide a GUI. It is intended to support dedicated journalling applications and deep integration with other desktop components.

Where?

Downloads: launchpad.net/zeitgeist/+download (zeitgeist-0.7.1.tar.gz)

About Zeitgeist: zeitgeist-project.com
Wiki: wiki.zeitgeist-project.com

See also Zeitgeist Datahub, GNOME Activity Journal and the repository for additional Zeitgeist data-sources. You may as well like Sezen.

News since 0.7.0

Engine:

 - Expose property information in the D-Bus introspection output.
 - Mention column names explicitly when inserting events, for compatibility
   with the upcoming 0.8 release.

Python API:

 - Expose DataSourceRegistry's enabled status in a callback.
 - Automatically reconnect to Zeitgeist if the connection is lost when using
   methods asynchronously (so far this only happened for synchronous calls).
 - Reinstall all active monitors upon reconnection (LP: #673008, #727226).
 - Fix a (harmless) race condition requesting the bus name (LP: #732015).

Overall:

 - Added new event interpretation types: AcceptEvent, DenyEvent and ExpireEvent.
 - Include NCO in the generated ontologies.
 - Better ./configure check for python-rdflib.
 - Update the manpage to document exit codes.

Thanks to everyone who contributed to this release, and since I hadn't blogged about it before, also to everyone who made the Zeitgeist Hackfest in Aarhus possible, including our sponsors:

                         

On Intel AppUp, the ExoPC Slate, MeeGo and Ubuntu 10.10

Introduction (Intel Rocks!)

Last Wednesday I attended the Intel AppUp Developer Day, a workshop where Intel employees presented the MeeGo stack and introduced Intel AppUp, a software center which will be shipping in netbooks/tablets/carputers/etc. There was also a live demo on how to design interfaces with QML and one of the Angry Birds creator said some words. Best of all, Intel was nice enough to give every participant a tablet!

MeeGo (really alpha!)

The ExoPC Slate came with Intel's new tablet version of MeeGo, which like its netbook counterpart seems to place great emphasis on social and multimedia uses, but it better suited for the touch screen. The system is still pre-alpha, though, and when I tried to use it lots of stuff failed to work. Asking about it at the MeeGo pavilion I was told to re-install the image, which solved some of the problems. Still, I don't really see myself using it at this point, so I decided to also put Ubuntu on it.

Installing Ubuntu

The installation went smooth; I got a message about the bootloader not being able to be installed, but I just ignored it and had no problems. I had already left half of the 64GB SSD empty when installing MeeGo, since it uses brtfs which Ubuntu can't resize yet. Of course, I had to plug in mouse and keyboard (I used a USB hub, since the tablet only has two USB ports and one is required for the installation media). Boot is somewhat slower than what I'd expect for an SSD, and sometimes shows some weird error messages which seem to have no effect.

One outstanding problem is that GRUB doesn't support the touch screen (and for that matter neither does it recognize my wireless keyboard), so if I want to change between Ubuntu and MeeGo I have to plug in a normal USB keyboard.

Getting the touch-screen to work (no multi-touch :()

The touch-screen didn't work out of the box either but required some fiddling. Basically, I had to open /etc/default/boot and change «GRUB_CMDLINE_LINUX_DEFAULT="quiet splash"» to «GRUB_CMDLINE_LINUX_DEFAULT="quiet splash usbhid.quirks=0xeef:0x72a1:0x40"» and run «sudo update-grub», otherwise touching the screen would invariably send the pointer to the top-left. And basically, that's it, now it's working using the free drivers!

However, the free drivers only support a single finger. There's also the option of using the proprietary hid_egalax driver, which is supposed to correctly support tracking two fingers (and it does in MeeGo), but I didn't have so much luck in Ubuntu and functionally I don't really see a difference between them. To install it I downloaded the eGalaxTouch tarball: eGalaxTouch-3.04.4912-32b-k26.tar.gz. Then uncompressed the file, executed the setup script and restarted the computer. This time the result wasn't so nice, since in addition to still not doing any multi-touch, the pointer was showing up in the wrong place and somehow now the touch-screen device shows up four times. The pointer problem was easy to fix, though, by running XXXX and calibrating the four "devices", so this basically left me just how I was with the free drivers.

Since with a single finger I have no way of triggering a right-click, I enabled the "secondary click when pressing primary button" accessibility option in the mouse preferences.

Final touch (pun intended?)

For typing I've installed "matchbox-keyboard" and placed a launcher for it in the top panel. Suggestions on better alternatives are welcome (especially if they show up automatically when I focus a text box).

Now something I could do to at least get a little bit of coolness factor is enabling single-finger scroll support in Chromium, by installing the chromeTouch extension (apparently there is also a similar extension for Firefox).

Finally, I disabled the key-binding for "open music player", since by default the Slate's touch hot-key had been assigned to it and it kept opening Rhythmbox every time I accidentally went over the hot-key.

References

To wrap up this post, here's some random pages which helped me on my way here:

Apunts d’Estructures de Dades i Algorismes: Programació dinàmica

1. Nombres de Fibonacci

L'algorisme trivial per al càlcul dels nombres de Fibonacci repeteix molts càlculs. Podem evitar-ho desant tots els valors que calculem en una matriu i cercant-los allà quan ens calguin abans de calcular-los un altre cop (memoization). Si només ens cal obtenir un sol nombre de Fibonacci, podem construir una versió iterativa de l'algorisme que eviti els càlculs sense utilitzar espai de memòria addicional.

2. Producte encadenat de matrius

[FIXME: imatge multiplicació de matrius]. Hem vist que per multiplicar dues matrius podem utilitzar l'algorisme escolar o l'algorisme d'Strassen. Amb el primer d'ells, cal calcular [latex]\theta(pqr)[/latex] productes escalars.

Si volem dur a terme una seqüència de multiplicacions, el nombre de productes escalars a fer canvia significativament segons com posem els parèntesis (el qual no té cap efecte sobre el resultat). Per exemple, amb tres matrius [latex]A_1 = 10×100[/latex], [latex]A_2 = 100×5[/latex] i [latex]A_3 = 5×50[/latex], l'operació [latex](A_1 \cdot A_2) A_3[/latex] resulta en [latex]10 \cdot 100 \cdot 50 + 10 \cdot 5 \cdot 50 = 7500[/latex] productes escalars. En canvi, l'operació [latex]A_1 \cdot (A_2 \cdot A_3)[/latex], amb les mateixes matrius, resultaria en [latex]100 \cdot 5 \cdot 50 + 10 \cdot 100 \cdot 50 = 75000[/latex] productes escalars.

Heus aquí el problema la multiplicació encadenada de matrius: on «posar» els parèntesis per poder dur a terme les multiplicacions amb el mínim nombre de productes escalars?

Per força bruta, amb [latex]n[/latex] matrius, les possibles formes de posar els parèntesis són igual al nombre d'arbres binaris amb [latex]n[/latex] fulles, el qual correspon a [latex]C_n = \frac{1}{n + 1}{2n \choose n} \approx \frac{4^n}{3^{n/2}}[/latex] ([latex]\small C[/latex] és el nombre de Catalan). Podem definir la següent funció per trobar el nombre mínim de productes escalars per multiplicar les matrius [latex]A_i[/latex], …, [latex]A_j[/latex]:

[latex]m(i, j) = \begin{cases}0 & i = j \\ min\left\{m(i, k) + m(k+1, j) + p_{i-1} \cdot p_k \cdot p_j\right\} & i < j\end{cases}[/latex]

Aquesta operació duplica càlculs → memorització! En resulta el següent codi C++ que triga temps [latex]\theta(n^3)[/latex]:

vector<vector<int>> mem(n+1, vector<int>(n+1, -1));
vector<vector<int>> tall(n+1, vector<int>(n+1, -1));
 
int m(int i, int j) {
    if (mem[i][j] != -1) return mem[i][j];
    if (i == j) return 0;
    int s = MAX_INT; // infinit
    for (int k = i; k <= j; ++k) {
        int x = m(i, k) + m(k+1, j) + p[i-1] + p[k] + p[j];
        if (x < s) {
            s = x;
            tall[i][j] = k; // resposta al problema de com multiplicar-les
        }
    }
    return m[i][j] = s;
}

També podem construir-ne una versió iterativa:

for (int i = 1; i <= n; ++i) mem[i][i] = 0;
for (int i = n; i >= 1; --i) {
    for (int j = i+1; j <= n; ++j) {
        int s = MAX_INT; // infinit
        for (int k = i; k <= j; ++k) {
            int x = mem[i][k] + mem[k+1][j] + p[i-1] + p[k] + p[j];
            if (x <= s) s = x;
        }
        mem[i][j] = s;
    }
}

3. Problema de la subseqüència comuna més llarga

Tenim dues cadenes X="abcbdab" i Y="bdcaba" i volem trobar la subseqüència comuna (per exemple, "bca") més llarga (en aquest cas, la més llarga és "bdab"). Definim [latex]m=|X|[/latex], [latex]n=|Y|[/latex], [latex]X'_i[/latex]=[latex]X_1[/latex]…[latex]X_i[/latex].

  • Si X i Y acaben igual: l'últim caràcter d'X (o Y) ha de ser l'últim caràcter d'LCS(X, Y).
    LCS(X, Y) = [latex]LCS(X'_{m-1}, Y'_{n-1}) \cdot X_m[/latex].
  • Si X i Y no acaben igual, pensem què passa amb LCS(X, Y).
    [latex]LCS(X, Y) = \begin{cases}LCS(X_{n-1}, Y) \\ LCS(X, Y_{n-1})\end{cases}[/latex] Quina de les dues? La més llarga.

Definim la funció [latex]l(i, j)[/latex] = llargada de l'LCS([latex]X'_i[/latex], [latex]Y'_i[/latex]).

[latex]l(i, j) = \begin{cases}0 & i = 0 \text{ o } j=0 \\ l(i-1, j-1)+1 & x_i = y_j \\ max\{l(i-1, j), l(i, j-1)\} & sin\acute{o}\end{cases}[/latex]

Apunts d’Estructures de Dades i Algorismes: Les classes de problemes P i NP

Classes de problemes – P i NP

Entrades Problemes Classes de problemes (no excloents)
[latex]x[/latex] [latex]\pi[/latex] P Coneixem algorismes amb temps pitjor polinomial (o millor) per a decidir el problema.
NP Coneixem algorismes en temps polinòmic indeterminista per a verificar si una solució és correcta.
Exemples de problemes que estan en NP:
  • HAM – és difícil trobar un cicle Hamiltonià en un graf (backtracking), però donada una sentència de vèrtexs és fàcil comprovar si és una solució.
  • Element mínim.
  • TSP (problema del viatjant de comerç).
  • Colorabilitat.
  • Quadrat llatí.
  • Sudoku.
Teorema

[latex]P \subseteq NP[/latex]

Queda una pregunta clau: [latex]P = NP[/latex]?

Reducció

Siguin [latex]L_1 \le E_1[/latex] i [latex]L_2 \le E_2[/latex] dos problemes decisionals. Diem que [latex]L_1[/latex] es redueix a [latex]L_2[/latex] en temps polinòmic si podem trobar un algorisme polinòmic [latex]A: L_1 \rightarrow L_2[/latex], és a dir, que converteixi tota solució a [latex]E_1[/latex] en una solució d'[latex]E_2[/latex].

En altres paraules, una reducció en temps polinòmic d'[latex]L_1[/latex] a [latex]L_2[/latex] és un algorise [latex]R: E_1 \rightarrow E2 / \forall x \in E_1: x \in L1 \Leftrightarrow R(x) \in L_2[/latex].

Podem reduir, per exemple, el problema del graf hamiltonià (HAM) al problema del viatjant de comerç (TSP).

Teorema: Si [latex]L_1 \le_p L_2[/latex] i [latex]L_2 \in P[/latex], llavors [latex]L_1 \in P[/latex].

Un problema decisional [latex]L[/latex] és NP-hard si tot problema en NP es pot reduir a ell en temps polinòmic. [latex]L \in \text{NP-hard} \Leftrightarrow \forall L' \in NP, L' \le_p L[/latex].

Un problema és NP-complet si és NP-hard i es troba en NP.

Teorema:
[latex]L \in NP-hard, L \in P \Leftrightarrow P = NP[/latex].

Teorema:
[latex]\left\{\begin{array}{l}L_1 \in \text{NP-C} \\ L_2 \in NP \\ L_1 \hookrightarrow L_2\end{array}\right\} L_2 \in NP-C[/latex]

Teorema de Cook (~1970)
[latex]\small\text{CIRCUIT-SAT} \normalsize\in \small\text{NP-C}[/latex] (va ser el primer problema NP-complet).

El problema decisional CIRCUIT-SAT pren com a entrada un circuit amb [latex]n[/latex] entrades booleanes, una sortida i portes AND, OR i NOT i el que pregunta és, «hi ha alguna entrada del circuit que faci que la sortida sigui 1?».

Nota: Una possible solució donada per justificar que un problema decisional té solució s'anomena testimoni.

Solucions pràctiques per a problemes NP

  • Heurístiques.
  • Aproximacions.
  • Paral·lelisme, ordinadors quàntics…

El problema de l'aturada

A part de les classes de problemes P, NP i NP-C n'hi ha moltes d'altres, i una d'elles que cal mencionar és la dels problemes irresolubles: aquells que l'ordinador (o millor dit, una màquina de Turing) no pot solucionar.

Un exemple de problema irresoluble és el de l'aturada: donada la descripció d'un programa i el seu estat inicial, determinar si el programa, si l'executem, arribarà a completar-se o bé funcionarà fins la fi de l'eternitat. Podem veure-ho amb el següent programa d'exemple:

typedef String Programa;
typedef String Entrada;
 
// Funci&oacute; que retorna cert si el programa p, donada l&#39;entrada
// x, arriba a aturar-se
bool acaba(Programa p, Entrada x);
 
void vinga(Programa p) {
    // Entra en un bucle infinit si el programa p, donant-li com a entrada
    // el mateix codi del programa, arriba a aturar-se
    if (acaba(p, p)) while (true);
}

Si analitzem aquest programa i executem vinga(vinga) veiem que pot haver-hi dos casos:

  1. Que acabi – si acaba, vinga entra en el bucle i no acaba → contradicció.
  2. Que no acabi – si no acaba, vinga acaba → contradicció.

Així doncs, no es pot solucionar el problema de l'aturada.

 
Skip to toolbar