Abstract FR:

Les phenomenes de seuil dans une structure aleatoire ont ete mis en evidence par erdos et renyi lors de leur etude de la taille des composantes connexes dans le modele de graphe aleatoire independant. De tels phenomenes ont pu etre mis en evidence pour d'autres problemes d'informatique theorique et sont lies aux transitions de phase existants en physique statistique. Dans cette these nous nous interessons a l'approximation de la fonction du seuil de satisfaisabilite d'une formule aleatoire sous forme 2-cnf sur un variable. Soit e fixe, on considere le rapport entre le nombre de clauses m de la formule et le nombre de variables n. Il a ete montre par chvatal et reed et par goerdt que lorsque ce rapport est inferieur a 1e alors la formule aleatoire est presque surement satisfaisable tandis que lorsque ce rapport est superieur a 1 + e, la formule est presque surement insatisfaisable. Nous donnons ici des bornes pour la valeur du rapport m/n en fonction d'une puissance de n. La borne inferieure est obtenue en ameliorant une preuve due a goerdt tandis que la borne superieure resulte d'une analyse d'algorithme a l'aide d'arbres de galton-watson. Nous etudions aussi les composantes fortement connexes dans le graphe aleatoire oriente et en particulier la taille de la composante geante. En effet, lorsque suffisamment d'aretes ont ete ajoutees, karp a montre que l'on assiste avec grande probabilite a l'apparition soudaine d'une composante fortement connexe de taille lineaire. Nous ameliorons les bornes donnees par karp concernant la taille de cette composante geante en utilisant des arbres de galton-watson dans une analyse d'algorithme.