Algorithmes en ISN

Bonjour à tous,
je lance ce topic pour recenser des idées d'algorithmes à proposer/à faire exécuter à la main/à faire implémenter à des élèves d'ISN.
(informatique et sciences du numérique, une spécialité de terminale S).

Quelques idées en vrac (mais je m'interroge sur la faisabilité) :
* exploration systématique d'un arbre (en largeur ou en profondeur) (y compris générer toutes les possibilités en dénombrement)
* sur les listes : retourner, chercher min max, accumulation, rechercher un élément, compter
* tracer une droite, un arc de cercle, pixel par pixel
* des algos de graphes pas trop compliqués genre Kruskal, Welsh-Powell, Dijkstra

Quelqu'un a essayé ce genre de choses ? Des retours d'expérience ?

J'ai tenté Djikstra, mais sans implémentation, ça marche très bien. Pour les listes, retourner, min/max, recherche d'un élément (une occurrence ou toute), l'implémentation n'a pas posé de problème.
Pour les arbres, je leur fais faire à la main (une séance sans ordinateur du tout) un codage de Huffman, c'est un peu long, il faut penser à leur donner l'arbre tout fait une fois qu'ils ont bien cherché (sinon impossible de traduire le texte codé). J'aime bien, ça leur montre un algo qu'ils perçoivent comme non mathématique contrairement aux autres.

Bonjour,
En Python pour la mise en oeuvre, j'ai fait faire un convertisseur numération shadock/décimal (ce qui a été pour certains la découverte du monde des shadocks - et de l'INA), la suite de syracuse (avec durée de vol, vol en altitude ...), le polynôme du diable (retour sur les bases de numération), un rendu de monnaie (avec parfois une caisse incomplète), le jeu du "plus ou moins" (et les vertus de la dichotomie), la vérification d'un mot de passe (2 saisies + critères), et bien sûr le chiffrement d'un message et le crible d'Eratosthène. Tout ça sous forme de "mini-projets" (description de l'algorithme puis de sa mise en oeuvre).

Merci de vos réponses à tous les deux.
Voltaire, c'est ça l'idée, de leur donner un contexte, de leur demander de résoudre un problème algorithmiquement (avec un algo fourni ou pas) puis de passer au tableau (et au video) pour exposer leur démarche sous forme de mini-projet.

Le truc est de chercher des algorithmes qui ne ressemblent pas à ce qu'ils font en maths, vu le profil des élèves...

Huffman n'est pas mal pour ça, mais est plus délicat à implémenter (sauf si on travaille sur des chaînes de caractères du genre '11011001110110001' pour représenter les binaires ?). Et si on fait un gros switch ça va être chiant ; par contre avec un dict du genre {'a': '100', 'b': '10011'} ça pourrait être plus agréable ?

Hélips, pour le retournement de liste tu as fait un truc récursif ?

Le système de numération des shadoks on l'a projeté en classe au moment où on a travaillé le binaire :-) Le son est un peu pourri hélas.

Dichotomie, Syracuse, Eratosthène, ça me semble trop mathématique pour le public que j'ai (bon il y en a quand même 3 qui tournent à 15 en maths mais la norme est plutôt 6). Ou alors avec une partie visualisation, mais on s'éloigne de l'algo pure.

Quelqu'un a tenté de la géo algorithmique, genre Voronoï ou plongement Euclidien (tu as une matrice de distances et tu veux placer chaque sommet dans R² au mieux) ?

Pour Dijkstra, il me semble qu'il faut déjà avoir bossé sur une sorte de bibliothèque maison sur les graphes avant d'espérer l'implémenter, avec en particulier le choix d'une représentation des graphes (listes d'adjacence ou matrice d'adjacence), ça me semble ambitieux pour un mini-projet sauf à passer deux séances en classe dessus avant, non ? Par contre à la main ça se fait bien (j'ai même un diapo qui traîne, pour les spé ES). Mais mon objectif est d'arriver à un truc implémenté (modeste mais implémenté).

Peut-être un peu de programmation dynamique avec "on a des pièces de 13 zlotys, 80 zlotys et 24 zlotys, peut-on arriver à une somme de 3215 zlotys ?"

Bref je cherche des problèmes super spécifiques :
* énoncé pas trop mathématique
* besoin de réfléchir à la représentation des données
* algorithme pas trivial mais pas trop compliqué
* un truc codable sans utiliser de fonctionnalités exotiques...

C'est pas simple !

Spoiler:

Pour les retournements, en fait, j'ai traité ça par la question suivante : pondre un programme qui teste si un mot ou une phrase est palindrome. Certains ont comparé les caractères, d'autres ont créer une nouvelle chaine en retournant la première et ont comparé les chaines.

Pour Huffman, voilà ce que je leur donne. L'arbre tout fait étant donné juste avant qu'ils commencent le décodage.

OK merci :-)
Je pense que ça va me faire une séance en janvier.

En papier crayon on a fait un truc sympa en décembre, qui a bien marché.
A partir du document joint (trouvé sur internet il y a quelques années), la question était de calculer P5. D'abord on est parti d'un cas particulier, 23154 p.ex, et la question était de trouver le nombre minimal de retournements nécessaire, avec un arbre exploré en largeur.
De 23154 tu peux aller à 32154, 13254, 51324 et 45132.
Un dessin au tableau et on recommence.
Ensuite il s'agissait d'énumérer les 5! positions de départ (et là il s'agit plutôt d'une exploration en profondeur).
Pour finir on a partiellement parallélisé le boulot en se répartissant les positions initiales entre les différents groupes.
Bon on a pas fini mais ça a permis de parler de minoration, majoration, de parcours d'arbres...

http://dl.free.fr/w4kHR2XZh (je n'arrive plus à héberger le pdf sur neo)

Ah oui, sympa ! Merci

Ça fait toujours son petit effet quand les élèves apprennent qu'une bonne partie des scénaristes des Simpsons et de Futurama ont une thèse de maths ou d'info :-)

Le problème était dans les questions du castor:
http://concours.castor-informatique.fr/
épreuve 2014, les questions sur les crèpes.

Merci pour toutes les infos !
Je travaille aussi avec quelques problèmes (simples, mais il vaut mieux tester avant, certains sont plus compliqués qu'il n'y parait) du projet Euler : https://projecteuler.net/

Les premiers sont "trop mathématiques" pour les élèves que j'ai,
les suivants sont trop durs.
Mais le projet Euler est très sympa, c'est vrai !

On peut aussi regarder les sujets d'informatique des concours des grandes écoles.

La réforme de 2013 donne lieu à de nouvelles épreuves plus accessibles que celles de l'option info de 1995 et dont on peut parfois extraire des parties gérables. Même des épreuves "MP-PC" ou "PSI-PT" de l'X peuvent être une bonne source car pendant longtemps, ces épreuves étaient destinées aux préparationnaires qui ne suivaient pas le cours d'informatique de l'option. Et il doit y avoir des trucs potables dans les sujets d'option du concours E3A.

http://concours-maths-cpge.fr/

231 sujets d'informatique à éplucher !
Ça risque de me prendre quelques jours, mais merci pour l'idée :-)

Il y a aussi, assez difficile, faire une division entière avec des entiers plus grands que ceux manipulés par le langage utilisé.

En Python ça risque d'être difficile...
Les entiers n'ont pas de taille maximale !

Oui, mais par exemple chercher la "clé" du numéro de sécu avec une calculatrice (97 - reste modulo 97 dudit numero, qui est bien trop long pour la calculatrice) peut être un vrai challenge (et au passage, "deviner" instantanément le mois, l'année et le département de naissance du père ou de la mère de l'élève assure un certain prestige ...)

Nan mais on fait ça en sixième, pas en ISN...
De toutes façons les spé isn ne font pas spé maths.

>>> 97-2139002555555%97
31
>>> 555**17
44975988072058513345811358442174889373779296875
>>> p=1
>>> for k in range(2,101):
p*=k

>>> p
8709782489089480079416590161944485865569720643940840134215932536243379996346583325877967096332754920644690380762219607476364289411435920190573960677507881394607489905331729758013432992987184764607375889434313483382966801515156280854162691766195737493173453603519594496000000000000000000000000000000000000000000000000
>>>

A la calculatrice ... en python aucun intérêt !

M'ouais, mais c'est le genre de choses qu'on fit plutôt au collège, quand on a le temps (c'est-à-dire quand on a une classe qui a des acquis convenables, et avec laquelle il n'est pas besoin de refaire intégralement le programme des années antérieures).
Je faisais ça en sixième, dans le temps : poser la multiplication de 6713 5849 3219 4162 par 6485 3574 1325 9547. Les groupes de quatre chiffres ne sont pas standards, mais 4 chiffres par 4 chiffres ça tient sur l'écran de la calculatrice.
De temps en temps avec des secondes quand j'y pense on fait du 8 chiffres par 8 chiffres ; la calculatrice affiche 10 chiffres en notation scientifique, on en récupère 9 et on soustrait cette partie ce qui permet de récupérer 4 chiffres de plus. Pour les derniers chiffres, on refait une multiplication avec seulement les derniers chiffres des facteurs initiaux.

P.ex


On a déjà les 9 premiers chiffres (le 10e peut avoir été arrondi) puis 4 en plus (là aussi attention à un éventuel arrondi).


95642358*46875214=4483255998714612

A la réflexion, ça pourrait être sympa de bosser ce genre de trucs en isn, mais alors en binaire, et pas plus d'une séance, car c'est plutôt marginal dans le programme me semble-t-il.

ben2510 a écrit:quand on a le temps (c'est-à-dire quand on a une classe qui a des acquis convenables, et avec laquelle il n'est pas besoin de refaire intégralement le programme des années antérieures).

Mon rêve ...

Moi j'aime bien l'écriture avec boucles et automates à pile, pour transformer ça en récursivité.

Exemple : Partir d'un entier et l'écrire en supposant qu'on ne dispose que de la primitive "print(i) pour i compris entre 0 et 9 et de la division par dix. Une fois le truc fait (laborieusement) en gérant la pile dans un tableau en mémoire, montrer comment on peut traiter ça élégamment en récursivité. C'est un bon exemple pour expliquer le passage de paramètres par valeur et le stockage des paramètres et adresses de retour dans la pile d'exécution.

Exemple : faire construire un arbre binaire pour classer des nombres arrivant aléatoirement. Faire une recherche dans l'arbre, un parcours de l'arbre pour tri. Si on a java, montrer que cela peut se faire en quelque lignes avec des objets de type "TreeSet".

Je pense aussi qu'il est indispensable d'initier les élèves à l'utilisation d'API. Plutôt que de toujours travailler sur des opérations de base du langage, prendre un peu de distance avec l'algo en donnant une API et en demandant de l'utiliser. L'informatique graphique est idéale pour ça.

Différents algorithmes de tri (tri à bulle par exemple). Ce sont des grands classiques.

zizou0105 a écrit:Différents algorithmes de tri (tri à bulle par exemple). Ce sont des grands classiques.

Pédagogiquement intéressant, mais ne pas oublier de montrer qu'aujourd'hui on ne programme plus ça, sauf à être maso. En java :

Code:

import java.util.TreeSet ;
public class Tri {
    public static void main (String [] args) {
        // Trieur générique pour objets Integer
        TreeSet <Integer> trieur = new TreeSet <> () ;
        // Génération de 100 entiers aléatoires, rangement dans le trieur
        for (int i = 1 ; i <= 100 ; i++)
            trieur.add (new Integer ((int)(Math.random() * 1000))) ;
        // Ecriture de la liste triée
        for (Integer x : trieur)
            System.out.println (x) ;
    }
}

Oui, mais de la même façon qu'on ne calcule pas un polynôme caractéristique à la main, etc.

C'est quand je vois des codes comme ça que je me dis que, pédagogiquement, Python, c'est pas mal…

Lorsque le programme d'isn est sorti, le langage recommandé était java.
Bizarrement, tout le monde utilise Python.

truc.sort()

C'est moins pesant que le java, non ?