Alan_T a écrit 242 commentaires

Houla, pas la peine de crier !

J'ai dit ça pour aller plus vite.

Pour info, la classe NP regroupe l'ensemble des problèmes dont une entrée donnée peut être validée ou invalidée en temps polynomial.

par exemple, pour SAT (satisfiabilité d'une formule logique), si on se donne un ensemble de valeur booléennes, on peut savoir si la réponse est 0 (false) ou 1 (true) en temps polynomial. Par contre, si on se retrouve avec 0 (false), il est difficile de savoir si la formule est satisfiable ou non.

Là, tu ne pourra pas dire que je n'ai pas été précis, mais va écrire ça dans des parenthèses !!! :-)

J'ai l'impression que les gens sont vachement sensibles ici ! 8-)

Je crois que tu confonds la complexité d'un algorithme ou d'un problème et son nombre d'opérations. Ce n'est pas bien grave car c'est souvent la même chose. Cependant, il existe ce que l'on appelle des 'classes de complexité' qui regroupent des problèmes de façon indépendante des algorithmes.

Par exemple, le test de primalité est P-complet(polynomial), le problème du voyageur de commerce est NP-complet (non polynomial), le problème de l'accessibilité dans un automate temporisé est P-space complet (polynomial en espace, on se fiche du temps), la résolution d'un système d'inéquations Diophantiennes est EXP-Time complet (exponentielle en temps), etc...

Tous ces problèmes peuvent avoir des algorithmes différents mais aucun algorithme ne peut avoir une complexité plus basse que la classe de complexité à laquelle appartient le problème. Maintenant, si tu considères le nombre d'opérations au pire cas, les algorithmes varient beaucoup, mais l'intéret est de considérer des problèmes et non des algorithmes. Évidemment, lorsque tu résouds un problème avec un algorithme calculer la complexité de ton algorithme te permet de voir si tu résoud de façon 'efficace' ou non ton problème (en gros, ton algorithme doit appartenir à la même classe de complexité que ton problème).

Par exemple, résoudre le problème du tri par bubble sort est une mauvaise idée car tu est au-dessus de la complexité du problème du tri (sans hypothèse sur les données).

Ok, je précise. Le O(n) permet de ne pas avoir à évaluer la constante qui est devant le 'n'. Le nombre d'étapes que l'algorithme devra faire au pire est en 'C.n' (avec 'C' une constante). Mais le 'C' change d'un algo à un autre alors on ne considère que les plus gros facteurs, on parle alors de O(n) (et non de 'C.n') pour la classe d'algorithmes ou pour un problème donné. Évidemment, lorsque 'n' tends vers l'infini on peut négliger le 'C'. Jusque là, tu as raison. Cependant, lorsque tu dis que la 'complexité' est 'n' pour un 'n' grand, là je dis non ! :-) Ta complexité est toujours 'n' (la complexité est la mesure générale de ton algorithme ou de ton problème). Par contre, le nombre de tes opérations pour un algorithme précis va tendre vers 'n'. Je crois que c'est seulement, là-dessus que repose notre divergence... Juste un point de détail quoi. :-)

Je crois que ce qui provoque notre désaccord provient d'une définition différente de la complexité. Devant le f(n) d'une complexité en O(f(n)), il y a une formule g(n) qui est de complexité moindre. Donc, le nombre d'opérations est f(n).g(n) dans la réalité (pour le pire cas toujours), mais on ne considère que les plus gros facteurs lorsqu'on parle de complexité. Mais par contre, c'est tout le temps la complexité pire cas qui est utilisée. La complexité en moyenne est extremement dure à calculer (pour ne pas dire impossible dans certains cas). Pour ce qui est de la complexité en temps et en espace, tu as raison.

Heu, aretez un peu de dire n'importe quoi ! :-) La complexité d'un algorithme est calculée quel que soit 'n'. Et c'est toujours la pire complexité que puisse atteindre cet algorithme (ou cette classe de problème). L'exemple du tri en O(n^2) est faux. Le problème du tri a une complexité en O(n.log(n)), il se trouve seulement que 'bubble sort' n'est pas un algorithme optimum pour résoudre un problème de tri. Je crois fermement que vous confondez votre cours de math sur les développements limités et votre cours d'info sur la théorie de la complexité. ;-)

Non, là je crois que tu mélanges les notions de limites en O(.) et la notion de complexité... :-/ Cela dit, c'est un peu normal car ces abrutis ont pris la même notation pour deux choses différentes. :-)

Moi, je connais et j'ai même implémenté des algos en O(e^n). Enfin pas completement exponentiels car ils sont P-space complet. Ce sont des algos de vérification de logiciels (model-checking). Mais, il est vrai qu'il s'agit là d'une limite. Cela dit, il est important de se rendre compte que lorsqu'on parle de O(.) on parle de complexité au pire et non pas en moyenne. Pour certains algorithmes les problèmes que l'on considère en pratique ont une complexité moindre que la complexité au pire. C'est le cas de l'algorithme du simplexe par exemple qui devrait être NP mais qui est P en pratique.

Argh, tu avais déjà répondu ! :-/ Désolé.

En fait, la complexité s'obtient en considérant le pire cas pour un problème. C'est à dire que tu part toujours du pire cas pour l'algorithme que tu considères. Exemple concret: Je prend 'buble sort'. C'est un tri qui considère les élements d'une liste deux à deux et qui les tri. Par exemple: 3, 4, 1, 8 On prend d'abord 3 et 4, 4 est plus grand que 3 donc on le met devant: 4, 3, 1, 8 On considère ensuite 3 et 1. Là, 3 est plus grand que 1, on laisse comme ça. Puis, 1 et 8. 4, 3, 8, 1 Et ainsi de suite jusqu'à ce que l'on ne puisse plus rien changer. 4*, 3*, 8, 1 4, 3*, 8*, 1 4, 8, 3*, 1* 4*, 8*, 3, 1 8, 4*, 3*, 1 8, 4, 3*, 1* Et enfin un dernier tour où rien ne change. Ici, le pire cas est lorsque la liste est inversée par rapport à l'ordre initial. On évalue donc la complexité de cet algorithme à: O(n^2) Car passer à travers la liste une fois et comparer les éléments deux à deux requière n (le nombre d'élements) et comme la liste est inversée, on doit le faire n fois. Donc n*n = n^2. Et voila. :-) Ah oui, je tiens à préciser que la meilleur complexité pour les algos de tri c'est en O(n*log(n)) (quicksort) et pas en O(n).

Pourquoi 'n' devrait-il etre "suffisamment grand" ? Il s'agit de la complexité dans le pire cas. C'est toujours vrai.

Et voila, je savais bien que j'allais dire plein de bétises !!! :-) Au fait, quelqu'un sait comment se comporte le noyau de Windows (XP ou 2k) au point de vue des threads ??? Je veux dire, pas de trolls, des faits.

Je vais essayer de t'expliquer en gros. Si jamais je fais des erreurs, les autres me reprendront ! ;-) Alors, un sytème d'exploitation multi-tâches est un logiciel qui gère plusieurs programmes en même temps. Que ce soit sur un ou plusieurs processeurs. De façon schématique on dit qu'un programme se présente potentiellement sous deux formes: 1) Son binaire. Qui est stocké sur le disque-dur ou en mémoire vive pendant son execution. 2) Un processus. Qui correspond à l'execution du binaire. Il est important de noter que chaque processus a son propre espace mémoire à lui. La plupart des systèmes d'exploitations partagent le processeur entre les différents processus, mais Linux, lui, utilise une granularité plus fine car il gère le partage du/des processeur(s) entre des threads. Un thread est un 'sous-processus' qui partage le même espace mémoire que les autres threads que gère le processus principal. Finalement, le scheduleur est le programme qui va donner la main à chacun des threads chacun leur tour suivant certaines données (comme leur priorité, leur age, etc). Le problème, c'est que ce scheduleur doit essayer d'éviter les deadlocks entre les threads (typiquement, un thread doit s'executer avant un autre ou alors ils tentent tous les deux d'acceder à une ressource critique). Et résoudre tout ces problèmes de dépendance est compliqué. L'algorithme proposé par Ingo, lui reste de complexité constante quelque soit le nombre de threads (O(1)). Et il semble marcher plutôt bien. Évidemment, lorsqu'on utilise des threads comme brique de base, il faut pouvoir commuter rapidement d'un processus à un autre (on appelle cela plutôt un 'environnement' car on charge en mémoire l'endroit où en était le processus que l'on redémarre). Il se trouve que la nouvelle implémentation des processus s'adapte particulièrement bien à la commutation de processus (et donc de threads). Voila, j'ai surement dit plein de bétise, mais au moins c'est un début d'explication.

Ok, je comprends mieux. J'ai trouvés quelques liens à ce propos:

NetBSD: http://www.netbsd.org/Ports/(...)

FreeBSD: http://www.freebsd.org/platforms/index.html(...)

Linux: http://www.tldp.org/links/devel.html(...)

Mais, cela sert à quoi d'avoir tout ces ports ? C'est pour des systèmes embarqués ? (je m'instruit, je critique pas!!!).

Moi, je trouve que cela ressemble vraiment à Dselect...

Je ne voulais pas provoquer de guerre sainte, c'est juste que leur page qui décrit les buts de NetBSD m'a paru bizarre:

http://www.netbsd.org/Goals/(...)

Je dois surement avoir mal compris, mais j'ai l'impression qu'ils essayent juste de s'intercaler entre FreeBSD et Linux... Je comprends les buts de Linux, FreeBSD, et même OpenBSD, mais là, je vois pas....

Quel'qu'un peut-il m'éclairer ? Ou alors, il s'agit juste d'un autre YAOS (Yet Another Operating System) ?

Donnez-moi des arguments plutôt que de me mettre des -1 !

Betement, je croyais que NetBSD était conçus pour faire des routeurs stables et efficaces... Mais, là, ils parlent l'USB 2.0, du support de système de fichiers Windows 2000, ...

NetBSD n'essayerait-il pas de faire plus qu'il ne devrait ????

-1 -> Parceque Troll en vue !

Vous avez vu le "Sysadmin Disaster of the Month" ?

http://user-mode-linux.sourceforge.net/sdotm.html(...)

C'est une manière originale de donner des exos en cours de système d'exploitation !!!

Pourquoi ne pas envisager le UML comme un excellent outils d'enseignement ? ;)

Ok, mais, au fait, il apporte quoi ce choix de 'design' ? Je ne suis pas programmeur Windows, donc forcémment, j'ai du mal à comprendre... Pour moi, cela doit, euuuuh, faciliter la communication entre éléments graphiques.

Ah bah, non je dis une connerie parceque sous Unix on a les évènements X-Windows qui sont sécurisés et qui font pareil...

Non, là, vraiment je vois pas! :)

-1, parceque je suis vraiment mesquin. :)

Tu avouera tout de même que Windows, pour un système d'exploitation qui est 'tout graphique', ça la fout mal de faire ce genre recommandation.

Alors que les pingouins, eux, ils peuvent le faire et ils ne sont même pas en environnement graphique tout le temps...

C"est un peu comme si on choisissait un algorithme pourri pour le système de fichier et que l'on demandais à l'utilisateur de faire marcher un programme de défragmentation de temps à autre...

Ooops. :-)

Allez --> -1

TOUT à fait d'accord, mais je ne parlais pas de taille. Je parlais de complexité. Ce n'est pas forcément la même chose.

La programmation système sous Unix requiert, à mon avis, pluls de connaissance que sous Windows.

Mais je peux me tromper, car je n'ai jamais programmé sous Windows. J'ai juste une idée théorique des algorithmes qu'ils utilisent dans les parties 'critiques' du systèmes (gestion des processus, système de fichiers, etc).

Pour la lourdeur, je voulais parler de la gestion des droits. La philosophie d'Unix est de créer des systèmes multi-utilisateurs. Tout est basé autour de cette assomption. La gestion des droits s'insère jusque dans les processus.

Windows, lui a initialement été conçus comme un système mono-utilisateur. Et je ne serais pas surpris qu'une part de cette 'culture' subsiste encore dans les choix de certains programmeurs Windows...

Je suis tout à fait d'accord, mais je voudrais juste ajouter un truc.

Bien sûr que le fait de d'avoir un process graphique root sûr dépend de X (et pas du kernel), mais comme on fait ici une comparaison avec Windows, je pense que l'on peut considérer que la config de base dont on parle inclus X.

En gros, cela ne change rien. X a aussi été conçus dans un esprit où, le fait d'avoir des connaissances en système et programmation empêche de gagner des privilèges non autorisés...

De plus, le fait de séparer X du kernel est, à mon humble avis, une sécurité supplémentaire.

En tout cas, merci pour les éclaircissements, j'avoue que je n'avais pas bien compris la portée du bug sous Windows, vu que pour moi tous les programmes windows étaient graphiques (je sais c'est stupide quand j'y reprense ! ;-)).

Ok, je vois mieux ce que tu veux dire.

Je ne connaissais pas les "recommandations" de Microsoft.

Cependant, je trouve tout de même, cette 'feature' quelque peu effarante ! Il est tout à fait possible sous Linux d'avoir un processus graphique root et de ne pas avoir de problème !

D'autre part, la 'culture' Microsoft semble plutôt favoriser les applications graphiques (souvent considérées comme plus 'simples' à utiliser). Donc, je vois une contradiction claire entre le fait qu'il faille à la fois des applications graphiques ET qu'ils fournissent un environnement graphique qui a un mauvais design... :-/

Mais, je suppose qu'il ne s'agit là que de mes vues personnelles sur le sujet. ;-)

Je cite:

Applications within Windows are entirely controlled through the use of messages. When a key is pressed, a message is sent to the current active window which states that a key was pressed. When Windows decides that an application needs to redraw its client area, it send a message to the application. In fact, when any event takes place that an application needs to know about, it is sent a message. These messages are placed into a queue, and are processed in order by the application.

This is a very reliable mechanism for controlling applications. However, on Win32 the mechanism for controlling these messages is flawed. Any application on a given desktop can send a message to any window on the same desktop, regardless of whether or not that window is owned by the sending application, and regardless of whether the target application wants to receive those messages. There is no mechanism for authenticating the source of a message; a message sent from a malicious application is indistinguishable from a message sent by the Windows kernel. It is this lack of authentication that we will be exploiting, taking into consideration that these messages can be used to manipulate windows and the processes that own them.

Il suffit donc d'avoir UNE application graphique qui tourne en root (sous Windows la plupart des applis ont une interface graphique) et qui soit épisodiquement dans cette file pour pouvoir passer root.

La méthode que décrit l'article s'appuie sur un anti-virus, mais on peut imaginer des tas d'autres applis.

Tu as tout à fait raison de dire que c'est une politique choisie par Microsoft. Mais cela nous donne le droit de discuter ces choix.

Pour ma part, je ne le trouve très bon.

Par contre, là où je ne suis plus d'accord, c'est lorsque tu dis qu'un système qui saurais se protéger contre les programmeurs devrait être lourd et ingérable.

C'est une légende ! La plupart des Unices sont programmé dans cet esprit.

Il est vrai qu'ils sont un peu plus complexes, et un peu plus lourds que Windows (et cela te donne en partie raison), mais le prix à payer n'est pas aussi excessif que tu sembles le dire (du moins si j'ai bien compris ton argumentation).

http://security.tombom.co.uk/shatter.html(...)

C'est tout. Lis, on en reparle après.