Mes fiches d'informatique : tout confondu

Automates : vocabulaire

Automates normalisés standard

Constructions sur les automates

Automate minimal

Lemme de l'étoile

Grammaire algébrique

Grammaire et dérivations

Grammaire réduite équivalente

Plus courte dérivation

Un lemme sur les arbres

Lemme d'Ogden

Différentes formes de grammaires

Décider si Lg(S) est vide

Décider si T apparaît dans Lg(S)

Décider si le mot vide appartient à Lg(S)

Équivalence de non terminaux

Algorithme de CYK

Engendré par une grammaire implique reconnu par un automate à pile

Automates à pile

Automate à pile standardisé

Mode d'acceptation d'un automate à pile

Analyse lexicale

« Premier »

« Suivant »

Analyse LL(1)

Rationnel => LL(1)

Analyse LR(0)

Recherche naïve de motifs

Règle de Hörner

Algorithme de Rabin-Karp

Alignement local

Calcul d'un alignement local

Recherche de motifs

Opérations d'édition et alignement

Coût d'alignement et distance de Levenshtein

Calcul de la distance de Levenshtein et d'un alignement

Lien entre plus longue sous-chaîne commune et distance de Levenshtein

Calcul de la plus longue sous-chaîne commune

Hash consing = partage maximal

Logarithme étoile

Union-find

Consécutivité des nœuds dans un ABR

Complété d'un ABR

Temps moyen de recherche dans un ABR

Algorithme de Dijkstra

Une caractéristique des coupes

Algorithme d'unification

Complétude de la résolution

Résolution

Correction de la résolution

Exemples de preuves en déduction naturelle

Règles de la déduction naturelle

Tiers exclu en logique classique

Problèmes d'atelier

Jobshop à deux pieces par programmation dynamique

Calage à gauche et critères réguliers

Problèmes d'ordonnancement à une machine.pdf

Algorithme pour résoudre "gmax" sur une machine (Lowler sans précédence)

Un problème d'ordonnancement à une machine NP-complet

Détail de la preuve de correction de l'algo. de timing proposé par Garey Tarjan et Wilfong

Le problème "ULS" (uncapacited lot-sizing)

Enchères à un bien

Design : TEMPLATED, modèle Linear
Images : mes photographies du Jardin des plantes de Paris