Notre thèse de doctorat s'intéresse à l'enseignement et l'apprentissage de savoirs informatiques chez des débutants en France. Elle vise à comprendre comment des débutants mettent en oeuvre et construisent des savoirs informatiques. Nous avons utilisé une méthodologie qualitative de type ethnographique mobilisant des observations, des questionnaires, des entretiens semi-directifs et des analyses de textes officiels et de manuels. Nous avons aussi précédé par une approche comparative des pratiques des lycéens et des étudiants d'une part, et des enseignants, d'autre part. Les résultats montrent des pratiques contrastées, entretenues par des tensions dans le prescrit. Au lycée, en dehors de la spécialité ISN, où l'informatique est rattachée aux mathématiques, les pratiques semblent influencées par quatre facteurs : la motivation (liée aux représentations), la formation continue des enseignants, la jeunesse dans le métier et l'approche pédagogique utilisée. La pratique est focalisée sur l'approche logique de l'algorithmique avec un travail au papier-crayon : la programmation est limitée, et lorsqu'elle a lieu, c'est plus avec une calculatrice mais aussi rarement avec le langage Algobox. Chez les élèves, l'algorithmique est vue comme un nouveau domaine supplémentaire introduit en mathématiques mais différent des mathématiques et de l'informatique. Les très bons élèves en algorithmique sont en général bons en mathématiques. L'ISN accueille des élèves de tous les profils, mais avec des motivations différentes, allant de la découverte de l'informatique dans un contexte formel au refuge des autres spécialités : leurs pratiques sont contrastées. C'est avec l'ISN qu'ils découvrent l'informatique au travers des formes d'enseignement variées et des problèmes de plus en plus complexes. Les pratiques des enseignants restent influencées par leur formation d'origine, avec un manque de recul chez les non-spécialistes d'informatique. À l'Université, les pratiques des étudiants en programmation sont avancées par rapport à celles des lycéens, une avance liée à la complémentarité des modules qui sont dispensés par des spécialistes. Les programmes informatiques ainsi réalisés sont souvent sophistiqués et incorporent des éléments issus de différentes sources externes. Les notions mathématiques investies par les étudiants sont souvent modestes. Si les lycéens et les étudiants sont tous débutants en informatique, les différences de pratiques entre eux semblent liées aux compétences spécifiques des enseignants. Au-delà de la formation des enseignants, la motivation occupe une place fondamentale pour adhérer à cet enseignement/apprentissage et soutenir des pratiques enseignantes comme chez les apprenants. / Our dissertation focuses on the teaching and learning of computer knowledge to beginners in France. It aims to understand how beginners implement and build computer knowledge. We used a qualitative methodology mobilizing ethnographic observations, questionnaire, semi-structured interviews and the analysis of official instructions and textbooks. We also conducted a comparative study of the practice of both school and university students, on the one hand, and teachers, on the other hand. Results show contrasting situations between secondary schools and university. In high school, algorithmic curricula exist within mathematic education. In this case, practice is influenced by four factors: motivation (related to representation), professional development for teachers, youth in business and pedagogical approach. The practice mainly focuses on a logical approach to algorithmic using work paper and pencil: programming is limited, and when it occurs, it is often with a calculator but rarely with the Algobox language. Among students, algorithms are perceived as a new domain in the mathematics programs, but different from both mathematics and informatics. Very good students in computing are generally good at math. Another elective course, specifically about informatics, has also been recently implemented for grade 12 students. It welcomes students of all profiles, but with different motivations, from the discovery of computers in a formal context to a shelter against other elective courses: their practices are manyfold. Within ISN, they discover computers through various forms of education and problems of increasing complexity. Teacher practice is influenced by their original education, with a lack of experience for non specialists teachers. At the University level, students show more advanced practice. They produce computer programs are often sophisticated and incorporate elements from various external sources. The mathematics knowledge invested by students is often modest. If students in lycée and university are all computer beginners, the differences in practice between them seem linked to the specific skills of teachers. In addition to teacher's training, motivation is fundamental to adhere to this teaching/learning and support practice, both for teachers and students.

Notre thèse de doctorat s'intéresse à l'enseignement et l'apprentissage de savoirs informatiques chez des débutants en France. Elle vise à comprendre comment des débutants mettent en oeuvre et construisent des savoirs informatiques. Nous avons utilisé une méthodologie qualitative de type ethnographique mobilisant des observations, des questionnaires, des entretiens semi-directifs et des analyses de textes officiels et de manuels. Nous avons aussi précédé par une approche comparative des pratiques des lycéens et des étudiants d'une part, et des enseignants, d'autre part. Les résultats montrent des pratiques contrastées, entretenues par des tensions dans le prescrit. Au lycée, en dehors de la spécialité ISN, où l'informatique est rattachée aux mathématiques, les pratiques semblent influencées par quatre facteurs : la motivation (liée aux représentations), la formation continue des enseignants, la jeunesse dans le métier et l'approche pédagogique utilisée. La pratique est focalisée sur l'approche logique de l'algorithmique avec un travail au papier-crayon : la programmation est limitée, et lorsqu'elle a lieu, c'est plus avec une calculatrice mais aussi rarement avec le langage Algobox. Chez les élèves, l'algorithmique est vue comme un nouveau domaine supplémentaire introduit en mathématiques mais différent des mathématiques et de l'informatique. Les très bons élèves en algorithmique sont en général bons en mathématiques. L'ISN accueille des élèves de tous les profils, mais avec des motivations différentes, allant de la découverte de l'informatique dans un contexte formel au refuge des autres spécialités : leurs pratiques sont contrastées. C'est avec l'ISN qu'ils découvrent l'informatique au travers des formes d'enseignement variées et des problèmes de plus en plus complexes. Les pratiques des enseignants restent influencées par leur formation d'origine, avec un manque de recul chez les non-spécialistes d'informatique. À l'Université, les pratiques des étudiants en programmation sont avancées par rapport à celles des lycéens, une avance liée à la complémentarité des modules qui sont dispensés par des spécialistes. Les programmes informatiques ainsi réalisés sont souvent sophistiqués et incorporent des éléments issus de différentes sources externes. Les notions mathématiques investies par les étudiants sont souvent modestes. Si les lycéens et les étudiants sont tous débutants en informatique, les différences de pratiques entre eux semblent liées aux compétences spécifiques des enseignants. Au-delà de la formation des enseignants, la motivation occupe une place fondamentale pour adhérer à cet enseignement/apprentissage et soutenir des pratiques enseignantes comme chez les apprenants. / Our dissertation focuses on the teaching and learning of computer knowledge to beginners in France. It aims to understand how beginners implement and build computer knowledge. We used a qualitative methodology mobilizing ethnographic observations, questionnaire, semi-structured interviews and the analysis of official instructions and textbooks. We also conducted a comparative study of the practice of both school and university students, on the one hand, and teachers, on the other hand. Results show contrasting situations between secondary schools and university. In high school, algorithmic curricula exist within mathematic education. In this case, practice is influenced by four factors: motivation (related to representation), professional development for teachers, youth in business and pedagogical approach. The practice mainly focuses on a logical approach to algorithmic using work paper and pencil: programming is limited, and when it occurs, it is often with a calculator but rarely with the Algobox language. Among students, algorithms are perceived as a new domain in the mathematics programs, but different from both mathematics and informatics. Very good students in computing are generally good at math. Another elective course, specifically about informatics, has also been recently implemented for grade 12 students. It welcomes students of all profiles, but with different motivations, from the discovery of computers in a formal context to a shelter against other elective courses: their practices are manyfold. Within ISN, they discover computers through various forms of education and problems of increasing complexity. Teacher practice is influenced by their original education, with a lack of experience for non specialists teachers. At the University level, students show more advanced practice. They produce computer programs are often sophisticated and incorporate elements from various external sources. The mathematics knowledge invested by students is often modest. If students in lycée and university are all computer beginners, the differences in practice between them seem linked to the specific skills of teachers. In addition to teacher's training, motivation is fundamental to adhere to this teaching/learning and support practice, both for teachers and students.

Le développement et l’utilisation de systèmes complexes multi-utilisateurs, ou encore la mise en réseau de systèmes d’observation ou d’information pose des problèmes complexes de partage de ressources entre les utilisateurs. La particularité de ces systèmes, impliquant plusieurs utilisateurs humains ou entités organisationnelles est que le partage des ressources doit satisfaire les préférences souvent antagonistes des utilisateurs et répondre à des exigences d’équité. Ce travail de thèse a pour objet l’étude des problèmes de partage de ressources indivisibles entre des agents ayant des préférences complexes sur ces ressources.Nous nous intéressons plus particulièrement à la modélisation de problèmes de partage en univers risqué.En effet, dans de nombreux problèmes d’allocation de ressources réels, la part revenant réellement à chaque agent après le partage de la ressource dépend de facteurs exogènes. C’est le cas par exemple dans les systèmes d’observation (satellitaires, capteurs embarqués,...), dans lesquels la réalisation d’une requête donnée dépend non seulement des conditions climatiques sur le secteur à observer, mais aussi du bon fonctionnement du capteur, de l’absence de brouillage du signal, etc. L’introduction de risque dans les problèmes de partage implique la redéfinition des notions classiques de choix social (utilité, absence d’envie, ...), et l’agrégation collective des préférences des agents s’en trouve compliquée. Au cours de ce travail de thèse, nous nous sommes tout d’abord intéressés à l’étude de cette extension au risque du formalisme associé aux problèmes de partage classiques : nous proposons un modèle simple de problèmes de partages de biens indivisibles en présence de risque, toutefois assez général pour rester proche des applications réelles considérées, et nous introduisons une extension générale des méthodes d’évaluation non risquées pour de tels partages. La seconde partie de ce travail de thèse porte sur l’algorithmique associée à ces problèmes, dont la résolution est notablement complexifiée par la présence de ressources risquées. Pour plusieurs critères d’évaluation (choisis car visant à garantir une certaine équité des solutions qu’ils suggèrent), nous proposons des algorithmes de résolution exacte et approchée des problèmes de partage associés. / The development and use of complex multi-user systems, or the networking of observation ou information systems raises complex resource allocation problems. The particularity of these systems, which involve several human users or organisational entities, rests in the fact that the share of resources must satisfy the often conflicting preferences of users and comply with equity exigences. This thesis deals with the problem of fairly allocating indivisible goods to a set of agents having complex preferences over these goods.We are more particularly interested in the modeling of fair allocation problems in a risky setting. In numerous real-world resource allocation problems, the actual share each agent receives after the allocation often depends on exogenous factors. This is for instance the case with the observation systems (satellites, embedded sensons, etc.) where the realisation of a request not only depends on weather conditions over the observation area, but also on the potential sensor malfunction, on the absence of jamming of the signal, etc. Introducing the risk in allocation problems implies the redefinition of classical social choice notions such as utility or envy-freeness for instance, and the collective aggregation of agents preferences becomes more complicated. We have studied in this thesis the extension of allocation problem formalism to a risky setting : we present a simple model for risky indivisible goods allocation problems, yet general enough to encompass most of the real-world applications, and we introduce a general extension of risk-free evalution methods for such allocations. The second part of the work concerns the algorithmical issues related to theses problems, whose resolution is significantly complexified because of the risky setting. Forseveral evaluation criteria (selected for the equity of the solutions they suggest) we present both exact and approached resolution algorithms for the related allocation problems.

Réalisé en cotutelle avec l'École normale supérieure de Cachan – Université Paris-Saclay / L'un des aspects fondamentaux des systèmes informatiques modernes, et en particulier des systèmes critiques, est la possibilité d'exécuter plusieurs processus, partageant des ressources communes, de façon simultanée. De par leur nature concurrentielle, le bon fonctionnement de ces systèmes n'est assuré que lorsque leurs comportements ne dépendent pas d'un ordre d'exécution prédéterminé. En raison de cette caractéristique, il est particulièrement difficile de s'assurer qu'un système concurrent ne possède pas de faille. Dans cette thèse, nous étudions la vérification formelle, une approche algorithmique qui vise à automatiser la vérification du bon fonctionnement de systèmes concurrents en procédant par une abstraction vers des modèles mathématiques. Nous considérons deux de ces modèles, les réseaux de Petri et les systèmes d'addition de vecteurs, et les problèmes de vérification qui leur sont associés. Nous montrons que le problème d'accessibilité pour les systèmes d'addition de vecteurs (avec états) à deux compteurs est PSPACE-complet, c'est-à-dire complet pour la classe des problèmes solubles à l'aide d'une quantité polynomiale de mémoire. Nous établissons ainsi la complexité calculatoire précise de ce problème, répondant à une question demeurée ouverte depuis plus de trente ans. Nous proposons une nouvelle approche au problème de couverture pour les réseaux de Petri, basée sur un algorithme arrière guidé par une caractérisation logique de l'accessibilité dans les réseaux de Petri continus. Cette approche nous a permis de mettre au point un nouvel algorithme qui s'avère particulièrement efficace en pratique, tel que démontré par notre implémentation logicielle nommée QCover. Nous complétons ces résultats par une étude des systèmes de transitions bien structurés qui constituent une abstraction générale des systèmes d'addition de vecteurs et des réseaux de Petri. Nous considérons le cas des systèmes de transitions bien structurés à branchement infini, une classe qui inclut les réseaux de Petri possédant des arcs pouvant consommer ou produire un nombre arbitraire de jetons. Nous développons des outils mathématiques facilitant l'étude de ces systèmes et nous délimitons les frontières au-delà desquelles la décidabilité des problèmes de terminaison, de finitude, de maintenabilité et de couverture est perdue. / One fundamental aspect of computer systems, and in particular of critical systems, is the ability to run simultaneously many processes sharing resources. Such concurrent systems only work correctly when their behaviours are independent of any execution ordering. For this reason, it is particularly difficult to ensure the correctness of concurrent systems. In this thesis, we study formal verification, an algorithmic approach to the verification of concurrent systems based on mathematical modeling. We consider two of the most prominent models, Petri nets and vector addition systems, and their usual verification problems considered in the literature. We show that the reachability problem for vector addition systems (with states) restricted to two counters is PSPACE-complete, that is, it is complete for the class of problems solvable with a polynomial amount of memory. Hence, we establish the precise computational complexity of this problem, left open for more than thirty years. We develop a new approach to the coverability problem for Petri nets which is primarily based on applying forward coverability in continuous Petri nets as a pruning criterion inside a backward coverability framework. We demonstrate the effectiveness of our approach by implementing it in a tool named QCover. We complement these results with a study of well-structured transition systems which form a general abstraction of vector addition systems and Petri nets. We consider infinitely branching well-structured transition systems, a class that includes Petri nets with special transitions that may consume or produce arbitrarily many tokens. We develop mathematical tools in order to study these systems and we delineate the decidability frontier for the termination, boundedness, maintainability and coverability problems.