lundi 13 mars 2023

P=NP (chap2)

Follwing Chap 1

To give a better idea of what could perhaps be done with a methode derived from Ec software.

We want  to resolve  the traveler purchaser problem  with a collection of towns T={A,B,C,D......}.

(Starting from A and going through each town in T/ {A})

For each permutations P of (B,C,D...) we need to find the one with the lowest distance the salesman has to run through. We could find several one but we need only one. 


One solution is run through a tree that build the permutation and at each leaf of calculate the distance for this permutation and record if it is lower that the previous one we found.

Another solution  is to upload the best distance  found in a sub tree and to select the best one at each level. 

In this case we can see that they are duplicated subtrees. Let's compare to branches:

(A,B,C,D, Tail1......)  and (A,D,C,B,Tail2) 

Tail1 and Tail2  subtrees have the same collection of towns and should yield the same  result. 

We don't need to explore the duplication we can simply cut it and use for ADCB the result previously found for ABCD.

For a 3 towns circular permutation we can spare half the nodes at each level for n level is approximately dividing the full process by 2^n. Approximately because it is not possible for all level (deepness).

They are perhaps several ways to find the duplication at each level (deepness in the tree):

  • we can use an array (created at each dive in the next level toward the leaf) and look up (B,C,D) when the previous nodes are (D,C,B). Each town being designated by a number. 
  • We could perhaps avoid to create a multi dim  array because duplicated subtree come  at a regular positions  at the same depth level  when using a specific permutation systeme (I show it in langage C program  and its output at the end of this post ). We could build in advance an array providing for each node at a same level which node previously got the result. Or better (to spare memory)  have a function for each level which provide for each node (its chronologic number) which previous node has the result. It could perhaps even be done with some quantum computer solution. I mean using a quantum computer as a coprocessor. The biggest problem is to find a way to build  automatically this function  for each level. It might be possible. Or we can use a build-in advance array. I will try this in a langage C program with thread. It will  give an idea on the number of nodes we can spare.    
But we might exploit  better the full potential  of this method.
because it should also work for a 2 town permutation :
for (A,B,C,tail1)  and (A,C,B,tail2)  tail1 and tail2 yield also the same result.
in fact we can cut each time we encounter  in a tree 
(A,,,X1,X2,,,,Xm, tail) and if  we already recorded this circular permutation of (Xm...,X2,X1) at this level.

It is not sure we can build a program that can do this with reasonable amount of memory.

But some brains might theoretically calculate the amount of node exploration we can spare.

Does it make the salesman problem polynomial or even logarithmic?

Finally. 
I'd like to excuse myself in advance in case of big error made by me  in this post.
I needed to fill the pressure of writing it down.
I discovered new things doing it. 

A first attempt to compute the number of node with and without cut:

Number of nodes without cut should be N=n!+(n-1)!+(n-2)!............+3!+2!

If we are able to detect sub tree duplication (in a "polynomial" way and with reasonable amount of memory) then with detection of permutation of 2 nodes in a branch from (head0,A,B,tail0) to (head0,B,A,tail0) we could lower the total amount by 2 at each level.

  
The new number of nodes would N2= N/(2^n)

The expressions N2 or N3.2 or Nm...3.2 are just variable name  with a suffix that  try to explain that  we could also use circular permutations  of 3,4,m subsequent nodes (m <n).

With a full optimisation it is difficult (for me) to count how many nodes with spare on the entire tree.

And finally difficult to know if we can reach the polynomial or logarithmic  target this way.

I tried to see what I can spare mixing 3 and 2 town permutation  optimisation with a branch-head of  
4  towns:  I got only  6 subtrees I need to really explore instead of 24.
If we do it at (n-m) levels we ca reduce the total number of nodes to N3.2 = N/(6^n)

If we mix  m ,m-1, .....3,2 town permutations optimisation we would get something like:
Nm.(m-1)...3.2= N/(X^m) but I don't know X.
The expression for the dénominator must be much more complicated.
The hope is we can choose m so  that X can be near enough of n without inducing a to high CPU/memory cost.
But it could still be useful for pure theoretical solution.

I will try an experimentation with Pthread... a good opportunity to work again with C language and learn Pthread. 
  
This a a first "dirty" version of the salesman programm without cut but ready for its implementation.
Just to show how the permutations are generated. 
The full directory can be found on Google Drive . It is interesting is to study the list of all routes generated by the program and mark the permutations  having the same collection of towns in a  a subtree. Town are numbers in the program.

We can see on this output of the programm that, if a list of more than 5 towns was used, duplication of permutation of two towns (green) and three town (red) would allow us to explore only 6 subtrees. But it is also very interesting to see the regularity at which green and red hyphens appear. It means that we could perhaps avoid to use a three dim lookup but only one dim. This one dim being the sequence at which nodes apper at the same depth level.

 A new version of salesman.c has been made  that seems to work much better in  Chap 3 . 

lundi 6 mars 2023

Brother HL2135w

J'ai pourtant été fidèle à la marque en prenant soin d'acheter des toners de la marque et même de racheter une deuxième imprimante couleur de de la même marque car j'étais content.

J'essaye donc d'imprimer un PDF en recto verso pour économiser du papier. Et je n'y arrive plus avec W11. Je vérifie la mise à jour des pilotes: tout est à jour.

Je dois donc investire en temps de formation pour trouver une solution ou décider de ne plus utiliser une imprimante en parfait état de marche mécanique pour pouvoir économiser du papier.

Obsolescence programée?

dimanche 5 mars 2023

P=NP Demonstration. Chap 1

It might be possible  that the langage C module named hash.c  used in the chess engine  Ec could help to resolve the question P=NP with a yes.

I don't have all the knowledge and capacity to expose the reason here. But I will try to see if this module and the way I explore the  chess-game tree in Ec could be used  in a similar manner to resolve a NP-complete problem: the Traveling purchaser problem.

What I think is: if I show  that the resolution can be obtained in polynomial time or even in logarithmic time then the demonstration of P=NP would be partially resolved.

But I am old and not well educated. So I might be wrong.

To help to understand what is done in EC with the module hash.c:

hash.c allow to save and retrieve the result of a tree below a  node named C (deep-level=n) that the engine reached after node A  (deee-level=n-2) and B (deep-level=n-1). I would name this situation (A,B,C) So the engine might have before encountered and saved situation (C,B,A).  C at deep level n-2, B at n-1 and A at n. 

From the point a view of chess and the way the result is transferred up from bottom tree,  (A,B,C) is generally equivalent to (C,B,A) (not equivalent if a chess piece is taken). That assumption might be also be challenged. I Am not completely shure. I took great risks. But It might be easier to verify it with the Traveling purchaser problem.

So now I need to build the program with  a kind of  Ec method to resolve the Traveling purchaser problem in -I hope - a logarithmic time.

Chap 2


vendredi 3 mars 2023

Problemes d'affichage avec Google Map , Chrome et Windows 11 et un Lenovo Tiny M700

Cela fait une ou deux semaine que cela arrive parfois avec W11.

Lorsque j'ouvre un fenêtre  avec chrome pour  visualiser  une carte avec Map j'ai des problèmes d'affichage:  la fenêtre s'affiche alternativement à plusieurs endroits en flashant. J'utilise un Lenovo Tiny M700.

J'avais fait une recherche sur Google avec "Caroline Du Nord" puis j'ai cliqué sur la petite carte à droite qui est un lien sur Google Map.

Cela ressemble plus à un problème de driver. Mais pourquoi donc le problèmes d'affichage n'est pas reproduit avec d'autres applications?

C'est peut-être tout simplement une panne intermittente  du M700.  

En fait cela semble être une panne de l'adaptateur Display-Port vers HDMI. 

En fin de compte et après avoir acheter un nouvel adaptateur display port vers HDMI, je conclue à un arrêt de la prise en charge par W11 d'un écran DGM en HDMI:

C'est écran marchait sur la prise HDMI il y a encore quelque jours. J'ai testé la partie hardware:  câble et  sortie HDMI.  En testant l'écran ne fonctionnant plus (marque DGM) en HDMI sur un autre PC, puis en utilisant un écran qui marche en HDMI ( marque SAMSUNG) sur la machine Windows 11. Ma conclusion là plus probable  est que le problème est purement logiciel et que le driver a été supprimé. Si cela n'est pas un erreur de la part de Microsoft alors je reprouve ce choix qui encourage la surconsommation. Je dois utiliser VGA pour pouvoir encore utiliser mon écran DGM alors qu'il marchait en HDMI avant.

mercredi 1 mars 2023

Prolog le langage

 J'avais dans ma jeunesse expérimenté turbo prolog. J'ai réessayé récemment d'utiliser sans succès une version récente de turbo prolog qui existe toujours.

Puis j'ai essayé Swi-prolog. 

Après quelques expérimentations plus fructueuses qu'avec turbo prolog je me pose certaines questions.

Comment se fait-il qu'un langage aussi fascinant que prolog soit aussi difficile à utiliser.

On a un terminal qui  permet d'interroger la base de donnée.

Mais!

  • Si on ajoute des faits, ils ne sont pas mémorisés de manière permanente. On est obligé de modifier le fichier source du programme.
  • Si on veut ajouter une règle il faut aussi modifier le fichier source du programme.
  • On a pas le moyen standard de stocker dans une base de donnée comme Sqlite.
Pour moi l'idéal serait de d'avoir un fichier source de base et un autre qui s'aliment automatiquement avec les modifications que l'on fait de manière interactive. 

Mais c'est peut-être infaisable. 

Je n'y ai pas beaucoup réfléchi.

Je verrais bien un module python qui permettrait de faire des requêtes de type prolog sur une base de donnée de type SQL.

Ca existe?

De toute façon j'en ai pour un bon moment avant de comprendre comment prolog fonctionne.

jeudi 16 février 2023

W11, OneDrive, Exfat et Fedora et W10 aussi

Pas trouvé le moyen de synchroniser un répertoire de mon pc sous W11 avec Onedrive.

Je transfère mes données d'un NAS vers un disque externe formaté avec Exfat (pas forcément une bonne idée) Pui je monte ce disque sur W11 et le partage pour pouvoir le monter sur une machine équipée du system Fedora. 

Je passe aussi l'antivirus de Microsoft sur ce disque externe. Il y trouve d'ailleurs un virus  ( .so pour php ) que j'ai téléchargé lorsque j'avais essayé de développer une nouvelle appli php pour  Eggdropcentral. J'avais d'ailleurs eu un problème pendant un chat avec le repreneur du site en utilisant une appli java. 

Conclusion: je me retrouve avec de très nombreux répertoires de ce disques externes qui sont vidés de leur contenu. Et des commentaires externes sur ce qui c'est passé: Une personne du coin a peut-être pris le contrôle de ma machine Fedora et décidé de me punir pour avoir fait confiance à Microsoft.

Probablement un cocktail explosif!

Et puis je découvre que j'ai surconsomé des donnée sur mon compte reglo mobile de 120go! Qu'elle est la raison ? Je regarde les comteur et je me demande pourquoi le system W11 a eu besoin a lui tout seul de 44Go. Je ne vois pas en quoi Microsoft à besoin de collecter 40go de données en moins d'un mois pour analyser mon comprtement et améliorer mon expérience.

Cela fait plusieurs jours que je fais des recherches sur internet pour essayer d'installer la synchronisation entre des dossiers sur mon PC et one drive. Echecs sur échecs. J'en suis arrivé à me demander si je suis devenu un débile mental, ou si Microsoft ne veux pas que je l'utilise (je paye un abonnement chaque mois). A moins que la facilité d'abonnement soit conditionné par un abonnement à office 360. Je vais peut-être me contenter de Google Drive que je n'aime pas beaucoup aussi. Je rappelle que je n'ai pas réussit à ouvrir un fichier qui se trouve dans onedrive avec une application dans mon pc w11. Le coffre fort Onedrive n'est accessble que par le navigateur internet pas l'application OneDrive??!!!

Je cherche donc un moyen d'améliorer l'utilisation du volume de données disponble avec reglo mobile: 120 Go par mois. Et je découvre que très peux de données de mise à jour du system ont été utilisées. Il y-a-t-il un problème comptage? J'aimerai bien savoir ce qui a causé le transfert par internet de 40go de données par le system w11.

J'utilise à nouveau mon portable W10 et alors que je suis sous tension 220V, je vois mon écran se mettre en veille très rapidement alors que les paramètre de mise en veille sont de 30 minutes. J'en conclus qu'il y a un problème: soit je n'ai pas compris comment fonctionne la mise en veille soit les paramètres choisis ne sont pas appliqués. Comme cette machine est mise à jour régulièrement et que l'antivirus de Microsoft est aussi lancé régulièrement j'estime qu'il est probable qu'il y ait un bug (peut-être lié au fait que je n'utilise plus d'écran externe). Il est également possible qu'un virus installé récemment n'a pas été détecté.

Encore d'autres problèmes non corrigés par la toute dernière mise à jour (22 fev 2023). Curseur souris qui saute d'un demi écran vers la gauche. Coincement de la touche majuscule en position majuscule. C'est peut-être l'ordinateur ou la souris presque neuve Amazon basic. Je suis obligé de redémarrer.

De plus j'ai souvent des doutes lorsque je dois entrer un mot de passe. Par exemple on me demande de mmettre à jour mes paramètres Outlook. Je dois entrer plusieurs mot de passes. A un moment on me demande :"Entre votre code sécurité pour accéder à Outlook.". Je finis par comprendre que je dois entrer le code PIN. Le même que j'ai utilisé pour le login w10.

Redmi 8A temps de réponse

J'ai 2go de Ram et un octo-core (probablement un 4cores / 8 threads)

Je réalise dans l'ordre:

  • Saisie du mot de passe (login)
  • Revenir sur le bureau à partir de l'application SMS: 5 s
  • Démarrer  l'application Téléphone: 3 s
  • Démarrer l'application Google Chrome: 4s
  • Mise en veille et login  par saisie mot de passe
  • Démarrer l'appareil photo: 3s

Souvent j'ai besoin d'un accès rapide à l'appareil photo pour photographier des gens qui me harcèlent et j'abandonne car le temps d'attente est trop long. Même si je le démarre à l'avance.

Je me demande donc: à quoi servent les 2 go de mémoire et les 8 cores?

LA dernière fois que j'ai démarré l'appareil photo, j'ai attendu plus de 10s