Sorting under partial information (without the ellipsoid algorithm)

We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (STOC 1992) showed that there exists a polynomial-time algorithm for the problem achieving this bound up to a constant factor. Their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it impractical. We develop efficient algorithms for sorting under partial information. Like Kahn and Kim, our approach relies on graph entropy. However, our algorithms differ in essential ways from theirs. Rather than resorting to convex programming for computing the entropy, we approximate the entropy, or make sure it is computed only once in a restricted class of graphs, permitting the use of a simpler algorithm. Specifically, we present: an O(n2) algorithm performing O(log n·log e(P)) comparisons; an O(n2.5) algorithm performing at most (1+ε) log e(P) + Oε(n) comparisons; an O(n2.5) algorithm performing O(log e(P)) comparisons. All our algorithms are simple to implement. © 2010 ACM.

A toolset for the analysis of et-lotos specifications

info:eu-repo/semantics/published

A simulator of real-time systems specified in et-lotos

info:eu-repo/semantics/published

Cannibal Animal Games: A new variant of Tic-Tac-Toe

This paper presents a new partial two-player game, called the cannibal animal game, which is a variant of Tic-Tac-Toe. The game is played on the infinite grid, where in each round a player chooses and occupies free cells. The first player Alice can occupy a cell in each turn and wins if she occupies a set of cells, the union of a subset of which is a translated, reflected and/or rotated copy of a previously agreed upon polyomino P (called an animal). The objective of the second player Bob is to prevent Alice from creating her animal by occupying in each round a translated, reflected and/or rotated copy of P. An animal is a cannibal if Bob has a winning strategy, and a non-cannibal otherwise. This paper presents some new tools, such as the bounding strategy and the punching lemma, to classify animals into cannibals or non-cannibals. We also show that the pairing strategy works for this problem.

Efficient energy distribution in a smart grid using multi-player games

info:eu-repo/semantics/submittedForPublication

Hopf hypersurfaces in pseudo-Riemannian complex and para-complex space forms

The study of real hypersurfaces in pseudo-Riemannian complex space forms and para-complex space forms, which are the pseudo-Riemannian generalizations of the complex space forms, is addressed. It is proved that there are no umbilic hypersurfaces, nor real hypersurfaces with parallel shape operator in such spaces. Denoting by J be the complex or para-complex structure of a pseudo-complex or para-complex space form respectively, a non-degenerate hypersurface of such space with unit normal vector field N is said to be Hopf if the tangent vector field JN is a principal direction. It is proved that if a hypersurface is Hopf, then the corresponding principal curvature (the Hopf curvature) is constant. It is also observed that in some cases a Hopf hypersurface must be, locally, a tube over a complex (or para-complex) submanifold, thus generalizing previous results of Cecil, Ryan and Montiel.

Asymmetric polygons with maximum area

We say that a polygon inscribed in the circle is asymmetric if it contains no two antipodal points being the endpoints of a diameter. Given n diameters of a circle and a positive integer k < n, this paper addresses the problem of computing a maximum area asymmetric k-gon having as vertices k < n endpoints of the given diameters. The study of this type of polygons is motivated by ethnomusiciological applications.

Classic Nintendo games are (computationally) hard

We prove NP-hardness results for five of Nintendo's largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokémon. Our results apply to generalized versions of Super Mario Bros.1-3, The Lost Levels, and Super Mario World; Donkey Kong Country 1-3; all Legend of Zelda games; all Metroid games; and all Pokémon role-playing games. In addition, we prove PSPACE-completeness of the Donkey Kong Country games and several Legend of Zelda games.

Modèle informatique du coapprentissage des ganglions de la base et du cortex : l'apprentissage par renforcement et le développement de représentations

Tout au long de la vie, le cerveau développe des représentations de son environnement permettant à l’individu d’en tirer meilleur profit. Comment ces représentations se développent-elles pendant la quête de récompenses demeure un mystère. Il est raisonnable de penser que le cortex est le siège de ces représentations et que les ganglions de la base jouent un rôle important dans la maximisation des récompenses. En particulier, les neurones dopaminergiques semblent coder un signal d’erreur de prédiction de récompense. Cette thèse étudie le problème en construisant, à l’aide de l’apprentissage machine, un modèle informatique intégrant de nombreuses évidences neurologiques. Après une introduction au cadre mathématique et à quelques algorithmes de l’apprentissage machine, un survol de l’apprentissage en psychologie et en neuroscience et une revue des modèles de l’apprentissage dans les ganglions de la base, la thèse comporte trois articles. Le premier montre qu’il est possible d’apprendre à maximiser ses récompenses tout en développant de meilleures représentations des entrées. Le second article porte sur l'important problème toujours non résolu de la représentation du temps. Il démontre qu’une représentation du temps peut être acquise automatiquement dans un réseau de neurones artificiels faisant office de mémoire de travail. La représentation développée par le modèle ressemble beaucoup à l’activité de neurones corticaux dans des tâches similaires. De plus, le modèle montre que l’utilisation du signal d’erreur de récompense peut accélérer la construction de ces représentations temporelles. Finalement, il montre qu’une telle représentation acquise automatiquement dans le cortex peut fournir l’information nécessaire aux ganglions de la base pour expliquer le signal dopaminergique. Enfin, le troisième article évalue le pouvoir explicatif et prédictif du modèle sur différentes situations comme la présence ou l’absence d’un stimulus (conditionnement classique ou de trace) pendant l’attente de la récompense. En plus de faire des prédictions très intéressantes en lien avec la littérature sur les intervalles de temps, l’article révèle certaines lacunes du modèle qui devront être améliorées. Bref, cette thèse étend les modèles actuels de l’apprentissage des ganglions de la base et du système dopaminergique au développement concurrent de représentations temporelles dans le cortex et aux interactions de ces deux structures.

La programmation informatique dans la recherche et la formation en mathématiques au niveau universitaire

Une étude récente auprès de 302 mathématiciens canadiens révèle un écart intriguant : tandis que 43% des sondés utilisent la programmation informatique dans leur recherche, seulement 18% indiquent qu'ils emploient cette technologie dans leur enseignement (Buteau et coll., 2014). La première donnée reflète le potentiel énorme qu'a la programmation pour faire et apprendre des mathématiques. La deuxième donnée a inspiré ce mémoire : pourquoi existe-t-il un tel écart ? Pour répondre à cette question, nous avons mené une étude exploratoire qui cherche à mieux comprendre la place de la programmation dans la recherche et la formation en mathématiques au niveau universitaire. Des entrevues semi-dirigées ont été conduites avec 14 mathématiciens travaillant dans des domaines variés et à différentes universités à travers le pays. Notre analyse qualitative nous permet de décrire les façons dont ces mathématiciens construisent des programmes informatiques afin d'accomplir plusieurs tâches (p.e., simuler des phénomènes réels, faire des mathématiques « expérimentales », développer de nouveaux outils puissants). Elle nous permet également d'identifier des moments où les mathématiciens exposent leurs étudiants à certains éléments de ces pratiques en recherche. Nous notons toutefois que les étudiants sont rarement invités à concevoir et à écrire leurs propres programmes. Enfin, nos participants évoquent plusieurs contraintes institutionnelles : le curriculum, la culture départementale, les ressources humaines, les traditions en mathématiques, etc. Quelques-unes de ces contraintes, qui semblent limiter l'expérience mathématique des étudiants de premier cycle, pourraient être revues.

Une étude du développement professionnel par l'intégration dans la pratique d'enseignement d'une approche visant le développement du potentiel mathématique des élèves

Les enseignants passent une bonne partie de leur à temps à produire, à adapter et à modifier des ressources pédagogiques, ce qui place ce travail, appelé travail documentaire, au coeur de leur développement professionnel (Gueudet et Trouche, 2008). Dans le cadre d'une recherche collaborative ayant pour but le développement professionnel d'orthopédagogues et d'enseignants, effectuée par des chercheurs de l'Université de Sherbrooke, des ressources pédagogiques visant le développement du potentiel mathématique des élèves en difficulté d'apprentissage ont été conçues, adaptées et modifiées. Nous appuyant sur l'approche documentaire du didactique de Gueudet et Trouche (2008), nous décrivons le processus d'intégration de l'approche de développement du potentiel mathématique dans la pratique d'enseignement d'une enseignante ayant participé à la recherche collaborative. L'analyse de différents types de données recueillies lors des phases préactive, interactive et postactive de l'enseignement nous a permis d'identifier cinq schèmes d'usage (schèmes d'instrumentation et d'instrumentalisation) dans la pratique d'enseignement de notre enseignante. Notre mémoire traite donc de la problématique du développement professionnel des enseignants en considérant, sous un angle didactique, leur travail sur des ressources pédagogiques.

Élaboration d'une formation en ligne pour la partie mathématique du cours Projet interdisciplinaire et Probabilités et statistique offert au collégial.

Dès le départ, l'élaboration d'une formation en ligne pour le cours Projet interdisciplinaire et Probabilités et statistique offert au Collège Gérald-Godin est apparue comme une solution intéressante aux préoccupations des enseignantes et enseignants et aux différents problèmes rencontrés. Les enseignantes et enseignants du regroupement de mathématiques trouvaient important de développer l'autonomie chez les étudiantes et les étudiants afin de bien les former pour l'université. La partie mathématique du cours présentait aussi certaines difficultés au niveau de la détermination de moments de rencontres permettant la réalisation du projet de sondage réalisé en équipe, ainsi qu'au niveau de la reprise de la partie mathématique échouée du cours qui entraînait un retard dans l'obtention du diplôme d'études collégiales. La récension des écrits a permis de définir le projet de formation en ligne développée dans cet essai. Cette formation en ligne a été réalisée de façon modeste par l'auteure de cet essai. Même les étudiantes et les étudiants ont suivi la formation en ligne, il y a aussi eu des rencontres en présence avec l'enseignante. Cette formation en ligne a utilisée un mélange de trois modèles : la classe technologique ouverte, l'autoformation Web hypermédia et l'enseignement en ligne. Elle a respecté la structure d'apprentissage suivant la séquence Unités d'apprentissage/Objets d'apprentissage/Ressources pédagogiques et a été présentée sur la plate-forme Moodle du Collège Gérald-Godin. En plus de présenter les différentes notions dans différents contextes, cette formation a favorisé une approche constructiviste dans laquelle nous retrouvons un projet de sondage. En nous basant sur la recension des écrits, la méthodologie de cet essai présente de quelle façon nous avons procédé à l'élaboration de la formation en ligne. Elle indique comment nous avons structuré la formation; les activités d'apprentissage privilégiées lors de l'élaboration de la formation en ligne; les ressources pédagogiques à rendre disponibles ainsi que la forme de ces ressources pédagogiques afin d'assurer la qualité des ressources rendues disponibles. De plus, elle présente de quelle façon nous avons utilisé l'ensemble des ressources disponibles sur la plate-forme afin d'assurer le meilleur encadrement possible.

Comptes rendus de l'Académie des sciences. Série 1, Mathématique

1985/09/15 (SER1,T301,N9).