Programmation en C - Page 6 — Les-mathematiques.net The most powerful custom community solution in the world

Programmation en C

12346»

Réponses

  • dpdp
    Modifié (February 2023)
    Attention, ne me fait pas dire ce que je n'ai pas dit. Évidement que ce n'est pas en L3 qu'il faut en parler à des étudiants maths/info : ce serait beaucoup trop tard. Néanmoins, les étudiants de @gebrane ne sont, semble-t-il, pas des étudiants des filières maths/info. De fait, ce serait plutôt en L2 qu'il faudrait leur en parler – voir jamais et leur apprendre à demander à des personnes dont c'est le métier de développer leurs outils (après tout quand il s'agit de créer des microscopes, télescopes, spectromètres de masses et autres, ils demandent bien à des personnes dont c'est le métier) mais c'est une autre histoire :D – si en revanche je me trompe et que @gebrane a bien la charge d'étudiants maths/info alors qu'il ne traine pas et qu'il leur en parle maintenant (et nous le fasse savoir une bonne fois pour toute), oui !
  • Modifié (February 2023)
    parisse a dit :
    La recherche de l'atome dans une table non triée est inefficiente. Il vaut beaucoup mieux trier le tableau par ordre alphabétique en utilisant une fonction de tri dans l'éditeur du code source, ceci afin de permettre une recherche dichotomique : avec un tableau périodique complet, on passe d'une cinquantaine de comparaisons en moyenne à 7 ou 8. Si on ne veut pas coder de recherche dichotomique, on peut au moins trier la liste par ordre décroissant de présence des éléments dans une formule chimique pour faire le moins d'itérations possibles.
    Il suffit de mieux réfléchir au mapping que l'on peut effectuer. En l'occurrence une simple table à double entrée (majuscule x minuscule avec minuscule éventuellement vide) à valeurs dans l'ensemble des masses molaires. En mémoire cela occupe 676 octets, et ne nécessite aucune recherche (dichotomique ou non). Voici un exemple d'implémentation qui n'utilise aucune bibliothèque extérieure (si ce n'est pour afficher un résultat à l'écran).
    with ada.text_io;
    use  ada.text_io;
    
    procedure chemistry is
    	joker : constant character := character'succ ('z');
    	subtype upper_char is character range 'A' .. 'Z';
    	subtype lower_char is character range 'a' .. joker;
    
    	mass : constant array (upper_char, lower_char) of Natural :=
    	('C' => (joker => 12, 'a' => 40, others => 0), 
    	 'H' => (joker => 1, 'e' => 4, others => 0),
    	 'O' => (joker => 16, others =>	 0), 
    	 others => (others => 0));
    	 	 
    	 function element_number (s : string) return Natural is
    	 	u : upper_char := s (s'first);
    	 	l : lower_char := joker;
    	 	start_digit : positive := s'first + 1;
    	 	n : natural := 0;
    	 begin
    	 	if s'length = 1 then 
    	 		return mass (u, l);
    	 	end if;
    	 	if s (start_digit) in lower_char then 
    	 		l := s (start_digit);
    	 		start_digit := start_digit + 1;
    	 	end if;
    	 	for c in start_digit .. s'last loop
    	 		n := 10 * n + (character'Pos (s(c)) - character'Pos ('0'));
    	 	end loop;
    	 	if n = 0 then n := 1; end if;
    	 	return mass (u, l) * n;
    	 end element_number;
    	 
    	 function value (s: string) return natural is
    	 	e : natural := s'first;
    	 begin
    	 	for i in s'first + 1 .. s'last loop
    	 		if s (i) in upper_char then 
    	 			e := i; exit; 
    	 		end if;
    	 	end loop;
    	 	return (if e = s'first then element_number (s) 
    	 	        else element_number (s (s'first..e - 1)) + value (s(e .. s'last)));
    	 end value;	 
    begin
    	put_line (value ("H2O")'img);
    end chemistry;
    

    On peut bien évidemment séparer dans un autre fichier le tableau "mass" contenant les masses molaires. On pourrait aussi faire passer un automate avant et éventuellement indiquer la première occurrence d'erreur de syntaxe.
  • On peut effectivement optimiser la recherche en utilisant une représentation dense des données dans le cas des symboles chimiques. En C on accèderait à la masse depuis une chaine s normalisée à taille 2 par ajout d'un caractère si nécessaire (caractère non utilisé en minuscule ou caractère supplémentaire joker s'il n'y en a pas) par une instruction
    masse=tab[s[0]-'A'][s[1]-'a']
    Il faut toutefois noter que contrairement à la représentation creuse de la table périodique (où on ne stocke que des valeurs de masse existantes) ce genre de méthode ne fonctionne que sur des données de petite taille (ici 5408 octets si la masse est un double sur 8 octets, contre environ 3 fois moins avec la représentation creuse sur une architecture 32 bits: environ 100*(4+4+8)) et est plus difficile à généraliser, alors que la recherche par dichotomie est un algorithme qui peut servir très souvent. Par exemple ici, si on veut rajouter la possibilité de distinguer des isotopes, il suffit d'ajouter une entrée dans la structure des atomes, alors que la taille des données en représentation dense va augmenter beaucoup plus qu'en représentation creuse. Et puis entrer le tableau de données dense en tableau constant est fastidieux.
  • @parisse : ce que je voulais dire c'est que si l'on dimensionne les données dans ce problème précis (précision sur la masse molaire et nombre d'éléments du tableau) alors on voit que la recherche dichotomique n'est pas le meilleur choix.
    En revanche, s'amuser à modifier un peu l'énoncé pour montrer qu'une recherche dichotomique peut, dans d'autres cas, être un meilleur choix, me semble être une belle progression pédagogique.
    Pour finir, je pense que cet exercice est le point de départ pour enseigner la notion de fonction de hachage dont il existe des implémentations très performantes dans la plupart des langages modernes.
  • C'est discutable, peut-être une différence d'appréciation qui provient de ma culture qui est principalement mathématique.
    La recherche dichotomique (lorsqu'elle est possible) est plus simple et moins couteuse que d'utiliser des fonctions de hachage. L'argument que c'est disponible de manière efficace dans beaucoup de langages n'a pas beaucoup d'importance à mes yeux d'un point de vue pédagogique, au sens où je pense qu'il faut éviter au maximum l'utilisation de boites noires.
    La notion de stockage creux ou dense des données me parait plus intéressante comme prolongement. Par exemple pour représenter des polynômes à une ou plusieurs variables, ce qui est un ingrédient essentiel de tout logiciel de calcul formel. Choisir la bonne structure de donnée, par exemple pour les multiplier efficacement, fait intervenir la taille des données, le nombre de variables et les degrés, la taille de RAM disponible mais aussi la taille des caches (ce genre de choix est fait de manière dynamique dans Xcas, en fonction des arguments).
  • au sens où je pense qu'il faut éviter au maximum l'utilisation de boites noires

    Je lisais il y a 2 ou 3 semaines sur un autre forum un avis totalement opposé.

    Dans l'enseignement de l'informatique, à un moment ou à un autre, on va apprendre au futur programmeur à faire par exemple un programme de tri. On va lui parler de tri-bulle et de 2 ou 3 autres méthodes de tri. Mais plus tard, on va lui dire : ce truc de tri que tu as programmé, surtout, dans ta vraie vie de programmeur, ne refais jamais ça. Utilise telle boite noire qui fait ça 1000 fois mieux que ce que tu as fait.

    Et on va lui apprendre à utiliser des boites noires.

    Certes, il va y avoir des exceptions. Certains informaticiens ne vont pas utiliser les boites noires développées par d'autres, ils vont créer ces boites noires. Mais ils sont minoritaires.

    Les menuisiers à qui on demande de faire de la plomberie, ou plutôt les chimistes à qui on demande de faire de l'informatique, ça ne me choque pas du tout. La double culture Informatique/Domaine d'application est un bonus énorme. Un informaticien et un chimiste sont incapables de parler ensemble, s'il n'y a pas l'un des deux qui a appris la langue de l'autre et qui accepte de faire l'effort de parler la langue de l'autre.

    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • @parisse : on s'est compris; tout cela dépend des objectifs visés. Je me permettais simplement de reprendre ta phrase
    La recherche de l'atome dans une table non triée est inefficiente. Il vaut beaucoup mieux trier le tableau par ordre alphabétique en utilisant une fonction de tri dans l'éditeur du code source, ceci afin de permettre une recherche dichotomique

    Cette phrase, sur cet exemple précis dont nous parlons était factuellement fausse.

    Si ton objectif est de présenter une solution alternative dans des cas où il y a davantage de données par une méthode de recherche dichotomique alors je suis d'accord avec toi.

    Je pense qu'en plus ce problème est une bonne introduction aux fonctions de hachage (et autres dictionnaires). Je ne reproche évidemment rien à la recherche dichotomique dès qu'elle est plus efficace que d'autres méthodes. Quant à l'utilisation des fonctions de hachage ou dictionnaires disponibles dans des langages, il s'agit là d'une compétence qu'il est préférable d'avoir plutôt que de ne pas avoir (à condition qu'elle soit utilisée à bon escient, cela va sans dire).

    @lourrran : +1
  • @lourran: il y a une différence énorme entre enseigner/apprendre et utiliser ensuite. Bien entendu, une fois qu'on a acquis une méthode, il est recommandé d'utiliser des librairies qui ont été optimisées en mode boite noire. Mais avant, il est important de comprendre ce qui se passe, en écrivant soi-même ces algorithmes avant de les utiliser en boite noire (et c'est d'ailleurs ce qui a lancé ce fil puisqu'il existe plein de code tout prêt pour calculer un polynôme d'interpolation). C'est exactement pour la même raison que je défends l'utilisation du calcul formel dans l'enseignement des maths : une fois qu'on a compris le principe de certaines opérations symboliques, on peut les utiliser en mode boite noire pour faire des choses plus évoluées. Jamais je ne recommanderai d'utiliser une fonction de calcul formel sans avoir fait soi-même quelques exemples en papier-crayon ou de tête. Je pense la même chose de l'enseignement de l'informatique.

    @troisqua : en quoi ma phrase est-elle factuellement fausse? Je n'ai pas dit que la recherche dichotomique était la méthode la plus efficace, juste qu'elle était plus efficace qu'une comparaison exhaustive. D'autre part, je n'ai rien contre l'utilisation des fonctions de hachage quand c'est utilisé à bon escient (j'en utilise un peu dans Xcas). Mais c'est plus difficile à comprendre (en tout cas pour moi) que de comprendre le principe d'une recherche dichotomique, qui est à la portée d'un élève du secondaire. Ou que la représentation de données creuse ou dense (par exemple pour les polynômes x^100-1 et (x^100-1)/(x-1)).
  • Tu as raison, j'ai effectivement mal lu ta phrase. Tu parlais d'une recherche dans une table non triée qui est effectivement moins efficace que si la recherche est dichotomique dans une table triée.  Je suis d'accord avec toi.
  • Ces interventions sont intéressantes, mais il me semble que l'on traite d'algorithmique, et pas de programmation ... (ce qui renvoie à la question : l'objectif pédagogique est il l'algorithmique ou la programmation ?).
  • @umrk : je suis d'accord. C'est pour ça que gebrane a été relancé plusieurs fois pour connaître les objectifs de ses cours à ses étudiants. C'est loin d'être une question anodine. Je dirais, mais c'est personnel, que c'est là qu'on reconnaît la principale qualité d'un enseignant: "sait-il précisément où il veut emmener ses étudiants/élèves ?" (ce qui nécessite beaucoup de recul sur ce qu'on enseigne et beaucoup de compétences disciplinaires).
    Du coup, si on parle algorithmique, alors je dirais que le problème du tableau périodique est un peu hors sujet (il n'y a pas vraiment d'algorithme, sauf si l'on va du côté des automates pour rendre le parser plus "joli" qu'une simple succession de tests). Si l'on va du côté de la programmation alors il y a des choix plus ou moins pertinents pour représenter les données permettant d'éviter des recherches dichotomiques. Si on veut mettre malgré tout de l'algorithmique alors on peut l'introduire ici (mais ce n'est pas pertinent sur le plan efficacité vu les contraintes sur les données ce qui rend la présentation moins opportune: un meilleur contexte devrait être choisi).

Connectez-vous ou Inscrivez-vous pour répondre.
Success message!