Maths et Délires
Des maths et des délires
 

Maths et Délires Index du Forum

 FAQFAQ   RechercherRechercher   Liste des MembresListe des Membres   Groupes d'utilisateursGroupes d'utilisateurs   S'enregistrerS'enregistrer 
 ProfilProfil   Se connecter pour vérifier ses messages privésSe connecter pour vérifier ses messages privés   ConnexionConnexion 

Prologin
Aller à la page 1, 2, 3 ... 11, 12, 13  Suivante
 
Poster un nouveau sujet   Répondre au sujet    Maths et Délires Index du Forum -> Discute
Voir le sujet précédent :: Voir le sujet suivant  
Auteur Message
Jill-Jênn
Au fait, on t'avait dit d'arrêter de flooder


Inscrit le: 23 Juin 2005
Messages: 6360
Localisation: ENS Cachan, France, Europe, Terre, Univers, ENS Cachan...

MessagePosté le: 20 Jan 2007, 11:34    Sujet du message: Prologin Répondre en citant

On a sélectionné en demi-finale avec Thibaut le 10 mars à l'École Polytechnique !

D'ailleurs, si c'est possible il m'emmènera voir les normaliens après l'épreuve :)

Est-ce que ça s'est bien passé pour Eldara ?
_________________
« Être amoureux, ce n'est qu'une erreur de jugement temporaire. Un peu comme une maladie mentale. »
— Haruhi, dans La Mélancolie de Haruhi Suzumiya
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail Visiter le site web du posteur Adresse AIM Yahoo Messenger MSN Messenger
Cerise
Admin gentil


Inscrit le: 23 Juin 2005
Messages: 3323
Localisation: Rennes

MessagePosté le: 20 Jan 2007, 13:24    Sujet du message: Re: Prologin Répondre en citant

Jill-Jênn a écrit:
Est-ce que ça s'est bien passé pour Eldara ?

Ah bon, il a participé cette année aussi ?

_____
Cerise, qui n'étais pas au courant...
_________________
Twisted Evil Victime vengeresse Twisted Evil

amo ergo sum

Méfiez-vous de l'assassinat ; il conduit au vol et, de là, à la dissimulation.
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail Adresse AIM Yahoo Messenger
Jill-Jênn
Au fait, on t'avait dit d'arrêter de flooder


Inscrit le: 23 Juin 2005
Messages: 6360
Localisation: ENS Cachan, France, Europe, Terre, Univers, ENS Cachan...

MessagePosté le: 20 Jan 2007, 17:31    Sujet du message: Répondre en citant

Je ne sais pas, je demandais juste Mr. Green
_________________
« Être amoureux, ce n'est qu'une erreur de jugement temporaire. Un peu comme une maladie mentale. »
— Haruhi, dans La Mélancolie de Haruhi Suzumiya
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail Visiter le site web du posteur Adresse AIM Yahoo Messenger MSN Messenger
Cerise
Admin gentil


Inscrit le: 23 Juin 2005
Messages: 3323
Localisation: Rennes

MessagePosté le: 20 Jan 2007, 17:32    Sujet du message: Répondre en citant

Ah bon. Alors il me semble pas qu'il ait participé, mais peut-être que si, on sait jamais.
_________________
Twisted Evil Victime vengeresse Twisted Evil

amo ergo sum

Méfiez-vous de l'assassinat ; il conduit au vol et, de là, à la dissimulation.
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail Adresse AIM Yahoo Messenger
musichien
Mathématicien(ne)


Inscrit le: 31 Aoû 2005
Messages: 1128
Localisation: devant mon ordi

MessagePosté le: 20 Jan 2007, 19:51    Sujet du message: Répondre en citant

Je vois que la communication familiale a les mêmes soucis partout... Very Happy
_________________
Le roi de la solution pas claire
(et fausse accessoirement)
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail MSN Messenger
Cerise
Admin gentil


Inscrit le: 23 Juin 2005
Messages: 3323
Localisation: Rennes

MessagePosté le: 21 Jan 2007, 18:47    Sujet du message: Répondre en citant

Bah écoute, il est à Paris et moi à Rennes (et le reste à Poitiers), alors on se dit pas tout en détail ce que l'on fait... L'année dernière, on était tous les deux à Poitiers alors je savais...
Ça ne veut pas dire que la communication passe mal, bien au contraire...
_________________
Twisted Evil Victime vengeresse Twisted Evil

amo ergo sum

Méfiez-vous de l'assassinat ; il conduit au vol et, de là, à la dissimulation.
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail Adresse AIM Yahoo Messenger
antony
Mathématicien(ne) fou (folle)


Inscrit le: 24 Juin 2005
Messages: 2176
Localisation: Vincennes/Aulnay

MessagePosté le: 22 Jan 2007, 13:09    Sujet du message: Répondre en citant

Je passe la demi-finale le 3 mars à Toulouse. Pour info, j'ai fait un peu n'importe quoi dans les questions de programmation 2 (complexité [tex:86dcd3857d]O(mn)[/tex:86dcd3857d], même si ça ne peut pas se voir) et 3 ([tex:86dcd3857d]O(n^4\ln n)[/tex:86dcd3857d], mais là non plus ça ne se voit pas Wink).
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé
Cerise
Admin gentil


Inscrit le: 23 Juin 2005
Messages: 3323
Localisation: Rennes

MessagePosté le: 22 Jan 2007, 19:48    Sujet du message: Répondre en citant

Tiens, en parlant d'informatique, je viens d'avoir ma note du premier semestre... Ouch ! Je réalise le record (dans la classe) de la plus grande différence entre la note de contrôle continu et la note d'examen terminal... J'ai la deuxième meilleure note au contrôle continu et la deuxième moins bonne à l'examen ! Et ça me fait... 10,875 de moyenne... Ouf Wink
_________________
Twisted Evil Victime vengeresse Twisted Evil

amo ergo sum

Méfiez-vous de l'assassinat ; il conduit au vol et, de là, à la dissimulation.
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail Adresse AIM Yahoo Messenger
Thibaut
Geek mutant fou


Inscrit le: 23 Juin 2005
Messages: 3226
Localisation: MB 318, Montrouge

MessagePosté le: 22 Jan 2007, 20:40    Sujet du message: Répondre en citant

Contrôle continu, c'est quoi, exactement ? Un partiel ? Une moyenne de plusieurs ?

antony a écrit:
Je passe la demi-finale le 3 mars à Toulouse. Pour info, j'ai fait un peu n'importe quoi dans les questions de programmation 2 (complexité [tex:2c4f9252c2]O(mn)[/tex:2c4f9252c2], même si ça ne peut pas se voir)
C'est pas optimal ? Le mieux qu'on puisse faire par un algorithme non-déterministe doit-être [tex:2c4f9252c2]O(n+log m)[/tex:2c4f9252c2], et je ne vois pas comment on peut obtenir cette complexité en déterministe...
Citation:
et 3 ([tex:2c4f9252c2]O(n^4\ln n)[/tex:2c4f9252c2], mais là non plus ça ne se voit pas Wink).
Qui est n ? Le nombre de cases de la grille d'un Sudoku généralisé ? Le côté d'un Sudoku généralisé ? La racine carré du nombre précédent ?
_________________
"“The Sith who were famous for being bad, Jacen, were the way they were because they were badly damaged men or women to start with. Not because they were Sith. Usually, they were weak, or deluded, or greedy to begin with. Like your grandfather.”"
Shira Brie aka Lumiya aka Brisha Syo, Legacy of the Force, #1: Betrayal
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail
Cerise
Admin gentil


Inscrit le: 23 Juin 2005
Messages: 3323
Localisation: Rennes

MessagePosté le: 22 Jan 2007, 20:52    Sujet du message: Répondre en citant

Thibaut a écrit:
Contrôle continu, c'est quoi, exactement ? Un partiel ? Une moyenne de plusieurs ?

En l'occurence, pour l'info, c'était un partiel et deux TP qui comptaient pour un huitième chacun...
_________________
Twisted Evil Victime vengeresse Twisted Evil

amo ergo sum

Méfiez-vous de l'assassinat ; il conduit au vol et, de là, à la dissimulation.
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail Adresse AIM Yahoo Messenger
antony
Mathématicien(ne) fou (folle)


Inscrit le: 24 Juin 2005
Messages: 2176
Localisation: Vincennes/Aulnay

MessagePosté le: 23 Jan 2007, 9:29    Sujet du message: Répondre en citant

Pour obtenir O(m+n), on fait un parcours en "escalier" : on monte sur la première colonne jusqu'à la fin de la colonne, on passe à côté, on continue à monter si c'est possible, et ainsi de suite.
Mais comme l'entrée des données se fait déjà en O(mn), ça ne peut pas se voir en testant sur le site de Prologin.

Cela dit je veux bien avoir l'algorithme non déterministe...

Et pour le Sudoku, c'est du côté du Soduku qu'il s'agit. Le ln n vient simplement du fait que pour tester l'égalité à {1,...,9} d'une liste, au lieu de cocher les éléments un à un dans un vecteur de booléens, je la trie et la compare à [1,...,9]. Oui, c'est totalement inefficace...
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé
Thibaut
Geek mutant fou


Inscrit le: 23 Juin 2005
Messages: 3226
Localisation: MB 318, Montrouge

MessagePosté le: 23 Jan 2007, 10:13    Sujet du message: Répondre en citant

Normalement, dans le calcul de complexité, on ne tient pas compte du temps d'entrée / sortie de données, ni de l'espace qu'elles occupent (sauf si on réécrit par-dessus).
Algorithme non déterministe :
* On choisit de manière non déterministe un nombre [tex:4d933844a1]i[/tex:4d933844a1] entre [tex:4d933844a1]0[/tex:4d933844a1] et [tex:4d933844a1]n-1[/tex:4d933844a1] (se fait en temps et en espace [tex:4d933844a1]O(\ln n)[/tex:4d933844a1]).
* On choisit de manière non déterministe un nombre [tex:4d933844a1]j[/tex:4d933844a1] entre [tex:4d933844a1]0[/tex:4d933844a1] et [tex:4d933844a1]m-1[/tex:4d933844a1] (se fait en temps et en espace [tex:4d933844a1]O(\ln n)[/tex:4d933844a1]).
Si pour tout [tex:4d933844a1]k[/tex:4d933844a1] entre [tex:4d933844a1]0[/tex:4d933844a1] et [tex:4d933844a1]n-1[/tex:4d933844a1], [tex:4d933844a1]A[k,j+1]=0[/tex:4d933844a1], et [tex:4d933844a1]A[i,j]=1[/tex:4d933844a1], alors la hauteur cherchée est [tex:4d933844a1]j+1[/tex:4d933844a1] (se fait en temps [tex:4d933844a1]O(n)[/tex:4d933844a1] avec une machine RAM comme nos ordis. Avec une "bête" machine de Turing, ça doit dépendre de si on rentre le tableau par lignes ou par colonnes. Espace : [tex:4d933844a1]O(\ln n+\ln m)[/tex:4d933844a1] si je ne m'abuse.)

Et pour le Sudoku, ça ne fait pas du [tex:4d933844a1]O(n^2 \ln n)[/tex:4d933844a1] ? ([tex:4d933844a1]n \ln [/tex:4d933844a1] par tri de longueur [tex:4d933844a1]n[/tex:4d933844a1], et [tex:4d933844a1]3n[/tex:4d933844a1] tris à effectuer, tout le reste étant en [tex:4d933844a1]O(n^2)[/tex:4d933844a1].


Tiens, en parlant d'algorithmes non déterministes...
Les algorithmes qu'on est censés pouvoir implémenter sur un ordinateur quantiques, est-ce que c'est ce qu'on appelle les algorithmes non-déterministes, alternants, probabilistes, ou rien de tout ça ?
_________________
"“The Sith who were famous for being bad, Jacen, were the way they were because they were badly damaged men or women to start with. Not because they were Sith. Usually, they were weak, or deluded, or greedy to begin with. Like your grandfather.”"
Shira Brie aka Lumiya aka Brisha Syo, Legacy of the Force, #1: Betrayal
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail
antony
Mathématicien(ne) fou (folle)


Inscrit le: 24 Juin 2005
Messages: 2176
Localisation: Vincennes/Aulnay

MessagePosté le: 23 Jan 2007, 10:23    Sujet du message: Répondre en citant

Thibaut a écrit:
Normalement, dans le calcul de complexité, on ne tient pas compte du temps d'entrée / sortie de données, ni de l'espace qu'elles occupent (sauf si on réécrit par-dessus).
Oui, je sais, mais dans ce cas, c'est ce qui a empêché le test sur le site de Prologin de n'accepter que les algorithmes en O(m+n).
Thibaut a écrit:
Et pour le Sudoku, ça ne fait pas du [tex:97594e1dd9]O(n^2 \ln n)[/tex:97594e1dd9] ? ([tex:97594e1dd9]n \ln [/tex:97594e1dd9] par tri de longueur [tex:97594e1dd9]n[/tex:97594e1dd9], et [tex:97594e1dd9]3n[/tex:97594e1dd9] tris à effectuer, tout le reste étant en [tex:97594e1dd9]O(n^2)[/tex:97594e1dd9].
Oui, autant pour moi ; mais on peut donc faire du O(n²).
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé
xavier
Mathématicien(ne)


Inscrit le: 23 Juin 2005
Messages: 1190

MessagePosté le: 23 Jan 2007, 10:54    Sujet du message: Répondre en citant

Thibaut a écrit:
Les algorithmes qu'on est censés pouvoir implémenter sur un ordinateur quantiques, est-ce que c'est ce qu'on appelle les algorithmes non-déterministes, alternants, probabilistes, ou rien de tout ça ?

Bah, on les appelle des algorithmes quantiques... Sinon je ne me rappelle plus bien, mais l'algorithme est en général déterministe dans le sens où l'on ne fait pas appel à un oracle aléatoire pour le décrire. Cependant, le résultat qu'il donne est une fonction d'onde qui est seulement une superposition de la bonne réponse et d'autre chose, la première étant surreprésentée. Lorsque l'on mesure celle-ci, on a donc seulement une certaine probabilité 1-eps d'avoir effectivement le résultat que l'on voulait.
Cela dit, je ne sais pas bien la différence que tu fais entre « non-déterministes » et « probabilistes » et je ne sais pas ce que veut dire « alternants », donc bon.
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Visiter le site web du posteur
Thibaut
Geek mutant fou


Inscrit le: 23 Juin 2005
Messages: 3226
Localisation: MB 318, Montrouge

MessagePosté le: 23 Jan 2007, 10:55    Sujet du message: Répondre en citant

Bah... Après tout, du [tex:892cc37c15]n^2 \ln n[/tex:892cc37c15], c'est du [tex:892cc37c15]n^{2+o(1)}[/tex:892cc37c15], non ? Donc c'est quadratique, et c'est tout ce qui compte...
_________________
"“The Sith who were famous for being bad, Jacen, were the way they were because they were badly damaged men or women to start with. Not because they were Sith. Usually, they were weak, or deluded, or greedy to begin with. Like your grandfather.”"
Shira Brie aka Lumiya aka Brisha Syo, Legacy of the Force, #1: Betrayal
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail
antony
Mathématicien(ne) fou (folle)


Inscrit le: 24 Juin 2005
Messages: 2176
Localisation: Vincennes/Aulnay

MessagePosté le: 23 Jan 2007, 11:58    Sujet du message: Répondre en citant

Oui, mais bon, le temps que je perds, je le perds sur un tri qui ne sert strictement à rien... enfin bon.
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé
Eldara-Elessar
Matheux(se) cinglé(e)


Inscrit le: 24 Juin 2005
Messages: 319

MessagePosté le: 24 Jan 2007, 22:14    Sujet du message: Répondre en citant

Pour répondre à la question de Jill-Jênn (et de Sandrine ;)) j'ai bêtement oublié de soumettre mes solutions le jour dit...

Donc du coup ça sera pour l'an prochain...

En revanche j'ai deux potes qui participent aussi à la demi finale le 10 mars (avec qui j'aurais du être normalement :p) donc modulo le ds de maths du matin je pense que j'essaierai d'y aller quand même (même si logiquement ils seront sensés être en épreuve machine l'aprem...)
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé MSN Messenger
Jill-Jênn
Au fait, on t'avait dit d'arrêter de flooder


Inscrit le: 23 Juin 2005
Messages: 6360
Localisation: ENS Cachan, France, Europe, Terre, Univers, ENS Cachan...

MessagePosté le: 25 Jan 2007, 1:17    Sujet du message: Répondre en citant

Cerise a écrit:
En l'occurence, pour l'info, c'était un partiel et deux TP qui comptaient pour un huitième chacun...
Antony a écrit:
Oui, autant pour moi ; mais on peut donc faire du O(n²).
Mr. Green

Eldara-Elessar a écrit:
Pour répondre à la question de Jill-Jênn (et de Sandrine ;)) j'ai bêtement oublié de soumettre mes solutions le jour dit...
Dommage... Sad

Eldara-Elessar a écrit:
Donc du coup ça sera pour l'an prochain...
C'est ça qui est cool, on peut repasser encore plein de fois Razz

Eldara-Elessar a écrit:
donc modulo le ds de maths du matin je pense que j'essaierai d'y aller quand même

_________________
« Être amoureux, ce n'est qu'une erreur de jugement temporaire. Un peu comme une maladie mentale. »
— Haruhi, dans La Mélancolie de Haruhi Suzumiya
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail Visiter le site web du posteur Adresse AIM Yahoo Messenger MSN Messenger
Thibaut
Geek mutant fou


Inscrit le: 23 Juin 2005
Messages: 3226
Localisation: MB 318, Montrouge

MessagePosté le: 25 Jan 2007, 7:52    Sujet du message: Répondre en citant

Jill-Jênn a écrit:
Antony a écrit:
Oui, autant pour moi ; mais on peut donc faire du O(n²).
Mr. Green
Bah quoi ?
_________________
"“The Sith who were famous for being bad, Jacen, were the way they were because they were badly damaged men or women to start with. Not because they were Sith. Usually, they were weak, or deluded, or greedy to begin with. Like your grandfather.”"
Shira Brie aka Lumiya aka Brisha Syo, Legacy of the Force, #1: Betrayal
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail
Eldara-Elessar
Matheux(se) cinglé(e)


Inscrit le: 24 Juin 2005
Messages: 319

MessagePosté le: 25 Jan 2007, 10:44    Sujet du message: Répondre en citant

je crois que ça s'écrit au temps pour moi normalement...

Mais c'est un des grands mystères de la langue française, les spécialistes se perdent en conjectures, certains (moins nombreux mais bon) disent que ça s'écrit autant pour moi, d'autres au temps pour moi... Passionnant...

Moralité, il vaut mieux ne pas l'écrire.
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé MSN Messenger
Montrer les messages depuis:   
Poster un nouveau sujet   Répondre au sujet    Maths et Délires Index du Forum -> Discute Toutes les heures sont au format GMT + 2 Heures
Aller à la page 1, 2, 3 ... 11, 12, 13  Suivante
Page 1 sur 13

 
Sauter vers:  
Vous ne pouvez pas poster de nouveaux sujets dans ce forum
Vous ne pouvez pas répondre aux sujets dans ce forum
Vous ne pouvez pas éditer vos messages dans ce forum
Vous ne pouvez pas supprimer vos messages dans ce forum
Vous ne pouvez pas voter dans les sondages de ce forum


Powered by phpBB © 2001, 2005 phpBB Group
Traduction par : phpBB-fr.com