Démontrer que si f est paire alors f' est impaire

Soit une fonction f définie sur un ensemble A centré à 0. Supposons que cette fonction soit paire et admet une dérivée en tout point où f est définie. Nous allons démontrer que f' (dérivée de f) est impaire.

nous avons pour tous x appartenant à A, f(x)=f(-x), car f est paire. Or f(-x) est identique à la  composée de f et de -x, f(-x) = f o (-x). Dérivons les deux membres de cette égalité, en utilisant la formule de la dérivée d'une fonction composée (f'(u(x))*u'(x)) pour le second membre.
Nous obtenons: f'(x) = f'(-x) * (-1),
alors, f'(x)=-f'(-x) pour tous x appartenant à A, par conséquent nous concluons que f' est une fonction impaire.

Quelques éléments de logique et raisonnement mathématiques

Nous allons expliquer et discuter les opérateurs implique et équivaut utilisés largement en sciences mathématiques. Ces opérateurs trouvent leurs fondements en théorie de la logique et du raisonnement mathématiques.

Commençons par définir une proposition par une phrase ayant un sens et qui peut être affectée une valeur vraie ou fausse. Nous allons traiter des propositions et leurs relations, quand elles sont définies, de l’une par rapport aux autres.

Essayons de dégager la définition de la relation implique entre deux propositions par la discussion de l’exemple suivant.

Soit p : un entier naturel n vérifie n >= 0,

Et q : 2 >= 0.

Nous avons p => q (p implique q). Mais pas q => p (q n’implique pas p).

Cela signifie que la valeur vraie de p nous mène à affirmer que q est vraie sans d’autres évidences supplémentaires. En effet, le fait que p soit vrai suffit à dire que q soit vraie. Cependant dans ce cas, la connaissance de q ne suffit pas pour déduire p (c’est la proposition q => p). En effet il y a une infinité de propositions similaires à q dont leur union mène à affirmer p. Par exemple, l’ensemble des propositions 0>=0, 1>=0, 2>=0, 3>=0,….. mène à dire d’une façon sure que la proposition p : un entier naturel n vérifie n >= 0 est vraie.

Donc la connaissance de la véracité de p=>q nous mènent pas à déduire la valeur de vérité de q=>p. Ces deux propositions sont indépendantes et ont des significations différentes.

p => q veut dire	q => p veut dire
Si p est vraie, alors q est vraie	Si q est vraie, alors p est vraie
Pour que p soit vraie, il faut que q soit vraie	Pour que q soit vraie, il faut que p soit vraie
Pour que q soit vraie, il suffit que p soit vraie	Pour que p soit vraie, il suffit que q soit vraie
q est vraie si p est vraie	p est vraie si q est vraie
p est vraie seulement si q est vraie	q est vraie seulement si p est vraie

L’opérateur <=> relie deux propositions p et q de la façon suivante : p<=>q, et signifie que ces deux propositions sont équivalentes, en d’autres termes, nous ne pouvons pas distinguer p et q, car p et q signifie exactement la même chose.

p<=>q signifie que p=>q et q=>p, c’est-à-dire p=>q et q=>p découle, ou est une conséquence de p<=>q. De même, p=>q et q=>p signifie que p<=>q, donc on peut déduire que p<=>q <=>(p=>q et q=>p).

Représentation graphique

p=>q peut être comparé à p ≥ q, c’est-à-dire q est un sous-ensemble de p. De cette façon, d’autres propositions différentes de q peuvent découler de p. Par exemple, p=>q1 et p=>q2, q1 et q2 seraient des sous-ensembles de p (q1 et q2 peuvent ne pas exister notamment si p<=>q). S’il n’existe pas d’autres propositions qi distincts de q qui vérifient p=>qi, on peut déduire que p et q sont égaux en tant qu’ensembles, et p<=>q, en tant que propositions. En effet, nous n’avons pas pu trouver de propositions qui soient une conséquence ( ou contenue dans l’un) de l’un mais pas de l’autre.

implique et équivaut

Model checking (ou vérification des systèmes réactifs)

Le model checking  est un domaine de l’informatique ayant pour but de vérifier le bon fonctionnement des systèmes concurrents ou réactifs. Ce domaine est en relation étroite avec le  domaine de la logique mathématique, plus particulièrement avec la logique temporelle linéaire propositionnelle, ou encore la logique temporelle arborescente. 

Les logiciels du model checking sont issus d’une recherche intensive dans le domaine d’exploration d’états de système à transition finis. Ce domaine a connu de nombreux apports dans la tâche de réduction du volume de l’exploration, comme la méthode du « Partial Order Reduction » par exemple.

Différents logiciels comme Spin [1] et Uppaal [2], nous permettent de décrire et de représenter notre système concurrent par un modèle simplifié, et de le vérifier par rapport à des propriétés de sûreté, de vivacité ou d’équité. Les propriétés de sûreté nous garantissent qu’un mauvais état de fonctionnement n’est jamais atteint, tandis que les propriétés de vivacité nous garantissent qu’un état convenable survient finalement, les propriétés d’équité nous garantissent que toutes les séquences d’exécution laissent les autres séquences accessibles aussi.

Les logiciels du model checking permettent par exemple de vérifier les algorithmes classiques des systèmes répartis (Spin en particulier) comme les algorithmes d’élection d’un chef, la terminaison d’un calcul et l’exclusion mutuelle. Aussi on peut vérifier les protocoles de communication comme le protocole du bit alterné, ajoutons aussi qu’on peut vérifier les propriétés de sécurité des protocoles de cryptographie. Les systèmes réactifs en temps réel peuvent être vérifiés à l’aide du logiciel Uppaal qui permet la modélisation des systèmes en des automates temporisés, et assure la vérification des propriétés sur les systèmes en utilisant des conditions portant sur le temps entre les événements.

En résumé, le model checking nous propose un  moyen simple et efficace pour la vérification des systèmes réactifs ou concurrents en utilisant des abstractions qui facilitent notre vue du système à vérifier.

[1] Spin outil de vérification. http://spinroot.com

[2] Uppaal outil de vérification. http://uppaal.org

Génie Logiciel

Le génie logiciel est une branche du génie qui a pour but de concevoir, d’appliquer et de mettre à jour les processus, méthodes et techniques du développement et de la mise en œuvre  des logiciels informatiques dans divers champs d’applications allant des mobiles, PCs, serveurs, jusqu’aux grandes machines parallèles. Ces logiciels sont conçus de manière à éviter ou à minimiser les fautes ou erreurs de fonctionnement ou de déploiement, et ont pour but le bien-être, la sécurité et la satisfaction des clients ou des organisations.

Le génie logiciel propose des méthodes complètes couvrant tout le cycle de vie d’un logiciel ou d’un système informatique, de la spécification des exigences, jusqu’au déploiement et maintenance du logiciel. Ces méthodes font preuve de robustesse, de fiabilité et de répétabilité par rapport à leur fonctionnement attendu. En plus du fonctionnement attendu, des attributs de qualité  comme la maintenabilité, évolutivité et réutilisabilité font aussi partie du cahier des charges des logiciels.

Le génie logiciel regroupe plusieurs sous-domaines comme l’architecture logicielle, l’approche orientée objet et l’intégration entre systèmes, et a des pistes communes avec d’autres domaines du génie et de la gestion, comme la spécification des cahiers des charges et la gestion des projets, respectivement.

P VERSUS NP By Farid El Hajj 2012

DESCRIPTION OF P VERSUS NP PROBLEM

Most famous open problem in theoretical computer science. Its solution can deep our understanding of algorithm complexity or maybe it will give us a mathematical tool for solving hard problems in an efficient way. Great work has been spent on providing a solution but no one has ever been able to solve it.

HISTORY
Described in its current form by Cook in 1971 in a paper where he proved the first NP-Complete problem. In 1973 Karp gave another 21 NP-Complete problems. Since then tremendous effort has been deployed to find an algorithm that will reduce any NP problem to P, or on the contrary to prove that these two classes of problems are different.

TECHNICAL IMPACT 

The P versus NP problem has a large impact which makes it a fundamental open problem. Imagine one could derive a polynomial time algorithm for solving an NP-Complete problem, then any NP problem with exponential time could be reduced and solved in a polynomial time in an efficient way. No such algorithm has been found, nor the impossibility to find such a problem has been proved.

LARGER IMPACT

  
If someone could derive such an algorithm the result will have an impact on several domains: theorem proving could be done in an efficient and tractable way. Optimization and resource management will be an easy matter. The impact will be tremendous on many and unthought-of domains such as evolutional biology and economics and much more.
 
If P equals NP then current cryptographic schemes will be broken in a reasonable time and power. The one way functions assumed to be hard could be broken like a piece of toy. But many experts think that P is not equal to NP.

TECHNICAL DESCRIPTION 

The problem belongs to complexity theory. P is the class of problems solved by a deterministic Turing machine in a polynomial time. NP is the class of problems which are solved by a non- deterministic Turing machine in a polynomial time, which means it can be solved by brute force algorithm in an exponential time. Cook in 1971 wrote a paper where he gave the description of the P versus NP problem and he proved that the Boolean satisfiability problem belongs to the NP-Complete class, also he proved that any NP problem could be reduced to an NP- Complete one using a Turing machine in a polynomial time.