Coucou

J'ai un problème d'info que j'aimerais vous soumettre.

On considère un matrice M carré réelle de taille n.
On dit que M admet un maximum local en (i,j) si :

M[i,j] >= M[i+1,j]
M[i,j] >= M[i-1,j]
M[i,j] >= M[i,j+1]
M[i,j] >= M[i,j-1]

(Il faut donc que i et j soient différents de 1 et de n)

En supposant que M admet un maximum local, proposer un algorithme de complexité au plus linéaire permettant de trouver un maximum local de M.

Je bloque un peu, n'hésitez pas à proposer des idées (juste des idées, pas la réponse)

Merci beaucoup

En n, la taille de la matrice

Le n tel que M appartient à Mn(R) si tu préfères

Et juste je suis sûr à 99% de la définition du "maximum local" de l'énoncé

Il est écrit "si M[i,j] >= M[i+1,j] etc si cela existe"

Et quand il dit "si cela existe" je ne sais pas s'il parle du maximum local ou tout simplement du coefficient "M[i+1,j]"

Puis c'est un exo de ma fiche de TD d'info donc j'imagine qu'il est résoluble

Ce que bluepoint essaye de te dire (à sa manière), c'est que linéaire veut dire ici en O(n²), puisque la matrice a n² coefficients.
Tu as juste à traverser une fois ta matrice, en faisant un nombre constant de comparaisons à chaque fois, et ça sera linéaire.

SI c'est juste ça c'est un peu nul comme exo

C'est censé être un exo assez dur, donc je crois pas que la solution tienne en 2 lignes...

Linéaire ça veut bien dire linéaire sur le nombre de lignes, et pas le nombre de coefficients

J'ai trouvé ça, regarde à la fin.
http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf

En gros c'est un algo "diviser pour régner", et apparemment c'est en theta(n). Je te laisse vérifier.
Si tu veux chercher par toi même, commence peut être avec le cas 1D (maxima locaux d'un vecteur). Dans ce cas on peut atteindre une complexité en log n.

Ok, c'est bien faisable en O(n), marrant.
Par contre pour que ça marche, je pense qu'il faut que les bords et les coins de la matrice comptent aussi comme des maximums locaux.

Ça fait un peu penser à l'algorithme du gradient ( https://fr.wikipedia.org/rg/wiki/Algorithme_du_gradient ), où on veut minimiser une fonction et pour ça on part d'un point quelconque et on descend toujours vers la direction de pente maximale.

Là imaginons qu'on parte du coin et qu'on se déplace toujours vers le voisin de valeur maximale, ça marche pas parce qu'on peut se retrouver à devoir se balader un peu partout dans la matrice :

1   2   3   4   5
0   0   0   0   6
15  16  17  0   7
14  0   0   0   8
13  12  11  10  9

L'astuce c'est, avant d'entamer la montée, de réussir à se créer des « barrières » pour diviser la matrice en 4 zones dont on ne pourra pas sortir.

T'as demandé "juste des idées, pas la réponse", alors je m'arrête là pour l'instant

Merci beaucoup les gars

Je vais essayer vos deux méthodes

Je pense qu'en fait c'est la même.

En tout cas vous affirmez qu'on a le droit de tomber sur un coefficient du bord ?

Non, le "cela" se réfère au maximum local.

Le problème c'est que la valeur "infinie" en caml je la connais pas

Tu pourras toujours leur affecter le maximum de la matrice sinon mais du coup c'est plus du O(n)

Le problème c'est que la valeur "infinie" en caml je la connais pas

• Sur les int, tu as la valeur max_int ; sur les float, tu as la valeur infinity ; sur les Num tu as la valeur 1/0 qui se comporte comme l'infini
• S'il n'y a pas de valeur infinie, tu peux la coder toi même. Par exemple avec des string, tu définis

type string_inf = Val of string | Plus_infinity | Minus_infinity

• De toute façon, c'est un exo d'algo et pas un exo de caml. Tu écris du pseudo code, on s'en fiche de comment tu encodes ce genre de détails (l'énoncé ne précise même pas si c'est des int ou des float). T'as le droit d'utiliser la valeur infinie sans t'embêter.

Par contre je vois pas où vous voulez en venir avec vos moins l'infini, vous faites le truc a l'envers je pense.
Si les bords ont le droit d'être des maximums locaux, alors tout marche très bien (et c'est là définition la plus intuitive de ce que devrait être un maximum local). Par contre s'ils n'ont pas le droit, l'algo donné plus haut ne marche pas, et je vois pas trop comment on pourrait faire (on perd le lemme qui dit "il y a forcément un maximum local dans le quadrant").

À mon avis c'est juste le premier cas de toute façon c'est pas ça l'intérêt du problème. Ce qui m'étonne juste c'est que du coup il existe toujours un maximum local mais tu as dit "on suppose qu'il y a un maximum local"

Le plus simple c'est de parcourir toute la matrice et de s'arrêter quand on a trouvé un maximum local.

Vous me faites rire ceux qui pensent qu'on peut coder une matrice a n^2 coefficients en n entiers