Résultats contre-intuitifs pour les étudiants de premier cycle

14

Je recherche des exemples de résultats qui vont à l'encontre de l'intuition des gens pour une conférence grand public. Des résultats qui, s'ils étaient demandés à des non-experts "qu'est-ce que votre intuition vous dit?", Presque tous auraient tort. L'énoncé des résultats devrait être facilement explicable aux étudiants de premier cycle en cs / mathématiques. Je recherche principalement des résultats en informatique.

Quels sont les résultats les plus contre-intuitifs / inattendus (d'intérêt général) dans votre région?

Anonyme
la source
1
Le deuxième des liens de Sasho est un doublon, non?
Huck Bennett
Similaire mais pas le même. Je suis à la recherche de résultats intéressants et contre-intuitifs pour les étudiants de premier cycle en sciences humaines et non pour les chercheurs. Par exemple, IP = PSPACE ne serait pas une bonne réponse.
Anonyme
4
Pour des tailles d'entrée suffisamment grandes, la primauté peut toujours être décidée en moins de temps que le moyen le plus rapide connu pour avoir une chance non négligeable de factoriser un module RSA.

Réponses:

25

Pour un public général, vous devez vous en tenir à ce qu'ils peuvent voir . Dès que vous commencerez à théoriser, ils allumeront leurs téléphones portables.

Voici quelques idées qui pourraient être élaborées pour compléter des exemples:

  1. Il y a une surface qui n'a qu'un côté .
  2. Une courbe peut remplir un carré entier .
  3. Il existe des courbes de largeur constante autres qu'un cercle.
  4. Il est possible de colorier l'avion avec trois couleurs de telle sorte que chaque point de bordure soit une tri-bordure .

Si vous pouvez compter sur un peu de connaissances mathématiques, vous pouvez en faire plus:

  1. Il y a autant de nombres impairs que de nombres naturels.
  2. Il existe une fonction continue et nulle part différentiable .
  3. Il existe une fonction qui est discontinue à tous les nombres rationnels et différenciable à tous les nombres irrationnels.F:RR
  4. Le "paradoxe" de Banach-Tarski .

Pour les programmeurs, vous pouvez essayer:

  1. Les fonctionnalités impossibles : il y a un programme qui prend un prédicat p : stream → bool, où streamest le type de données de séquences binaires infinies, et retourne truesi et seulement si p αc'est truepour tous les flux α(c'est un nombre incalculable), et falseautrement.

  2. Il est possible de jouer au poker par téléphone de manière fiable, ce qui évite de tricher.

  3. Un groupe de personnes peut calculer leur salaire moyen sans que personne ne découvre le salaire d'une autre personne.

  4. Il existe un programme qui construit un arbre binaire T avec les propriétés suivantes:

    • l'arbre est infiniT
    • il n'y a pas de programme qui trace un chemin infini en T
Andrej Bauer
la source
le paradoxe banach-tarski (et les paradoxes associés) ont à voir avec les notions (et les manipulations) de l'infini, quelque chose que même les mathématiciens professionnels peuvent se tromper (ou être en désaccord beaucoup à ce sujet) :)
Nikos M.
4
D'accord, mais c'est le genre de théorème ourageux qui suscite l'intérêt des gens. Cela leur donne une secousse et leur fait douter de leurs propres intuitions sur l'infini.
Andrej Bauer
17

Une idée est quelque chose de simple à partir d' algorithmes de streaming . Le meilleur candidat est probablement l'algorithme majoritaire. Supposons que vous voyez un flux de nombres , l'un après l'autre, et que vous savez qu'un nombre se produit plus de la moitié du temps, mais vous ne savez pas lequel. Comment pouvez-vous trouver le nombre majoritaire si vous ne vous souvenez que dedeux nombres à la fois? La réponse est l'algorithme Misra-Gries.s1,,sn

À chaque pas de temps, vous stockez un nombre du flux et un compteur de fréquence f . Au début, vous définissez x sur le premier nombre du flux et initialisez la fréquence f à 1. Ensuite, chaque fois que vous voyez un nouveau nombre s i , vous vérifiez si x = s i . Si x = s i , augmenter f à f + 1 , sinon diminuer f à f - 1 . Si f = 0 , définissez x et fXFXFsjeX=sjeX=sjeFF+1FF-1F=0X sur sjeFretour à 1 . Après le dernier élément du flux, s'il y avait un élément majoritaire, il sera égal à .X

Une autre idée est le jeu bien connu pour illustrer les preuves de connaissance zéro . Je pense que cela est dû à Oded Goldreich et est similaire à la preuve de connaissance zéro pour l'isomorphisme des graphes.

Pour rendre la réponse autonome, voici le jeu. Supposons que vous vouliez convaincre votre ami daltonien que vous pouvez distinguer le rouge du vert. Votre ami a deux jeux de cartes et il sait qu'une pile est verte et l'autre rouge. Il fait ce qui suit sans que vous le voyiez: avec une probabilité de 1/2, il pioche une carte de chaque paquet, avec une probabilité de 1/4, il tire deux cartes du pont de gauche, et avec une probabilité de 1/4, il tire deux cartes du pont de droite . Puis il vous montre les cartes et vous demande si elles sont de la même couleur. Si vous n'êtes pas daltonien, vous pouvez bien sûr répondre correctement à chaque fois. Si vous êtes daltonien, vous échouerez avec une probabilité 1/2. Alors maintenant, si le jeu est joué 10 fois, la probabilité que vous puissiez gagner à chaque fois tout en étant daltonien est extrêmement faible.

Le coup de pied est que si votre ami savait que les deux jeux de cartes sont de deux couleurs différentes, mais ne savait pas lequel est rouge et lequel vert, il ne le saura toujours pas à la fin de cela! Donc en résumé:

  1. Il y a place pour le hasard dans les preuves.
  2. Vous pouvez convaincre quelqu'un que vous savez quelque chose sans lui donner aucune information à ce sujet.
Sasho Nikolov
la source
3
Outre Misra-Gries, je pense également que l' échantillonnage du réservoir est simple mais agréable.
Juho
1
@Juho je suis d'accord. Une question d'entrevue populaire pour démarrer :).
Sasho Nikolov
13

Le volume d'une sphère unitaire de dimension croît d'abord lorsque n croît ( 2 , π , 4 π / 3 , ) mais commence à diminuer pour n = 6 et finit par converger vers 0 lorsque n .nn2,π,4π/3,n=60n

Denis
la source
1
Et la raison en est la décision arbitraire de considérer les sphères de rayon unitaire, par opposition à un autre paramètre de longueur. En particulier, les volumes de sphères de diamètre 1 diminuent dès le départ.
Emil Jeřábek 3.0
Il existe de nombreux faits amusants et contre-intuitifs sur la géométrie dans les dimensions élevées. Par exemple, prenez l'hypercube de l'unité et inscrivez une sphère touchant tous les côtés. À quelle distance se trouve un coin de l'hypercube de la sphère? (Réponse: il diverge à fur et à mesure que la dimension augmente. Le rayon de la sphère est de 0,5 , mais la distance du centre au coin du cube est de 0,5 0,5 .)0,5n
usul
10

Un résultat contre-intuitif de la théorie de la complexité est le théorème PCP:

De manière informelle, indique que pour chaque problème A , il existe une machine de Turing randomisée efficace qui peut vérifier l'exactitude de la preuve (preuve d'appartenance à A ) en utilisant un nombre logarithmique de bits aléatoires et en ne lisant qu'un nombre constant de bits de la preuve. La constante peut être réduite à 3 bits. Par conséquent, le vérificateur aléatoire ne doit lire que trois bits de la preuve proclamée.NPAA

Mohammad Al-Turkistany
la source
Quelle est la référence pour "peut être réduit à 3 bits"?
Ryan
2
C'est ce que l'on appelle le théorème PCP de 3 bits (ou 3 requêtes) de Håstad, et cela nécessite de sacrifier l'exhaustivité parfaite
Joe Bebel
1
Vous trouverez ici de plus amples informations et la référence au document de Håstad: people.csail.mit.edu/madhu/papers/1998/glst.pdf
Mohammad Al-Turkistany
6
@JoeBebel En fait, il existe des vérificateurs 3 bits avec une parfaite complétude. Le vérificateur de Hastad est "linéaire": il échantillonne trois bits et prend leur XOR. Pour un tel vérificateur, vous devez sacrifier l'exhaustivité parfaite. BTW, il existe des preuves PCP qui ne lisent que deux bits (là encore nécessairement sans parfaite exhaustivité). Par exemple, voir ma réponse ici cstheory.stackexchange.com/a/20549/4896
Sasho Nikolov
9

Une chose qui se révèle contre-intuitive pour les étudiants de premier cycle CS, est le fait que l'on peut sélectionner le statistiques d'ordre -ème d'un tableau non trié de n éléments en O ( n ) temps. Tous les élèves pensent qu'ils doivent d'abord nécessairement trier le tableau (en temps O ( n l g n ) ).inO(n)O(n lg n)

Massimo Cafaro
la source
7

en s'appuyant sur la réponse / l'angle MdB, un résultat classique de quelque chose de contre-intuitif au moment de la découverte dans TCS à ses fondements est l'existence même de la (non) décidabilité . au tournant du 20 e siècle, Hilbert, reflétant la pensée d'autres grands mathématiciens de l'époque, pensait que les mathématiques pouvaient être systématisées (quelque peu sous la forme de ce que nous reconnaissons maintenant comme algorithmiques ) et quelque peu via le concept du de "finitisme" ( qui a des parallèles approximatifs avec l'idée d'un algorithme comme une séquence finie d'étapes). il a proposé des problèmes ouverts célèbres dans ce sens. son intuition (et d'autres) s'est révélée erronée d'une manière spectaculaire. la contre-épreuve estThéorème de Godels et problème de l'arrêt de Turings. les deux étaient à l'origine des concepts / résultats extrêmement abstraits et de longs articles / arguments très techniques compréhensibles uniquement par les mathématiciens de l'époque, mais ils sont maintenant affinés pour des structures conceptuelles plus simples et enseignés aux étudiants de premier cycle. ceux-ci n'étaient pas initialement considérés comme deux aspects / visage du même phénomène, mais ils le sont maintenant.

il a également fallu près de ¾ de siècle pour prouver que les équations diophantiennes entières sont indécidables, problème de Hilberts 10e . ceci est contre-intuitif dans le sens où il a toujours été connu que la théorie des nombres était extrêmement difficile mais le concept selon lequel certains problèmes spécifiques / identifiables peuvent en fait être "impossibles à résoudre" était presque choquant à l'époque pour certains. l'indécidabilité continue d'être un défi majeur en mathématiques / TCS, même si nous avons des décennies d'augmentations exponentielles du matériel dues à la loi de Moores et pourtant des supercalculateurs massifs qui sont dans un sens toujours "impuissants contre elle". certains aspects de la surprise de l'indécidabilité peuvent être trouvés dans le livre Mathematics, Loss of Certainty de Klein.

vzn
la source
2
L'article de Turing n'était pas extrêmement abstrait / technique. C'est en fait assez simple et accessible.
Jeffε
1
très bien, peut-être pour vous, maintenant, mais combien d' étudiants de premier cycle savez-vous qui peut suivre l' intégralité du document? l' avez - vous suivi en tant que premier cycle? pourquoi le contenu complet n'est-il pas couvert dans les classes de premier cycle? pourquoi un livre entier a-t-il été écrit en analysant ce papier? Qu'en est-il des parties qui anticipent des concepts qui n'ont été découverts que des décennies plus tard, tels que la correspondance curry-howard , les langages de programmation de haut niveau, etc.?
vzn
3
Pourtant, «de longs articles / arguments hautement techniques ne sont compréhensibles que par les grands mathématiciens de l'époque» n'est pas exact par rapport à l'article de Turing, qui est des ordres de grandeur plus accessible que les articles de Godel. Cette réponse est pleine de non-sequitirs. Je ne vois pas ce que le finitisme a à voir avec le programme de Hilbert (je suis certain qu'il n'aurait pas été finaliste). Ce que la loi de Moore a à voir avec l'indécidabilité est aussi un casse-tête pour moi. Pensez-vous vraiment qu'un matériel exponentiellement plus rapide résoudrait des problèmes indécidables ?
Sasho Nikolov
3
pourquoi le contenu complet n'est-il pas couvert dans les classes de premier cycle? - Pas assez de temps.
Jeffε
1
D'accord, je ne connaissais pas le finitisme de Hilbert. Je ne connaissais que les notions modernes et beaucoup plus strictes de finitisme. Il serait préférable que vous écriviez une bonne réponse plutôt que de référer des gens au chat, mais je doute que vous suivriez ce conseil.
Sasho Nikolov
6

Cela semble évident, mais par expérience personnelle, l'idée que vous pouvez estimer la médiane d'une collection d'articles en utilisant un nombre constant d'opérations est un peu choquante. Et si cela semble un peu trop technique, vous pouvez toujours le convertir en une déclaration sur les sondages et les élections (vous avez besoin de 1300 personnes pour obtenir un échantillon avec une erreur de 3%, quelle que soit la taille de la population).

Le paradoxe de l' anniversaire est bien sûr lié à cela .

Suresh Venkat
la source
5

Un bon exemple (non directement lié à la complexité de calcul) est peut-être l'universalité de Turing de modèles de calcul simples.

Par exemple, règle 110 est efficacement (faiblement) universelle:

Étant donné un tableau (infini) de cellules 0-1 (blanc-noir) correctement initialisé et les règles de substitution simples:

entrez la description de l'image ici

nous avons un "ordinateur qui fonctionne"! :-)

Pour la définition de "faiblement" et "efficace", et pour d'autres exemples de machines de Turing universelles simples, regardez: Turlough Neary, Damien Woods; La complexité des petites machines universelles de Turing: une enquête .

Un autre exemple déroutant est l'exhaustivité de Turing du FRACTRAN "langage de programmation" :

  • (p1/q1,p2/q2,...,pn/qn);
  • donné une entrée n trouver le premier qje qui divise n et remplacer nnpjeqje;
  • répéter l'étape précédente jusqu'à ce que non qje divise n.

Avec un codage approprié de l'entrée n, FRACTRAN peut simuler n'importe quelle machine de Turing.

Vous pouvez également utiliser d'autres modèles, comme des systèmes de balises cycliques, des ant-automates, ....
L'idée pas si intuitive est que le "calcul" est caché presque partout ... Wolfram a écrit 1192 pages remplies de chiffres et de texte pour mieux exprimer cette idée dans son A New Kind of Science (oui ... oui ... malgré quelques critiques critiques, j'en ai finalement acheté une copie papier :-)

Marzio De Biasi
la source
3

Quelques bons candidats du haut de ma tête:

  • Chaque NFA a un DFA équivalent

  • Il existe un champ de taille fini p ou pjejeN et je>0.

  • Cryptographie à clé publique

    • Appel à une fonction avec des arguments chiffrés et réception du résultat souhaité sans révéler d'informations sur vos entrées

    • Encrpytion RSA

  • Codes Reed-Solomon

  • Comptabilité

    • |N|=|Z|=|N×N|=|Q|

    • L'ensemble des éléments de la langue {0,1} est dénombrable, mais R est innombrable (diagonalisation de Cantor)

    • Théorème de Cantor: |S|<|P(S)|

  • À un niveau plus philosophique, cela m'a étonné que les machines de Turing définissent avec précision le calcul

Bharadwaj Ramachandran
la source