[PDF] [PDF] Articulations preuves – algorithmes – programmes Questions - A Zitt

[PDF] Algorithmique au lycée

Ecrire l'algorithme associé à ce programme de calcul Un professeur s'identifie sur le réseau informatique en entrant le code 4 732 suivi de la clé 7 L'accès au mathématiques et les problèmes posés doivent être en relation avec les 

[PDF] LE PROGRAMME DALGORITHMIQUE SANS - Maths ac-creteil

cycle 4 : notion d'algorithme, branchement conditionnel, boucle, et variable informatique Chaque activité suit Marcel qui se prépare pour aller à l'école

[PDF] Partie 2 : Comment écrire un algorithme ? Quest-ce quune variable

12 sept 2014 · Algorithme Puissance // algorithme qui calcule une puissance d'un nombre entiers en maths (ceux qu'on peut écrire selon une règle d'écriture donnée et qui dépend du langage informatique) • Les « int » en C (sur mon 

[PDF] ALGORITHMIQUE

Exemple de progression pour aborder l'algorithmique en seconde Algorithmes au programme Fonctions mathématiques Racine carrée EXERCICE( d' après un exercice de l'IOI(olympiade internationale d'informatique)) Sur la planètes 

[PDF] exercices corrigés algorithmepdf

Exercice 5 2 Ecrire un algorithme qui demande un nombre compris entre 10 et 20, jusqu'à ce que la réponse convienne En cas de réponse supérieure à 20, 

[PDF] Algorithmique et programmation - USTO

le cours d'Informatique est devenu obligatoire pour la majorité des sections de la Faculté de génie cet algorithme au moyen d'un langage de programmation En mathématiques, c'est une expression contenant une ou plusieurs variables 

[PDF] Articulations preuves – algorithmes – programmes Questions - A Zitt

Questions didactiques à l'interface mathématiques – informatique Antoine Quelles interactions entre programme, algorithme et démonstration ? 14 / 35 

[PDF] Maths Algorithmes

[PDF] Maths argumenter

[PDF] Maths assé simple a comprendre d'après les autres

[PDF] Maths au secours aidez moi !!!!!!!!!!!!!!!!!!!!

[PDF] maths au travail segpa pdf

[PDF] Maths avec les égyptiens

[PDF] maths bac pro

[PDF] Maths besoin d'aide

[PDF] Maths besoin d'aide svp Pour calculer 35/8 svp

[PDF] maths besoin de verification merci

[PDF] Maths brevet

[PDF] maths bts cg

[PDF] Maths calcul

[PDF] maths calcul 5éme

[PDF] maths calcul besoin d'aide

Articulations preuves - algorithmes - programmes

Questions didactiques à l"interface mathématiques - informatique

Antoine Meyer

1Simon Modeste2

1 LIGM, Université Paris Est - Marne-la-Vallée 2

I3M / DÉMa, Université Montpellier II

Journée "Interface math-info", 17 janvier 2016

1/35

Avant de commencer...

Question

C"est quoi, pour vous, le rapport entre l"informatique et les math?

Micro-trottoir fantasmé :

I "Je ne veux pas en (entendre) parler"I "Geogebra et LibreOffice"I "Algobox, HP et Casio"I "Piaget, Papert et Logo"I "Scratch (c"est nul, et je déteste ce chat)"I "Encore un truc que nous impose qui vous savez"I "Aucun, l"info c"est l"affaire des profs de techno"I "L"info est une branche des math"2/35

Avant de commencer...

Question

C"est quoi, pour vous, le rapport entre l"informatique et les math?

Micro-trottoir fantasmé :

I "Je ne veux pas en (entendre) parler"I "Geogebra et LibreOffice"I "Algobox, HP et Casio"I "Piaget, Papert et Logo"I "Scratch (c"est nul, et je déteste ce chat)"I "Encore un truc que nous impose qui vous savez"I "Aucun, l"info c"est l"affaire des profs de techno"I "L"info est une branche des math"3/35

Avant de commencer...

Question

C"est quoi, pour vous, le rapport entre l"informatique et les math?

Micro-trottoir fantasmé :

I "Je ne veux pas en (entendre) parler"I "Geogebra et LibreOffice"I "Algobox, HP et Casio"I "Piaget, Papert et Logo"I "Scratch (c"est nul, et je déteste ce chat)"I "Encore un truc que nous impose qui vous savez"I "Aucun, l"info c"est l"affaire des profs de techno"I "L"info est une branche des math"4/35

Avant de commencer...

Question

C"est quoi, pour vous, le rapport entre l"informatique et les math?

Micro-trottoir fantasmé :

I "Je ne veux pas en (entendre) parler"I "Geogebra et LibreOffice"I "Algobox, HP et Casio"I "Piaget, Papert et Logo"I "Scratch (c"est nul, et je déteste ce chat)"I "Encore un truc que nous impose qui vous savez"I "Aucun, l"info c"est l"affaire des profs de techno"I "L"info est une branche des math"5/35

Avant de commencer...

Question

C"est quoi, pour vous, le rapport entre l"informatique et les math?

Micro-trottoir fantasmé :

I "Je ne veux pas en (entendre) parler"I "Geogebra et LibreOffice"I "Algobox, HP et Casio"I "Piaget, Papert et Logo"I "Scratch (c"est nul, et je déteste ce chat)"I "Encore un truc que nous impose qui vous savez"I "Aucun, l"info c"est l"affaire des profs de techno"I "L"info est une branche des math"6/35

Avant de commencer...

Question

C"est quoi, pour vous, le rapport entre l"informatique et les math?

Micro-trottoir fantasmé :

I "Je ne veux pas en (entendre) parler"I "Geogebra et LibreOffice"I "Algobox, HP et Casio"I "Piaget, Papert et Logo"I "Scratch (c"est nul, et je déteste ce chat)"I "Encore un truc que nous impose qui vous savez"I "Aucun, l"info c"est l"affaire des profs de techno"I "L"info est une branche des math"7/35

Avant de commencer...

Question

C"est quoi, pour vous, le rapport entre l"informatique et les math?

Micro-trottoir fantasmé :

I "Je ne veux pas en (entendre) parler"I "Geogebra et LibreOffice"I "Algobox, HP et Casio"I "Piaget, Papert et Logo"I "Scratch (c"est nul, et je déteste ce chat)"I "Encore un truc que nous impose qui vous savez"I "Aucun, l"info c"est l"affaire des profs de techno"I "L"info est une branche des math"8/35

Avant de commencer...

Question

C"est quoi, pour vous, le rapport entre l"informatique et les math?

Micro-trottoir fantasmé :

I "Je ne veux pas en (entendre) parler"I "Geogebra et LibreOffice"I "Algobox, HP et Casio"I "Piaget, Papert et Logo"I "Scratch (c"est nul, et je déteste ce chat)"I "Encore un truc que nous impose qui vous savez"I "Aucun, l"info c"est l"affaire des profs de techno"I "L"info est une branche des math"9/35

Avant de commencer...

Question

C"est quoi, pour vous, le rapport entre l"informatique et les math?

Micro-trottoir fantasmé :

I "Je ne veux pas en (entendre) parler"I "Geogebra et LibreOffice"I "Algobox, HP et Casio"I "Piaget, Papert et Logo"I "Scratch (c"est nul, et je déteste ce chat)"I "Encore un truc que nous impose qui vous savez"I "Aucun, l"info c"est l"affaire des profs de techno"I "L"info est une branche des math"10/35

Interactions math - info

Dans la recherche :

I

Histoire partagée, apports mutuels?

I Notions et thématiques communes, voisines, spécifiques? I Préoccupations, approches, méthodes, raisonnements?

Dans l"enseignement, la formation :

I Math et info dans le secondaire? Dans le supérieur? I

Informatique outil vs. discipline informatique?

I

Provenance et formation des enseignants?

Dans la classe (de math, ou ailleurs) :

I Quelles notions, à quel niveau, avec quels prérequis? I Quelles activités mêlant les deux disciplines? I

Pour quels objectifs d"apprentissage?

11/35

Nos questions de recherche

Projet en deux parties non indépendantes

I

Partie épistémologique :

contribuer à identifier les champs, notions, conceptions, modes de pensée communs ou spécifiques aux deux disciplines et leurs effets l"une sur l"autre I

Partie didactique :

contribuer à élab oreret exp érimenterdes ressources de formation et d"enseignement riches à l"interface math-info, au secondaire et au supérieur 12/35

Axes d"analyse

Valeurs mathématiques et valeurs informatiques

I Nombre mathématique (N,R...) et nombre informatique (int,float...) I Types et structures de données, codage, représentation I Types de données abstraits et jeu d"opérations I Algorithmes idéaux (précision arbitraire) ou implémentés

Rôles et statuts des variables

I Math : inconnue, variable substitutive, variable formelle I Logique : variable libre ou muette, quantification, portée I Programmation : portée, durée de vie,temporalité, paramètres formels ou effectifs 13/35

Axes d"analyse

Logique, langage et nature du raisonnement

I Décomposition en sous-problèmes : parallèle entre lemme et sous-programme, encapsulation I

Récurrence / induction / récursion

I Preuves constructives et complexité / preuves d"existence I

Question de l"implicite et de l"explicite

I Niveau de langue / niveau de langage (de programmation) I

Question de l"abstractionDans cet exposé (restriction n°1)Quelles interactions entre programme, algorithme et démonstration?

14/35

Définitions

Démonstration ou preuve

Suite d"arguments visant à établir une proposition, à partir d"un ensemble de propositions déjà établies ou admises Une preuve peut faire appel à différents types de raisonnements (disjonction de cas, preuve par l"absurde, récurrence...) en principe formalisables en logiquePreuve formelle Preuve exprimée dans un système de déduction fo rmelle (incluant axiomes et règles de déduction), contenant toutes les étap eslogiques élémentaires permettant d"aboutir à la proposition souhaitée 15/35

Définitions

Algorithme

Procédure

systématique de résolution de p roblème , qui permet de résoudre toute instance du p roblèmeen un nomb re fini d"étap eset à l"aide d"un ensemble fini d" opérations élémentairesProgramme Suite d"instructions ou d"opérations obéissant à la syntaxe d"un langage de programmation , destinée à être exécutée par une machine selon une certaine sémantique 16/35

Preuves, algorithmes, programmes

Programme$algorithme

I Un algorithmepeutêtre implémenté sous forme de programme I Un programme (ou " quasi-programme »)peutservir à décrire un algorithme

Algorithme$preuve

I L"analyse d"un algorithme (ou d"un programme) peut requérir une ou plusieurs démonstrations I Une démonstration mathématique " constructive » peut contenir ou mener à un algorithme (implicite ou explicite)

Preuve formelle$programme

I

Cas des assistants de preuve (en France : Coq)

I

Vérification formelle de programmes

17/35

Preuves, algorithmes, programmes

Plus généralement :

I

Dialectique

outil / objet , diverses conceptions de l"algorithme vis-à-vis des mathématiques (M odeste,2012) I Quels concepts, méthodes, types de raisonnements, champs d"application... communs ou spécifiques? I

Quelles conséquences didactiques?Dans cet exposé (restriction n°2)Quelques exemples de preuves d"algorithmes

18/35

Divers types de preuves d"algorithmes

Preuve de terminaison :

I L"algorithme s"arrête sur toute entrée annoncée comme valide I Techniques : décroissance dans un ordre bien fondé, convergence de suite...

Preuve de correction :

I L"algorithme fournit le bon résultat quelle que soit l"instance I Techniques : preuve d"invariant, récurrence / induction

Complexité :

I Bornes supérieures et/ou inférieures sur les ressources (temps, espace...), au pire ou en moyenne I Techniques : dénombrement, résolution de suites récurrentes, réductions, théorie de l"information... 19/35

Exemple 1 : algorithme d"Euclide

Problème :

Soient ab0 deux naturels, calculer le p.g.c.d. dea etb(plus grand naturelcdivisantaetbou 0 siaetbnuls)AlgorithmeA1Soit la suite(ri)i0telle que (r

0=a;r1=b

r i+2=rimodri+1: Résultat : premierrnt.q.rn+1=0.AlgorithmeA3defpgcd (a, b): while b 0 a, b b, a b return a AlgorithmeA2Le résultat estasib=0, et le p.g.c.d. debetamodbsinon.AlgorithmeA4defpgcd (a, b): if b 0 return a else return pgcd(b, a b) 20/35

Exemple 1 : algorithme d"Euclide

Problème :

Soient ab0 deux naturels, calculer le p.g.c.d. dea etb(plus grand naturelcdivisantaetbou 0 siaetbnuls)AlgorithmeA1Soit la suite(ri)i0telle que (r

0=a;r1=b

r i+2=rimodri+1: Résultat : premierrnt.q.rn+1=0.AlgorithmeA3defpgcd (a, b): while b 0 a, b b, a b return a AlgorithmeA2Le résultat estasib=0, et le p.g.c.d. debetamodbsinon.AlgorithmeA4defpgcd (a, b): if b 0 return a else return pgcd(b, a b) 21/35

Exemple 1 : algorithme d"Euclide

Problème :

Soient ab0 deux naturels, calculer le p.g.c.d. dea etb(plus grand naturelcdivisantaetbou 0 siaetbnuls)AlgorithmeA1Soit la suite(ri)i0telle que (r

0=a;r1=b

r i+2=rimodri+1: Résultat : premierrnt.q.rn+1=0.AlgorithmeA3defpgcd (a, b): while b 0 a, b b, a b return a AlgorithmeA2Le résultat estasib=0, et le p.g.c.d. debetamodbsinon.AlgorithmeA4defpgcd (a, b): if b 0 return a else return pgcd(b, a b) 22/35

Exemple 1 : algorithme d"Euclide

Problème :

Soient ab0 deux naturels, calculer le p.g.c.d. dea etb(plus grand naturelcdivisantaetbou 0 siaetbnuls)AlgorithmeA1Soit la suite(ri)i0telle que (r

0=a;r1=b

r i+2=rimodri+1: Résultat : premierrnt.q.rn+1=0.AlgorithmeA3defpgcd (a, b): while b 0 a, b b, a b return a AlgorithmeA2Le résultat estasib=0, et le p.g.c.d. debetamodbsinon.AlgorithmeA4defpgcd (a, b): if b 0 return a else return pgcd(b, a b) 23/35

Exemple 1 : algorithme d"Euclide

quotesdbs_dbs47.pdfusesText_47