Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Fonctions totales : comment et pourquoi

Description

Cette séance de cours traite de l'efficacité des tables de hachage, de l'importance des fonctions totales dans la modélisation du code et de l'utilisation de relations bien fondées pour assurer la terminaison des fonctions récursives. Il couvre également le concept de points fixes et limportance des fonctions totales dans les cadres de preuve.

Source officielle

Concepts associés (32)

Fonction récursive

En informatique et en mathématiques, le terme fonction récursive ou fonction calculable désigne la classe de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique fini. En fait, cela fait référence à deux concepts liés, mais distincts. En théorie de la calculabilité, la classe des fonctions récursives est une classe plus générale que celle des fonctions récursives primitives, mais plus restreinte que celle des fonctions semi-calculables (ou partielles récursives).

Table de hachage

Une table de hachage est, en informatique, une structure de données qui permet une association clé–valeur, c'est-à-dire une implémentation du type abstrait tableau associatif. Son but principal est de permettre de retrouver une clé donnée très rapidement, en la cherchant à un emplacement de la table correspondant au résultat d'une fonction de hachage calculée en O(1). Cela constitue un gain de temps très important pour les grosses tables, lors d'une recherche ou d'un besoin d'accès aux données en utilisant la clé définie.

Computable function

Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do the job of the function, i.e. given an input of the function domain it can return the corresponding output. Computable functions are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines.

Fonction récursive primitive

En théorie de la calculabilité, une fonction récursive primitive est une fonction construite à partir de la fonction nulle, de la fonction successeur, des fonctions projections et des schémas de récursion primitive (ou bornée) et de composition. Ces fonctions constituent un sous-ensemble strict des fonctions récursives. Elles ont été initialement analysées par la mathématicienne Rózsa Péter. On s'intéresse aux fonctions définies sur l'ensemble des entiers naturels, ou sur les ensembles des -uplets d'entiers naturels, et à valeurs dans .

Fonction d'Ackermann

Dans la théorie de la récursivité, la fonction d'Ackermann (aussi appelée fonction d'Ackermann-Péter) est un exemple simple de fonction récursive non récursive primitive, trouvée en 1926 par Wilhelm Ackermann. Elle est souvent présentée sous la forme qu'en a proposée la mathématicienne Rózsa Péter, comme une fonction à deux paramètres entiers naturels comme arguments et qui retourne un entier naturel comme valeur, noté en général A(m, n).

Afficher plus

Séances de cours associées (44)

Analyse probabiliste: Paradoxe de l'embauche et de l'anniversaire

Explore l'analyse probabiliste dans les algorithmes, couvrant le problème de l'embauche et le paradoxe de l'anniversaire, ainsi que les tables de hachage et les fonctions.

Analyse des tables de hachage

Couvre l'analyse des tables de hachage, y compris les opérations de recherche et les collisions attendues.

Ingénierie des systèmes décentralisés: DHT de corbeille

Couvre le Chord DHT en ingénierie décentralisée des systèmes, en mettant l'accent sur la fiabilité, la redondance et l'entretien des structures.

Induction et récurrence : résumé

Couvre l'induction mathématique, les fonctions définies récursivement et les algorithmes itératifs pour la résolution de problèmes.

Mise en œuvre des ensembles : Hashing

Couvre la mise en œuvre des ensembles à l'aide du hachage et des opérations d'ensemble.

Afficher plus

Concepts associés (32)

Fonction récursive

Table de hachage

Computable function

Fonction récursive primitive

Fonction d'Ackermann

Afficher plus