Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/06979.jsonl.gz/1392

La méthode de résolution appliquée par un informaticien ne doit pas seulement fournir un résultat correct, mais devrait aussi être rapide et efficace.
Il existe néanmoins un ensemble de problèmes complexes, pour lesquels seules des méthodes de résolution inefficaces sont connues aujourd'hui : pour certains d'ampleur relativement faible déjà, l'effort de calcul est si énorme qu'il durerait plusieurs années, même sur les ordinateurs les plus puissants. En informatique, la complexité est une mesure de la rapidité de croissance de la puissance de calcul nécessaire, par rapport à l'ampleur du problème.
Le problème du voyageur de commerce
Étant voyageur de commerce, tu dois visiter tous les carrés marqués sur le sol. Trouve le circuit le plus court qui, partant de l’un carré et s’achevant sur un autre, passe exactement une fois par tous les autres carrés. La distance entre deux carrés est chaque fois indiquée.
Le réseau ferroviaire minima
Étant ingénieur des chemins de fer, tu dois relier les carrés de telle sorte que par train, on puisse accéder depuis chaque carré à tous les autres carrés. Et la longueur totale des voies doit être ici la plus courte possible.