Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Lorsqu’il est question de programmation informatique, il est d'usage de schématiser les étapes permettant la résolution d'un problème. Cette étude a permis de vérifier si la symbolisation des concepts et des règles a un effet sur l'acquisition et la rétention des habiletés de programmation linéaire. En d'autres termes, nous avons vérifié si l'usage d'un ordinogramme (représentation graphique du déroulement d’un programme) a un effet sur l'apprentissage des règles informatiques. Par la même occasion, nous avons observé les influences de l’enseignement tutoriel sur la motivation des apprenants ainsi que sur la rétention des habiletés visées. L’expérimentation a eu lieu auprès des étudiants du cours Initiation à l’ordinateur et aux A.P.O. durant la session d’hiver 1988. / Québec Université Laval, Bibliothèque 2019

Thèse (Ph. D.)--Université Laval, 2007. / Titre de l'écran-titre (visionné le 5 mai 2008). Bibliogr.

Un bloc de bits est équilibré s’il contient un nombre de bits à 0 égal à celui des bits à 1. Les codes équilibrés (Balanced Codes, BC) sont largement appliqués dans plusieurs domaines. Par exemple, ils sont utilisés pour réduire le bruit dans les systèmes VLSI (Tabor, 1990). Dans le domaine de la télécommunication, ils sont utilisés dans la synchronisation et la transmission des données par fibre optique (Bergmann et al., 1986). Leur utilisation dans le domaine de l’identification par radiofréquence (RFID) permet d’augmenter les taux de transfert de données via les canaux RFID (Durgin, 2015). Étant donnée leur importance, plusieurs travaux de recherche ont été menés pour optimiser leur construction. Knuth fut le premier à trouver une méthode simple et rapide pour l’élaboration des codes équilibrés (Knuth, 1986). Il a introduit un algorithme très simple pour générer les codes équilibrés sans l’utilisation des tables de correspondance. Cependant, cet algorithme ajoute presque le double de la redondance minimale nécessaire pour la création des codes équilibrés. Une partie de cette redondance est due à la multiplicité d’encodage (ME) de cet algorithme. Plusieurs chercheurs ont essayé de réduire la redondance de l’algorithme de Knuth (Immink et Weber, 2009a, 2010; Immink et al., 2011; Al-Rababa’a et al., 2013). Dans les derniers travaux de Al-Rababa’a et al. (2013), les auteurs ont réussi à éliminer la redondance créée par ME et pourtant un écart par rapport au seuil minimal subsiste. Ce travail présente une alternative à l’algorithme de Knuth pour créer les codes équilibrés sans surplus de redondance. Nous proposons un algorithme nommé « Pacman » ¹ basé sur les permutations et les nombres entiers à précision limitée. En effet, le processus de codage de cet algorithme peut être assimilé à un Pacman qui consomme et produit des blocs d’informations d’une façon cyclique. Au cours de ce travail, nous allons montrer analytiquement et expérimentalement que la redondance introduite par notre technique est particulièrement faible, que les résultats sont nettement meilleurs que ceux des travaux antérieurs et que les complexités temporelle et spatiale utilisées sont linéaires. ¹. Inspiré de la marque de commerce PAC-MAN de l’entreprise BANDAI NAMCO. / A block of m bits is said to be balanced if it contains an equal number of zeros and ones. Note that m has to be an even number. Balanced codes (BC) have applications in several domains. For example, they are used to reduce noise in VLSI systems (Tabor, 1990). In telecommunication, they are used in synchronization and data transmission by optical fibers (Bergmann et al., 1986). Their use in the field of radio frequency identification (RFID) can help to boost data transfer rate through RFID channels (Durgin, 2015). Given their importance, several research works have been carried out to optimize their construction. Knuth was the first to find a simple and fast method to create balanced codes (Knuth, 1986). He introduced a very simple algorithm to generate balanced codes without using lookup tables. However, Knuth’s balanced codes incur redundancy that is almost twice the one attested by the lower bound. A part of this redundancy is due to the multiplicity of encoding (ME) of this algorithm. Improvements to the Knuth’s algorithm are discussed in several research works (Immink et Weber, 2009a, 2010; Immink et al., 2011; Al-Rababa’a et al., 2013). In the last one (Al-Rababa’a et al., 2013), redundancy created by ME was eliminated and yet there is still some gap that needs to be closed. This work presents an alternative to Knuth’s algorithm for creating balanced codes without unwanted redundancy overhead. We propose an algorithm called "Pacman" ² that is based on permutations and limited-precision integers. Indeed, the coding process of this algorithm can be assimilated to a special Pacman that consumes and produces pills of information in a cyclical manner. In the presented work, we prove analytically and experimentally that our algorithm closes the mentioned redundancy gap while preserving a favorable compromise between calculation speed and memory consumption. ². Inspired by the trademark PAC-MAN of BANDAI NAMCO.

La définition d'un rôle social est très complexe. Cette complexité est encore accentuée lorsqu'il s'agit de la définition d'un rôle professionnel dans une technique très récente. De tout temps, les individus ont décidé tant de la définition que de l'exercice d'un rôle, mais dans une môme société constituée de définisseurs de rôle, il peut exister des groupes qui définissent différemment un même rôle. Dans notre société, certaines personnes préparent l'individu un rôle donné et par contre d'autres personnes utilisent ses performances dans ce rôle et par conséquent, chacun d'eux ont une influence justifiable sur la définition de ce rôle. Le rôle est composé de normes auxquelles est soumise l'action de sujets qui occupent une fonction particulière dans un groupe ou dans une collectivité. Il est dans la nature de presque toute collectivité, si petite soit-elle, qu'une différenciation des fonctions s'y produise, soit entre les personnes, soit entre les groupes, de sorte que chacun apporte è l'ensemble une contribution spécifique particulière et parfois singulière. La fonction du système total est fondée sur l'interdépendance de ces fonctions particulières. Même dans les plus petits groupes, les tests sociométriques et les études sur les groupes restreints ont mis en évidence cette division des fonctions. A chacune de ces fonctions correspondent des conduites particulières, des manières de faire qui répondent â certaines attentes chez les autres; certaines tâches demandent d'être accomplies d'une façon et non d'une autre. Par conséquent, outre des normes communes qui s'appliquent è tous les membres du groupe, d'autres plus spécifiques servent de guides aux différents membres du groupe selon les fonctions qu'ils remplissent. Même si l'on dit que le rôle est défini socialement, il demeure que ce sont des individus qui le définissent, et que parmi un groupe de définisseurs de rôle on peut retrouver des éléments de la personnalité caractéristique de ce groupe qui influence de beaucoup la définition comme telle. A priori, l'expérience nous porte â soupçonner une différence d'opinion dans la définition du rôle de l'informaticien. Toutefois, la recherche envisagée ici ne veut ni ne peut se contenter d'admettre une telle différence d'opinion. Encore faut-il retrouver les principaux éléments grevant cette différence et en mesurer l'importance. En conséquence, cette étude ne tiendra compte que de certains éléments de types sociologiques, personnels et organisationnels, et son cadre opérationnel sera la définition du rôle de l'informaticien. A cette fin, nous devons donc préciser la définition du rôle, et les conséquences générées vis-à-vis de la différence d'opinion. De plus nous devrons choisir un cadre théorique répondant aux besoins de notre recherche, identifier les diverses variables dont le rôle est une fonction, puis en discuter le mérite et l'incidence de chacun des éléments pour déterminer l'hypothèse axiomatique de la recherche. / Québec Université Laval, Bibliothèque 2014

Les analyses interprocédurales automatiques de programmes qui sont basées sur des théories mathématiques rigoureuses sont complexes à réaliser, mais elles sont d'excellents outils pour augmenter notre conance envers les comportements possibles d'un programme. Les méthodes classiques pour réaliser ces analyses sont l'analyse de modè- les, l'interprétation abstraite et la démonstration automatique de théorèmes. La base d'un démonstrateur automatique de théorèmes est une logique ou une algèbre et le choix de celle-ci a un impact sur la complexité de trouver une preuve pour un théorème donné. Cette dissertation développe un formalisme algébrique concis pouvant être utilisé en démonstration automatique de théorèmes. Ce formalisme est appellé algèbre de Kleene à pile visible. Cette dissertation explique comment ce formalisme peut être utilisé pour réaliser des analyses interprocédurales de programmes, comme des vérications formelles et des vérications d'optimisations efectuées par des compilateurs. Cette dissertation apporte aussi des preuves que ces analyses pourraient être automatisées. L'algèbre de Kleene à pile visible est une extension de l'algèbre de Kleene, un excellent formalisme pour réaliser des analyses intraprocédurales de programmes. En bref, l'algèbre de Kleene est la théorie algébrique des automates nis et des expressions régulières. Donc, cette algèbre à elle seule n'est pas appropriée pour faire des analyses interprocédurales de programmes car la puissance des langages non contextuels est souvent nécessaire pour représenter le lot de contrôle d'un tel programme. L'algèbre de Kleene à pile visible étend celle-ci en lui ajoutant une famille d'opérateurs de plus petit point xe qui est basée sur une restriction des grammaires non contextuelles. En fait, cette algèbre axiomatise exactement la théorie équationnelle des langages à pile visibles. Ces langages sont une sous-classe des langages non contextuels et ont été dénis par Alur et Madhusudan pour faire de l'analyse de modèles. La complexité résultante de la théorie équationnelle de l'algèbre proposée est EXPTIME-complète. / Automatic interprocedural program analyses based on rigorous mathematical theories are complex to do, but they are great tools to increase our condence in the behaviour of a program. Classical ways of doing them is either by model checking, by abstract interpretation or by automated theorem proving. The basis of an automated theorem prover is a logic or an algebra and the choice of this basis will have an impact in the complexity of nding a proof for a given theorem. This dissertation develops a lightweight algebraic formalism for the automated theorem proving approach. This formalism is called visibly pushdown Kleene algebra. This dissertation explains how to do some interprocedural program analyses, like formal veri cation and verication of compiler optimizations, with this formalism. Evidence is provided that the analyses can be automated. The proposed algebraic formalism is an extension of Kleene algebra, a formalism for doing intraprocedural program analyses. In a nutshell, Kleene algebra is the algebraic theory of nite automata and regular expressions. So, Kleene algebra alone is not well suited to do interprocedural program analyses, where the power of context-free languages is often needed to represent the control flow of a program. Visibly pushdown Kleene algebra extends Kleene algebra by adding a family of implicit least xed point operators based on a restriction of context-free grammars. In fact, visibly pushdown Kleene algebra axiomatises exactly the equational theory of visibly pushdown languages. Visibly pushdown languages are a subclass of context-free languages dened by Alur and Madhusudan in the model checking framework to model check interprocedural programs while remaining decidable. The resulting complexity of the equational theory of visibly pushdown Kleene algebra is EXPTIME-complete whereas that of Kleene algebra is PSPACE-complete.

Titre de l'écran-titre (visionné le 12 janvier 2024) / Devant l'augmentation de la place qu'occupe la technologie dans nos vies, de plus en plus d'enseignants tentent d'intégrer l'enseignement de la programmation à leurs pratiques pédagogiques. Dans ce mémoire, nous étudions comment deux activités menées dans le cours de Didactique des sciences III permettent à de futurs enseignants de se construire un modèle de l'enseignement de la programmation. Dans une posture ancrée dans la 3ᵉ génération de la théorie de l'activité, nous analysons, dans un premier temps, comment une activité menée sur un forum de coélaboration de connaissances, le Knowledge Forum, a permis à des étudiants de se créer un premier modèle en indiquant autant des sources de tensions que des solutions aux possibles problèmes soulevés de l'enseignement de la programmation en classe. Dans un deuxième temps, nous documentons comment une activité pratique, la construction d'une serre automatisée avec un module Arduino, un microcontrôleur programmable qui permet d'automatiser des systèmes, a permis à des étudiants de voir la pertinence de la programmation au secondaire. Cependant, nous identifions un manque ressenti de compétence en programmation pour que les futurs enseignants soient à l'aise d'ajouter cet apprentissage à leurs cours. / As technology becomes increasingly important in our lives, more and more teachers are trying to integrate computer programming into their teaching practices. In this memoir, we study how two activities carried out in the Sciences didactics III course enable future teachers to build a model for teaching programming. Based on 3rd generation cultural historical activity theory (CHAT), we first analyze how an activity carried out on the Knowledge Forum enabled students to create an initial model. We then document how a practical activity, the construction of an automated greenhouse using an Arduino kit, enabled students to see the relevance of programming in high school. However, we identify a perceived lack of programming competence for future teachers to feel comfortable introducing this learning into their courses.

De plus en plus de pays introduisent ou réintroduisent la programmation informatique dans les programmes de formation de la maternelle jusqu’à l’école secondaire. Dans ce contexte, ce projet de recherche vise à explorer les conditions qui supportent l’engagement lors de la pratique de la programmation informatique envisagée comme activité humaine. L’engagement est ici défini suivant à la fois des définitions issues des sciences de l’éducation et de l’informatique. Il se décline en trois types : comportemental, cognitif et affectif. Dix-huit (18) sujets ayant un minimum de cinq (5) ans d’expérience en programmation informatique ont accepté de participer à des entretiens individuels semi-dirigés au cours desquels ils étaient invités à discuter de la façon par laquelle ils ont appris à programmer, des contextes dans lesquels ils se sont engagés et de leurs perceptions de l’implication cognitive et affective en jeu. Les discours ont été codifiés à partir d’une démarche de recherche interprétative émergente afin d’éclairer la question de recherche suivante : Quelles sont les conditions supportant l’engagement dans l’activité de programmation informatique ? Les résultats nous amènent à proposer trois conditions supportant l’engagement : (1) les programmeurs et programmeuses développent un rapport au savoir dans lequel ils regardent un même problème depuis quatre postures épistémologiques en tension, (2) il y a convergence entre les motivations personnelles et organisationnelles, et (3) ils ont assez d’espace pour exprimer leur créativité. / Computer programming is being introduced or reintroduced in K-12 around the world. In this context, this project aims at exploring what supports engagement in computer programming considered as a human activity. Engagement is here defined following both an educational definition of school engagement and a computer science definition of engagement, and it is divided into three types: behavioral, cognitive and affective. Eighteen (18) subjects each with at least five years of cumulated programming experience accepted to take part in semidirected individual interviews. They were invited to discuss the way they learnt programming, the various contexts in which they engage themselves regarding programming, and their perception about cognitive and affective involvement. Parts of speech were then classified following an emergent research design to answer the following question: What conditions support engagement in computer programming? Results lead us to propose three conditions that support engagement: (1) programmers adopt a relationship to knowledge in which they must undertake different epistemological positions to develop an effective understanding of a problem, (2) there is a convergence between self and organizational motivations, and (3) they have enough space to express their creativity.

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. / A recent survey of 302 Canadian mathematicians points to an intriguing gap: while 43% of the participants use computer programming in their research, only 18% indicate that they use such technology in their teaching (Buteau et al., 2014). The first statistic reflects the enormous potential that programming has for doing and learning mathematics. The second served as the inspiration for our research: why would such a gap exist? In response to this question, we put forth an exploratory study aimed at better understanding the place of programming in mathematical research and university mathematics education. Semi-directed interviews were conducted with 14 mathematicians working within various mathematical subfields at different universities across Canada. Our qualitative analysis allows us to describe the ways in which these mathematicians construct computer programs in order to accomplish several tasks (e.g., simulating real-world phenomena, doing "experimental" mathematics, developing new powerful tools). It also allows us to identify some moments where the mathematicians expose their students to certain elements of these research practices. We notice, however, that the students are rarely invited to conceptualize and write their own programs. In the end, our participants highlight several institutional constraints: the curriculum, departmental culture, human resources, the traditions in mathematics, etc. Some of these constraints, which seem to be limiting the mathematical experience of some undergraduate students, could warrant re-examination.

Thesis (Ph. D.)--Harvard University, 1985. / Includes bibliographical references (p).