Question aux matheux

OP
BB

BriquetBLOC

il y a 9 mois

Bonjour les kheys

J'étais en train de me remettre dans mes cours d'algèbre et je me suis posé une question, sur les algorithmes

Un algorithme est censé être une série d'instruction finie, avec des entrées et une sortie. Mais admettons que l'algorithme possède une infinité d'étape. Est-ce que cela est seulement possible ? J'aurai tendance à dire oui. Admettons l'algorithme qui admet n (un entier naturel) en entrée et retourne 0 en sortie, quelque soit n. On pourrait écrire une infinité d'instruction (qui ne bouclent pas) entre les deux que ça ne changerait pas la sortie. La sortie pourrait être considérée comme une « limite » de l'algorithme. Si P désigne une des étapes de l'algorithme « infini » 0 est la limite quand P tend vers l'infini.

Le cas est trivial mais suffit largement à illustrer mon propos. En gros, au lieu d'avoir une vision arithmétique de l'algorithme, on pourrait en proposer une vision analytique. Ou la sortie est la limite d'une infinité d'instruction

Qu'en pensez-vous ?

DA

Dazee

il y a 9 mois

On dit que ton algorithme ne finit pas, c'est le problème de l'arrêt si je dis pas n'importe quoi. C'est de l'informatique avant tout

TF

The_ff3_fan

il y a 9 mois

Bah c'est une question de sémantique donc je trouve pas ça super intéressant

Un algorithme de utilisé dans le sens commun c'est fait pour tourner sur un ordinateur "réel" donc c'est forcément un nombre fini d'étapes.

Par contre si tu regardes du côté des machines de Turing qui sont censées formaliser ce qu'est uin algo, il existe des algorithmes qui ne terminent jamais donc ça prend en compte ta définition

OP
BB

BriquetBLOC

il y a 9 mois

Je conçois qu'il ne finit pas, mais ce n'est pas pour autant qu'on ne peut pas prédire un résultat, enfin il me semble. De la même manière que certaines fonction admettent des limites bien qu'on ne puisse pas les « calculer »

DA

Dazee

il y a 9 mois


Je conçois qu'il ne finit pas, mais ce n'est pas pour autant qu'on ne peut pas prédire un résultat, enfin il me semble. De la même manière que certaines fonction admettent des limites bien qu'on ne puisse pas les « calculer »

Faut te renseigner sur internet mais ce que tu décris est vraiment le problème de l'arrêt.

OP
BB

BriquetBLOC

il y a 9 mois


Bah c'est une question de sémantique donc je trouve pas ça super intéressant

Un "algorithme" tel qu'utilisé dans le sens commun c'est fait pour tourner sur un ordinateur "réel" donc c'est forcément un nombre fini d'étapes.

Par contre si tu regardes du côté des machines de Turing qui sont censées formaliser ce qu'est uin algo, il existe des algorithmes qui ne terminent jamais donc ça prend en compte ta définition

Il y a une légère nuance. Ce n'est pas que l'algorithme ne se finit pas, dans le sens où il boucle, mais plutôt qu'il comporte une infinité d'étape différente les unes des autres.

TF

The_ff3_fan

il y a 9 mois


Je conçois qu'il ne finit pas, mais ce n'est pas pour autant qu'on ne peut pas prédire un résultat, enfin il me semble. De la même manière que certaines fonction admettent des limites bien qu'on ne puisse pas les « calculer »

Je pense que t'es en train de confondre plusieurs choses. Ca veut dire quoi un résultat pour un algo qui ne termine jamais au juste ? Ton analogie avec la limite est pas top, mais même si on garde cette analogie, il y a bien des fonctions qui n'ont pas de limite

OP
BB

BriquetBLOC

il y a 9 mois

Faut te renseigner sur internet mais ce que tu décris est vraiment le problème de l'arrêt.

Dac je vais regarder ça

TF

The_ff3_fan

il y a 9 mois

Il y a une légère nuance. Ce n'est pas que l'algorithme ne se finit pas, dans le sens où il boucle, mais plutôt qu'il comporte une infinité d'étape différente les unes des autres.

Tu gagnerais a formaliser ce que tu veux dire parce que tu utilises du langage courant alors que pour ce genre de subtilités, un langage mathématique serait beaucoup plus adapté

[2

[25032022]

il y a 9 mois

Un algorithme infini n'a aucun intérêt parce qu'il ne va jamais produire de sortie, or c'est la sortie qui nous interesse dans un algorithme.

Et en pratique, un algorithme qui ne se termine jamais est considéré comme un cas d'erreur sévère en informatique

OP
BB

BriquetBLOC

il y a 9 mois

Ouais pas faux, mais la je suis sur mon portable donc pas facile

OP
BB

BriquetBLOC

il y a 9 mois


Un algorithme infini n'a aucun intérêt parce qu'il ne va jamais produire de sortie, or c'est la sortie qui nous interesse dans un algorithme.

Et en pratique, un algorithme qui ne se termine jamais est considéré comme un cas d'erreur sévère en informatique

Pourquoi cet acharnement à considérer l'algorithme comme un outil informatique et non un objet mathématique ?

GO

Goniol

il y a 9 mois

A deux doigts de découvrir while () { }

[2

[25032022]

il y a 9 mois

Pourquoi cet acharnement à considérer l'algorithme comme un outil informatique et non un objet mathématique ?

Parce que l'étude des algorithmes fait partie du domaine de l'informatique et non des mathématiques (plus précisément du champ de l'informatique théorique pour l'aspect le plus théorique des algorithmes et de la programmation pour l'aspect le plus pratique).

TF

The_ff3_fan

il y a 9 mois

Pourquoi cet acharnement à considérer l'algorithme comme un outil informatique et non un objet mathématique ?

Parce que c'est défini rigoureusement dans le cadre de l'informatique

Si tu veux définir ce qu'est un algorithme mathématique bah va falloir lui donner une définition mathématique

OP
BB

BriquetBLOC

il y a 9 mois

Parce que c'est défini rigoureusement dans le cadre de l'informatique

Si tu veux définir ce qu'est un algorithme mathématique bah va falloir lui donner une définition mathématique

Toute définition d'objet est mathématique, le formalisme ne sert qu'à la formulation d'énoncé et proposition. Un objet n'est pas une proposition. Et le but des mathématiques est d'étudier les structures et les relations entre objet. Enfin si je me souviens bien de mes cours de logique.

D'ailleurs les démonstrations se redigent dans un langage courant, pas dans un langage formel