Séance de cours

Le principe de Pigeonhole : bases et applications

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Dans cours

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics as diverse as mathematical reasoning, combinatorics, disc ...

Description

Cette séance de cours introduit le principe de Pigeonhole, indiquant que si k + 1 objets sont placés dans k boîtes, alors au moins une boîte contient deux objets ou plus. Il explore les applications du principe pour prouver que les fonctions ne sont pas individuelles et s'étend au principe de Pigeonhole généralisé. Des exemples illustrent comment le principe garantit des résultats spécifiques, tels que trouver des personnes nées dans le même mois ou sélectionner des cartes de la même couleur à partir d'un jeu.

Enseignant·e

Karl Aberer

Co-Founder of LinkAlong Sarl, 2017.Vice-president EPFL for Information Systems, 2012 –2016.Director of the Swiss National Centre for Mobile Information and Communication Systems NCCR MICS (mics.ch), 2005 -2012.Member of the Swiss Research and Technology Council SWTR, consulting the Swiss Federal government, 2004 - 2011.

Source officielle

Concepts associés (27)

Théorie des ensembles

La théorie des ensembles est une branche des mathématiques, créée par le mathématicien allemand Georg Cantor à la fin du . La théorie des ensembles se donne comme primitives les notions d'ensemble et d'appartenance, à partir desquelles elle reconstruit les objets usuels des mathématiques : fonctions, relations, entiers naturels, relatifs, rationnels, nombres réels, complexes... C'est pourquoi la théorie des ensembles est considérée comme une théorie fondamentale dont Hilbert a pu dire qu'elle était un « paradis » créé par Cantor pour les mathématiciens.

Théorie naïve des ensembles

Les ensembles sont d'une importance fondamentale en mathématiques ; en fait, de manière formelle, la mécanique interne des mathématiques (nombres, relations, fonctions, etc.) peut se définir en termes d'ensembles. Il y a plusieurs façons de développer la théorie des ensembles et plusieurs théories des ensembles existent. Par théorie naïve des ensembles, on entend le plus souvent un développement informel d'une théorie des ensembles dans le langage usuel des mathématiques, mais fondée sur les axiomes de la théorie des ensembles de Zermelo ou de Zermelo-Fraenkel avec axiome du choix dans le style du livre Naive Set Theory de Paul Halmos.

Fonction de compte des nombres premiers

En mathématiques, la fonction de compte des nombres premiers est la fonction comptant le nombre de nombres premiers inférieurs ou égaux à un nombre réel x. Elle est notée π(x) (à ne pas confondre avec la constante π). L’image ci-contre illustre la fonction π(n) pour les valeurs entières de la variable. Elle met en évidence les augmentations de 1 que la fonction subit à chaque fois que x est égal à un nombre premier. Soit l'ensemble des nombres premiers et un nombre réel.

Fonction arithmétique

En théorie des nombres, une fonction arithmétique f est une application définie sur l'ensemble des entiers strictement positifs et à valeurs dans l'ensemble des nombres complexes. En d'autres termes, une fonction arithmétique n'est rien d'autre qu'une suite de nombres complexes, indexée par N*. Les fonctions arithmétiques les plus étudiées sont les fonctions additives et les fonctions multiplicatives. Une opération importante sur les fonctions arithmétiques est le produit de convolution de Dirichlet.

Théorie des ensembles de Zermelo

La théorie des ensembles de Zermelo, est la théorie des ensembles introduite en 1908 par Ernst Zermelo dans un article fondateur de l'axiomatisation de la théorie des ensembles moderne, mais aussi une présentation moderne de celle-ci, où les axiomes sont repris dans le langage de la logique du premier ordre, et où l'axiome de l'infini est modifié pour permettre la construction des entiers naturels de von Neumann. Cette section présente les axiomes originaux de l'article de Zermelo paru en 1908, numérotés comme dans cet article.

Afficher plus

Séances de cours associées (64)

Catégories

Présente les catégories comme des collections d'objets avec des morphismes et des morphismes d'identité.

Théorie de l'ensemble : Opérations et fonctions

Couvre les opérations et les fonctions théoriques, y compris les injections et les surjections.

Fonctions et périodicité

Couvre les fonctions, y compris les fonctions paires et impaires, la périodicité et les opérations de fonction.

Théorèmes en analyse

Couvre le théorème de Meyers-Serrin en analyse, en discutant des conditions des fonctions dans différents espaces.

Fonctions réelles : Définitions et propriétés

Explore les fonctions réelles, couvrant la parité, la périodicité et les fonctions polynomiales.

Afficher plus

Concepts associés (27)

Théorie des ensembles

Théorie naïve des ensembles

Fonction de compte des nombres premiers

Fonction arithmétique

Théorie des ensembles de Zermelo

Afficher plus