Voir le sujet précédentAller en basVoir le sujet suivant
ben2510
ben2510
Expert spécialisé

Algorithmes en ISN Empty Algorithmes en ISN

par ben2510 Mer 21 Déc 2016 - 13:27
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 ?

_________________
On fait la science avec des faits, comme on fait une maison avec des pierres : mais une accumulation de faits n'est pas plus une science qu'un tas de pierres n'est une maison. Henri Poincaré  La notion d'équation différentielle est le pivot de la conception scientifique du monde. Vladimir Arnold
Hélips
Hélips
Prophète

Algorithmes en ISN Empty Re: Algorithmes en ISN

par Hélips Mer 21 Déc 2016 - 13:37
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.

_________________
Un jour, je serai prof, comme ça je serai toujours en vacances.
Voltaire
Voltaire
Niveau 10

Algorithmes en ISN Empty Re: Algorithmes en ISN

par Voltaire Mer 21 Déc 2016 - 14:49
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).
ben2510
ben2510
Expert spécialisé

Algorithmes en ISN Empty Re: Algorithmes en ISN

par ben2510 Mer 21 Déc 2016 - 15:17
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:

_________________
On fait la science avec des faits, comme on fait une maison avec des pierres : mais une accumulation de faits n'est pas plus une science qu'un tas de pierres n'est une maison. Henri Poincaré  La notion d'équation différentielle est le pivot de la conception scientifique du monde. Vladimir Arnold
Hélips
Hélips
Prophète

Algorithmes en ISN Empty Re: Algorithmes en ISN

par Hélips Mer 21 Déc 2016 - 15:37
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.

_________________
Un jour, je serai prof, comme ça je serai toujours en vacances.
ben2510
ben2510
Expert spécialisé

Algorithmes en ISN Empty Re: Algorithmes en ISN

par ben2510 Mer 21 Déc 2016 - 18:07
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)

_________________
On fait la science avec des faits, comme on fait une maison avec des pierres : mais une accumulation de faits n'est pas plus une science qu'un tas de pierres n'est une maison. Henri Poincaré  La notion d'équation différentielle est le pivot de la conception scientifique du monde. Vladimir Arnold
Hélips
Hélips
Prophète

Algorithmes en ISN Empty Re: Algorithmes en ISN

par Hélips Mer 21 Déc 2016 - 20:01
Ah oui, sympa ! Merci Smile

_________________
Un jour, je serai prof, comme ça je serai toujours en vacances.
ben2510
ben2510
Expert spécialisé

Algorithmes en ISN Empty Re: Algorithmes en ISN

par ben2510 Jeu 22 Déc 2016 - 0:09
Ç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 :-)

_________________
On fait la science avec des faits, comme on fait une maison avec des pierres : mais une accumulation de faits n'est pas plus une science qu'un tas de pierres n'est une maison. Henri Poincaré  La notion d'équation différentielle est le pivot de la conception scientifique du monde. Vladimir Arnold
ycombe
ycombe
Monarque

Algorithmes en ISN Empty Re: Algorithmes en ISN

par ycombe Jeu 22 Déc 2016 - 0:55
Le problème était dans les questions du castor:
http://concours.castor-informatique.fr/
épreuve 2014, les questions sur les crèpes.


_________________
Assurbanipal: "Passant, mange, bois, divertis-toi ; tout le reste n’est rien".

Franck Ramus : "Les sciences de l'éducation à la française se font fort de produire un discours savant sur l'éducation, mais ce serait visiblement trop leur demander que de mettre leur discours à l'épreuve des faits".
Voltaire
Voltaire
Niveau 10

Algorithmes en ISN Empty Re: Algorithmes en ISN

par Voltaire Jeu 22 Déc 2016 - 9:46
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/
ben2510
ben2510
Expert spécialisé

Algorithmes en ISN Empty Re: Algorithmes en ISN

par ben2510 Jeu 22 Déc 2016 - 21:18
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 fait la science avec des faits, comme on fait une maison avec des pierres : mais une accumulation de faits n'est pas plus une science qu'un tas de pierres n'est une maison. Henri Poincaré  La notion d'équation différentielle est le pivot de la conception scientifique du monde. Vladimir Arnold
avatar
e1654d
Niveau 7

Algorithmes en ISN Empty Re: Algorithmes en ISN

par e1654d Sam 31 Déc 2016 - 11:31
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/
ben2510
ben2510
Expert spécialisé

Algorithmes en ISN Empty Re: Algorithmes en ISN

par ben2510 Sam 31 Déc 2016 - 14:51
231 sujets d'informatique à éplucher !
Ça risque de me prendre quelques jours, mais merci pour l'idée :-)

_________________
On fait la science avec des faits, comme on fait une maison avec des pierres : mais une accumulation de faits n'est pas plus une science qu'un tas de pierres n'est une maison. Henri Poincaré  La notion d'équation différentielle est le pivot de la conception scientifique du monde. Vladimir Arnold
verdurin
verdurin
Habitué du forum

Algorithmes en ISN Empty Re: Algorithmes en ISN

par verdurin Sam 4 Fév 2017 - 20:50
Il y a aussi, assez difficile, faire une division entière avec des entiers plus grands que ceux manipulés par le langage utilisé.

_________________
Contre la bêtise, les dieux eux mêmes luttent en vain.
Ni centidieux, ni centimètres.
ben2510
ben2510
Expert spécialisé

Algorithmes en ISN Empty Re: Algorithmes en ISN

par ben2510 Sam 4 Fév 2017 - 22:30
En Python ça risque d'être difficile...
Les entiers n'ont pas de taille maximale !

_________________
On fait la science avec des faits, comme on fait une maison avec des pierres : mais une accumulation de faits n'est pas plus une science qu'un tas de pierres n'est une maison. Henri Poincaré  La notion d'équation différentielle est le pivot de la conception scientifique du monde. Vladimir Arnold
Voltaire
Voltaire
Niveau 10

Algorithmes en ISN Empty Re: Algorithmes en ISN

par Voltaire Sam 4 Fév 2017 - 22:54
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 ...)
ben2510
ben2510
Expert spécialisé

Algorithmes en ISN Empty Re: Algorithmes en ISN

par ben2510 Dim 5 Fév 2017 - 0:50
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
>>>




_________________
On fait la science avec des faits, comme on fait une maison avec des pierres : mais une accumulation de faits n'est pas plus une science qu'un tas de pierres n'est une maison. Henri Poincaré  La notion d'équation différentielle est le pivot de la conception scientifique du monde. Vladimir Arnold
Voltaire
Voltaire
Niveau 10

Algorithmes en ISN Empty Re: Algorithmes en ISN

par Voltaire Dim 5 Fév 2017 - 9:21
A la calculatrice ... en python aucun intérêt !
ben2510
ben2510
Expert spécialisé

Algorithmes en ISN Empty Re: Algorithmes en ISN

par ben2510 Dim 5 Fév 2017 - 12:15
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

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

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.

_________________
On fait la science avec des faits, comme on fait une maison avec des pierres : mais une accumulation de faits n'est pas plus une science qu'un tas de pierres n'est une maison. Henri Poincaré  La notion d'équation différentielle est le pivot de la conception scientifique du monde. Vladimir Arnold
Voltaire
Voltaire
Niveau 10

Algorithmes en ISN Empty Re: Algorithmes en ISN

par Voltaire Dim 5 Fév 2017 - 15:07
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 ...
JiPe38
JiPe38
Niveau 5

Algorithmes en ISN Empty Re: Algorithmes en ISN

par JiPe38 Dim 5 Fév 2017 - 19:27
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.
zizou0105
zizou0105
Niveau 2

Algorithmes en ISN Empty Re: Algorithmes en ISN

par zizou0105 Dim 12 Fév 2017 - 21:51
Différents algorithmes de tri (tri à bulle par exemple). Ce sont des grands classiques.
JiPe38
JiPe38
Niveau 5

Algorithmes en ISN Empty Re: Algorithmes en ISN

par JiPe38 Lun 13 Fév 2017 - 9:55
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) ;
    }
}
avatar
e1654d
Niveau 7

Algorithmes en ISN Empty Re: Algorithmes en ISN

par e1654d Lun 13 Fév 2017 - 9:59
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…
ben2510
ben2510
Expert spécialisé

Algorithmes en ISN Empty Re: Algorithmes en ISN

par ben2510 Lun 13 Fév 2017 - 15:30
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 ?

_________________
On fait la science avec des faits, comme on fait une maison avec des pierres : mais une accumulation de faits n'est pas plus une science qu'un tas de pierres n'est une maison. Henri Poincaré  La notion d'équation différentielle est le pivot de la conception scientifique du monde. Vladimir Arnold
Voir le sujet précédentRevenir en hautVoir le sujet suivant
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum