9 novembre 2007 par Yohann CIURLIK
Prologin est le concours national d’informatique destiné aux étudiants (moins de 20 ans. Des épreuves d’algorithmiques réparties sur 36 heures.
L’inscription est ouverte jusqu’au 6 Janvier 2008 au soir.
Les trois étapes
Le questionnaire de sélection permet de se qualifier pour les demi-finales. Il consiste en deux parties : la première est un questionnaire de culture générale informatique, tandis que la seconde est une sélection de cinq problèmes algorithmiques de difficulté croissante. Il est possible de soumettre son questionnaire soit par courrier papier, soit directement sur le site.
Les demi-finales permettent de sélectionner les 100 finalistes. L’épreuve dure une journée, et se déroule un samedi, au mois de Janvier ou Février. Les candidats sont répartis en dix sessions, dans différents centres d’examen sur toute la France. L’évaluation se fait selon trois aspects : une épreuve papier sur un problème d’algorithmique, une épreuve machine formée de plusieurs exercices indépendants, et un entretien.
La finale se déroule sur trois jours à Paris, généralement mi-avril. Il s’agit de programmer l’intelligence artificielle d’une sorte de jeu, en seulement 36 heures. Les programmes des candidats sont évalués en s’affrontant les uns contres les autres. C’est aussi une occasion unique de rencontrer d’autres passionnés d’informatiques, le tout dans une ambiance joyeuse et décontractée.
J’ai malheureusement dépassé l’âge pour ce genre de challenge, c’est bien dommage! A quand les concours pour les plus anciens (moins de 30 ans) ?
17 janvier 2007 par Yohann CIURLIK
L’algorithme Aho-corasick de recherche de mots dans un texte est l’algorithme utilisé dans des commandes UNIX telles que GrepL’algorithme d’Aho-Corasick est un algorithme de recherche de chaîne de caractère (ou motif) dans un texte dû à Alfred Aho et Margaret Corasick et publié en 1975. L’algorithme consiste à avancer dans une structure de données abstraite appelée dictionnaire qui contient le ou les mots recherchés en lisant les lettres du texte T une par une. La structure de données est implantée de manière efficace, ce qui garantit que chaque lettre du texte n’est lue qu’une seule fois. Généralement le dictionnaire est implanté à l’aide d’un trie ou arbre digital auquel on rajoute des liens suffixes. Une fois le dictionnaire implanté, l’algorithme a une complexité linéaire en la taille du texte T et des chaînes recherchées.Lien vers wiki. Vous trouverez les sources de mes trois versions d’aho-corasick et d’un générateur de texte aléatoire en langage C pour effectuer des tests.Trois versions différentes:
- Matrice de transitions
- Liste d’adjacence
- Matrice pour la racine et liste d’adjacence pour les noeuds de l’arbre
Sources
N.B. 1:Les programmes sont pleins de petits bugs mais fonctionnels. Si vous avez des questions, n’hesitez pas à les poser sur mon forum.N.B. 2: Vous remarquerez dans les sources que j’ai evité l’utilisation de la fonction realloc du C qui posée problèmes.J’ai donc utilisé des valeurs assez importantes dans les malloc pour éviter les réallocations mémoires. Je ne doute pas que cette façon de faire n’est pas la meilleur, cela dit, si vous le souhaitez, vous pouvez modifier les sources à votre convenance.
