Discussion :

[Nemerle]

ouhaip, une question "hard": soit une matrice M carrée n*n, disons booléenne.

En s'autorisant à échanger les lignes & colonnes, ou en rénumérotant l'ordre sur {1...n}, on veut obtenir la plus grande sous-matrice de M ne contenant que des zéros; au sens où

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
  |A 0|
M=|0 B|,

le zéro en haut à droite étant notre recherche. Le O(??) étant le caractère de référence

pour tester, le "n" de référence est 300 000 000.

[gorgonite]

quel est le but de la question ?
+ proposition de defis fonctionnels ?
+ question algo (mauvais forum dans ce cas ) ?

[SpiceGuid]

La réponse pourrait être longue à écrire, je propose ceci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
print_string "(0, ";
while true do
  print_string "0, ";
done;
print_string "0 ) ";;

[DrTopos]

pour tester, le "n" de référence est 300 000 000.

Ta matrice contient donc 90 000 000 000 000 000 entrées. Même en supposant que chaque entrée soit codée sur 1 bit, elle occupe 11 250 000 000 000 000 bytes, c'est à dire plus de 11 millions de gigabytes.

Si tu me payes la machine, je veux bien essayer.

[Jedai]

Ta matrice contient donc 90 000 000 000 000 000 entrées. Même en supposant que chaque entrée soit codée sur 1 bit, elle occupe 11 250 000 000 000 000 bytes, c'est à dire plus de 11 millions de gigabytes.

Si tu me payes la machine, je veux bien essayer.

On va supposer qu'il s'agit d'une matrice creuse, sinon il y a effectivement un problème... Le fait qu'elle soit creuse change pas mal les données par contre, parce qu'il est plus aisé de savoir quelles parties sont nulles, il s'agit juste de prendre le rectangle maximum dans une fusion de surface ou quelque chose comme ça.

--
Jedaï

[Nemerle]

Ta matrice contient donc 90 000 000 000 000 000 entrées. Même en supposant que chaque entrée soit codée sur 1 bit, elle occupe 11 250 000 000 000 000 bytes, c'est à dire plus de 11 millions de gigabytes.

Si tu me payes la machine, je veux bien essayer.

Pour info, il y a bien un 0 de trop dans le n: n=30 000 000, soit effectivement plus de 100 tera de données.

[Garulfo]

ouhaip, une question "hard": soit une matrice M carrée n*n, disons booléenne.

En s'autorisant à échanger les lignes & colonnes, ou en rénumérotant l'ordre sur {1...n}, on veut obtenir la plus grande sous-matrice de M ne contenant que des zéros; au sens où

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
  |A 0|
M=|0 B|,

le zéro en haut à droite étant notre recherche. Le O(??) étant le caractère de référence

pour tester, le "n" de référence est 300 000 000.

Quelle est ta question exactement ?! Tu cherches un algorithme qui permet d'obtenir la plus grande sous-matrice de M ne contenant que des zéros ?

Dans ce cas comme le dit Gorgonite tu n'es pas sur le bon forum.

[Nemerle]

SI: je sais faire en langage non fonctionnel, je m'intèresse juste à comment ça se développerait en Haskell par exemple (avec 110 Tera)

[Garulfo]

SI: je sais faire en langage non fonctionnel, je m'intèresse juste à comment ça se développerait en Haskell par exemple (avec 110 Tera)

Donc tu as un algorithme et tu veux l'implémenter ?
Sauf que tu n'as pas un algorithme qui serait implémentable, selon toi, dans un langage fonctionnel ? Je te rassure ça l'est toujours avec quelques modifications. Même si ce n'est pas forcément évident.

Mais en conclusion, c'est un problème d'algo et pas un problème de langage.

[SpiceGuid]

Et c'est quoi exactement une matrice plus grande ?
Par exemple si on compare une matrice 3*4 et une matrice 2*6, laquelle est la plus grande et pourquoi ?