Wiki du LAMA (UMR 5127) - Contributions [fr]

MSHS501 et MSHS601 : Enquête et sondage

2011-05-30T10:07:16Z

Quentinscott :

== Introduction ==

Qu'est-ce qu'une enquête dans le cadre de ce cours ? Dans quels cas faire une enquête. Il faut faire attention à la surcharge du mot enquête en français (ici on va parler des "surveys" et des "polls" de la langue anglaise).

Définition: pour ce cours, on définit enquête et sondage par les caractéristiques suivantes :
* démarche scientifique et rigoureuse,
* recherche de réponses à une ou plusieurs questions déterminées,
* interrogation d'un échantillon choisi parmi une population bien définie.

Attention, l'enquête n'est pas toujours la bonne manière de répondre à une question.

Il existe deux types d'enquêtes :
* l'enquête qualitative (en générale par entretien),
* l'enquête quantitative ou statistique (principal objet de ce cours) dont les sondages font partie.

Plan général du cours en trois parties :
# conception d'une enquête.
# mise en oeuvre et contribution des outils informatiques modernes.
# considérations statistiques avancées.

Voici les feuilles de TD :
* [http://www.lama.univ-savoie.fr/~raffalli/pdfs/MSHS501-TD1.pdf TD1]
* [http://www.lama.univ-savoie.fr/~raffalli/pdfs/MSHS501-TD2.pdf TD2]
* [http://www.lama.univ-savoie.fr/~raffalli/pdfs/MSHS501-TD3.pdf TD3]
* [http://www.lama.univ-savoie.fr/~raffalli/pdfs/MSHS501-TD4.pdf TD4]

Voici le sujet d'examen de janvier 2009 et son corrigé: [http://www.lama.univ-savoie.fr/~raffalli/pdfs/exam090109.pdf sujet] et [http://www.lama.univ-savoie.fr/~raffalli/pdfs/exam090109-corr.pdf corrigé]

Le projet de cette année (2008-2009) a pour but de conduire une [[enquête sur les comportements à risque des étudiants de l'université]] .

== Modalités d'une enquête ==

# Choisir d'enquêter ou non.
# Construire l'enquête :
#* Préciser les objectifs, c'est-à-dire les questions auxquelles l'enquête devra répondre, ou les hypothèses qu'elle devra confirmer ou invalider. Il faut distinguer l'objectif général (qui donne son unité à l'enquête et les objectifs particuliers. Attention aux cahiers des charges "tout fait".
#* Définir le "plan d'observation" : préciser la population et l'échantillon (taille et structure) et les contraintes matérielles.
#* Modalité de l'enquête.
#* Décider du caractère qualitatif ou quantitatif.
#* Préparation et test du questionnaire ou des entretiens.
#* Entretien préparatoire.
# Recueil de l'information. Après cette étape on ne peut plus revenir en arrière.
# Dépouillement et analyse des données.
# Rédaction du rapport final.

=== Contexte et problématique d'une enquête ===

Première question : l'enquête est-elle la bonne méthode ? Confrontation avec les autres méthodes : étude documentaire, observation directe (engagée ou non), expérimentation.

3 TYPES D'ENQUETES

-Enquête transversale: question sur l'ensemble de la population

-Comparaison de groupe: dans la question initiale il y a déjà la définition de groupe

-Etude longitudinale: temps, comment la population évolue

=== Plan de réalisation d'une enquête ===

==== Objectifs et cahier des charges ====

Le cahier des charges de départ va d'une unique question vague à un questionnaire tout fait (il faut alors revenir en arrière).

Il faut donc déterminer la question générale de départ et la transformer en questions de recherches spécifiques sous forme d'hypothèses ou de quantités (exemple de la croyance au paranormal).

* Les hypothèses et les quantités à mesurer doivent être définies de manière objective et non ambiguë. Elles doivent être respectivement vérifiables et mesurables (exemple du bonheur).
* L'hypothèse doit être plausible et remise en question.
* Attention : vérifier une hypothèse n'est pas demander aux gens ce qu'ils en pensent.

Pour formuler les hypothèses, il faut rechercher des indicateurs et les multiplier. Exemple: "Il y a une relation négative entre les croyances religieuses et les croyances au paranormal".

Pour cela, on fait une pré-enquête avec une recherche documentaire, la réalisation d'entretien (avec des informateurs priviligiés ou auprès de la population sujet de l'enquête). On repère ainsi les bons indicateurs et le vocabulaire de la population. On s'arrête lorsque l'on tourne en rond.

==== Population parente -- échantillon -- modalités du sondage ====

Population parente : le sujet de l'enquête (individu, famille, entreprise). Il faut bien définir les critères d'inclusion.

Plan d'observation : - Enquête transversale - Comparaison de groupes : (Quasi expérimentation : on prend une population, on la divise aléatoirement en 2 echantillons et on en soumet un à un cas et l'autre non. Vraie expérimentation : on selectionne 2 échantilons en fonstion du fait qu'ils aient subis ou non l'evenement cas témoin : on compare les groupes en fonction de plusieurs critères),- Enquête longitudinale :(étude de cohorte : choix d'un echantillon à un intervalle régulier dans une même population,étude à série chronologique : on interroge 2 fois la même population avant et apres l'évenement, interview répété ou panel : on fixe l'echantillon, étude de tendance : similaire à l'étude de cohorte mais la population est plus large).

Sondage : il faut choisir un échantillon (faire un sondage). Problème de la taille et du choix.
C'est l'un des problèmes majeurs, on y consacrera le chapitre 3.

==== Le questionnaire ====

Il s'agit de préparer ''l'instrument d'observation''. Etape délicate, là aussi le chapitre 4 y est consacré.

=== Recueil des données ===

C'est une phase sans retour en arrière possible. C'est aussi cette phase qui concentre la majeur partie du coût de l'enquête (sauf en cas de collecte par internet et dans une moindre mesure par courrier).

=== Traitement et analyse des résultats ===

C'est là et dans le choix de l'échantillon qu'il faut vraiment faire preuve de rigueur scientifique. cf chapitre 6.

=== Le rapport ===

Comme tout rapport, il commence par une page de titres et une introduction comportant les motivations, le plan et un résumé des résultats (ou pas). Attention, la plupart de vos lecteur s'arrêteront là ...

La suite du rapport peut (doit ?) suivre le plan de réalisation de l'enquête et donc présenter les objectifs et la méthode de l'enquête. Vous devez '''prouver''' votre rigueur scientifique. Ensuite, vous donnez les résultats bruts (à plat) et enfin les analyses statistiques qui justifient vos conclusions.

La conclusion (qui peut-être incluse dans l'introduction) résume vos résultats, vos ''échecs'' et vos éventuelles recommandation si l'étude avait pour motivation une aide à la décision.

Attention : ce qui compte dans un rapport '''scientifique''', c'est sa cohérence et sa rigueur. Il faut éviter les répétitions et la dispersion. Il faut rechercher la ''densité'' et la ''cohésion''.

== Les modalités d'un sondage ==

=== Population et méthode de collecte ===

==== La population ====

Que les critères d'inclusions aient l'air de s'imposer d'eux mêmes ou non, il faut absolument prendre soin de les définir par écrit. Il faut être face à un individu, savoir s'il fait partie ou non de la population étudiée. Pas de place ici pour le libre arbitre des enquêteurs.

==== Type de collecte ====

Le type de collecte (enquête avec un sondeur, questionnaire auto administré, etc ...), influe sur le choix de l'échantillon et aussi sur l'analyse des données.

- questionnaire administré ( face à face, au tel, internet )

- questionnaire auto administré ( papier, internet )

- entretien

=== Les problèmes d'échantillonnages ===

==== La population et l'échantillonnage ====

L'échantillon doit couvrir toute la population (être représentatif, sinon on a une généralisation abusive). C'est là le principal problème. (attention à : echantillon original biaisé, auto selection, echantillonnage par quotas...)

==== La taille de l'échantillon ====

Il faut simuler des sondages et s'assurer que la taille de l'échantillon sera suffisante dans la plupart des cas.
Dans certains cas, on peut calculer une taille d'échantillon, dans d'autres cas, seule la simulation permet de conclure.
Attention, la méthode d'échantillonage permet (et sert souvent) à réduire la taille de l'échantillon sans dégrader la qualité des résultats.

=== Les différents types classiques d'échantillonnages ===

==== Les échantillons aléatoires ====

1. Tirages aléatoires simples : il s'applique pour l'enquete transversale ou encore longitudinale, il consiste à prendre, au hasard "n" individus dans le liste d'une population

2. Échantillon systématique : on prend la liste d'une population et on prend un individu tous les "n". On peut choisir le premier au hasard.

3. Échantillon avec probabilité inégale : ( ex : si on veut connaitre le pourcentage de femmes dans une entraprise, on prend alors des entreprises au hasard mais pas avec une probabilité uniforme, avec par exemple une probabilité proportionelle à la taille ).

4. Échantillon stratifié : on découpe la population en fonction des critères que l'on a déja identifié,on obtient alors des strates et on prend ensuite un échantillon pour chaque strates

5. Échantillon par grappes : on découpe la population en grappe, on choisit aléatoirement un echantillon pour chaque grappe et enfin on interroge toutes les personnes de chaque grappe

6. Échantillon à plusieurs degrés : on découpe la population en groupe, en sous groupe, en "sous-sous" groupe ... d degrés.

7. Échantillon à plusieurs phases :on prend un echantillon qui contient des individus externe à la population que l'on veut observer et on fait notre questionnaire en 2 parties: si l'individu fait parti de la population que l'on veut observer alors on continue le questionnaire.

==== Les échantillons empiriques ====

#Méthode des quotas : il faut disposer de stat de la population avant l'enquete, on choisit des critères et on essaie d'avoir le bon pourcentage pour chaque critères.
#Échantillon par choix raisonné : on selectionne un echantillon que l'on considère représantatif
#Échantillon "aléatoire reconstitué" : on fait se déplacer l'enqueteur au hasard dans la ville et il interroge des personnes au hasard.
#Échantillon de commodité ou volontaire : on prend les personnes que l'on a sous la main.

==== Correction du biais de non réponses ====

== Les questionnaires ==

=== Généralités ===

Un instrument de mesure qui cherche à être précis et fiable et qui prend en compte l'enquêté.

Chaque question doit avoir un (et un seul) objectif précis et bien déterminé.
Les questions doivent être construite avec le plus grand soin pour éviter toutes erreurs...

Il faut aussi s'assurer (autant que possible) que l'enquêté acceptera d'aller jusqu'au bout du questionnaire
et répondra avec sincérité.

=== Questions ouvertes ou fermées ===

Les deux types de questions ne sont pas équivalentes. Il n'y a pas trop de problème pour l'âge, mais c'est plus
difficile pour des concepts comme l'inflation (13% contre 21%).

* La question ouverte donne une grande liberté (impossible pour des sujets très généraux genre
"que pensez-vous de la paix dans le monde ?"). Réponses riches et diversifiées, mais parfois dur à grouper en classe et donc à analyser.
Repose trop sur la mémoire de l'enquêté (risque d'oublis d'une possibilité pour certains et pas pour d'autres).
* La question fermée (à choix multiples ou à choix unique) est plus facile à analyser, mais peut induire des biais (risque de désirabilité sociale, réponses peu réfléchies) mais il faut faire attention à ne pas être exhaustif.

En général, on élabore des questions fermées à partir de questions ouvertes posées lors d'une pré-enquête.

Précaution : exhaustivité et exclusion mutuelle. L'item "autre" doit être évité sauf pour des cas exceptionnels.

=== Type de questions ===

==== Questions de comportements (Que font-ils ?) ====

Problème des comportements génants : rendre la question acceptable, utiliser des procédures spécifiques (urne, isoloir, question indirecte ).

Attention aux problèmes de mémoire : proposer des listes, des questions sur un passé récent.

==== Questions d'opinion (Que pensent-ils ?) ====

On utilise des échelles unidimensionnelles (à deux ou plusieurs ''degrés''), des mises en situation ou des classements.

Position intermédiaire : veut-on connaître les indécis ou forcer à prendre partie.

Sans opinion : attention, la formulation de la question peut beaucoup faire varier la proportion de sans opinion. L'absence de
cette possibilité peut forcer l'enquêté à répondre au hasard.

Attention on veut bien demander ce que pense l'interogé et pas ce que pense l'interoogé sur l'opinion des autres personnes.

==== Questions d'intentions (Que vont-ils faire ?) ====

L'enquêté est peu engagé par sa réponse d'où une surestimation globale
de l'action (surestimation des intentions d'achats par exemple).

==== Questions de connaissances (Que savent-ils ?) ====

L'enquêté risque de ne pas oser la non-réponse. Il faut utiliser des formulations plus acceptables : "Sauriez-vous par hasard...".
Introduire des questions faciles et éventuellement des fausses réponses (auteur ou livre inexistant)

==== Renseignements signalétiques (Qui sont-ils ?) ====

* Recoupement possible avec des données existantes (par exemple en utilisant les catégories socio-professionnelles de l'INSEE)
* Souvent des variables importantes dans les hypothèses de l'enquête.

=== Questions indirectes ===

* Mise en situation
* Association de mots (liste ouverte ou fermée)
* Phrases à compléter
* Bulle de BD à compléter

=== Qualités des questions ===

* Neutralité : tendance à l'acquiescement, ...,question chargée (pas toujours un défaut) (= question biaisée : "etes vous en faveur de l'assassinat d'un bébé dans le ventre de sa mère?)
* Être compris : niveau, intérêt (filtrage), vocabulaire (bon sens, sens multiple, confusion, ambiguité, non familier, vague, interpretation contradictoire), question complexe
* Économie globale du questionnaire : ordre, transition, effet de halo, taille, présentation, frontiere nette des reponses (je ne peux pas associer une modalité à une autre, pas de chevauchement)
* Experience personnelle, diverse des individus.
* Effet de l'ordre des questions : effet de rapport, effet de fatigue , effet de deliberation (une modalité peut être avantagée si elle est enoncée en premier ou si elle est enoncée en dernier)
* Les possibilités de réponses : eviter de proposer plus de 5 modalités (ex: choix entre 0 et 10 ), choix d'integrer une reponse mediane ou non.

=== Analyse du questionnaire ===
- ACM
- scinder la population de la bonne manière
- analyse d'indépendance: il faut estimer les 2 variables avec le même effort,la même rigueur

'''2 types de classification:'''
- classification discrète/continue
- classification qualitative/quantitative

'''3 types de questions et VA:'''
- énumérative
- ordinale
- numérique

'''numérique:''' classification de type quantitative.La somme et /ou la différence ont un sens.La moyenne aussi.VA sont dans (R,+).
'''ordinale:''' La somme et la différence n'ont pas de sens mais l'ordre a un sens.
Exemple: 1- Très satisfait
2- Satisfait
3- ...
6- Pas du tout satisfait
La moyenne n'a ici pas de sens.Mais la médiane garde du sens(écart interquartile).
'''énumérative:''' C'est tout le reste!
Exemples: couleur,goût,partis politiques,opinions politiques...
On peut juste se poser des questions sur la distribution elle-même.

-essayer d'avoir le plus d'informations possibles pour chaque sous-adjectif.
numérique > ordinale > énumérative

== Techniques informatiques modernes de collecte ==

== Traitement et analyse statistique des données ==

== Programme de TD et TP du second semestre ==

[http://www.lama.univ-savoie.fr/~raffalli/pdfs/enquete-0427.odt Questionnaire étudiants au format open office]
[http://www.lama.univ-savoie.fr/~raffalli/pdfs/enquete-0427.doc Questionnaire étudiants au format word] au 27 avril

Pour info les vieux fichiers :

[http://www.lama.univ-savoie.fr/~raffalli/pdfs/enquete-0421.odt Questionnaire étudiants au format open office]
[http://www.lama.univ-savoie.fr/~raffalli/pdfs/enquete-0421.doc Questionnaire étudiants au format word] au 21 avril

[http://www.lama.univ-savoie.fr/~raffalli/pdfs/enquete-0420.odt Questionnaire étudiants au format open office]
[http://www.lama.univ-savoie.fr/~raffalli/pdfs/enquete-0420.doc Questionnaire étudiants au format word] au 20 avril

Semaine 5 : préparation du questionnaire pour le projet

Semaine 7 en salle machine : étude des estimateurs de la moyenne, de la variance et de la médiane.

Semaine 9 : découverte et application d'un test

Semaine 11 : feuille de TD sur le cours

TP 1 (2H, semaine 6 ou après) : mise en place du questionnaire en php+mysql et des tests.

TP 2 (2H) : faire l'enquête sur le campus.

TP 3 (2H) : on verra ...

[http://cvresumewritingservices.org/ resume service]

MATH206 : Probabilités et Statistiques

2011-05-30T10:07:14Z

Quentinscott :

Feuilles de TD :
[http://www.lama.univ-savoie.fr/~raffalli/pdfs/TD1-MATH206.pdf 1]
[http://www.lama.univ-savoie.fr/~raffalli/pdfs/TD2-MATH206.pdf 2]
[http://www.lama.univ-savoie.fr/~raffalli/pdfs/TD3-MATH206.pdf 3]

==Introduction==

Statistique descriptive: décrire avec le moins possible de nombres (ou avec un graphique) des données constituées
d'un (très) grand nombre de valeur.

Probabilité: prédire la description précédente sans faire de mesure (à l'aide d'hypothèses).

Statistique mathématique ou inférentielle: comparer la prédiction à la mesure et confirmer ou infirmer des hypothèses scientifiques.

Exemple du dé juste.

==Vocabulaire de probabilité==

* ''' Population ''' : Groupe d'objets étudiés. Elle peut-être :
**"réelle" : les Français, les étudiants de ce cours...
** "virtuelle" : l'ensemble des lancés de dés possibles...
* '''Sous-population, échantillon '''
* '''Expérience ''' : Choisir un élément dans une population.
* '''Evénement''' : L'événement se produit lorsque l'élément appartient à la sous-population.
* '''Partition ''' : Découpage d'un ensemble en plusieurs sous-ensembles disjoints.
* '''Cardinal ''' : Nombre d'éléments d'un ensemble.
* '''Fréquence ''' d'un sous ensemble A ⊂ Ω : <math> F(A)=\frac{\displaystyle {card(A)}}{\displaystyle{card}(\Omega)} </math>
* '''Variable aléatoire ''' et ''' Série statistique ''' : Application d'une population Ω dans un ensemble ''G'' quelconque.

==Estimateur ponctuel==

* '''Moyenne ''' et '''espérance''' (rappel et "sens")
Formule de la moyenne (resp. espérance) d'une série statistique (resp. variable aléatore) X sur un population <math>\Omega</math>:

<math>\displaystyle M(X) = E(X) = \frac{\sum_{i \in \Omega} X_i}{Card(\Omega)}</math>

Remarque: pour avoir le droit d'écrire <math>E(X)</math> il faut que <math>X</math> soit une variable aléatoire numérique, c-à-d une application de <math>\Omega</math> dans <math>\mathbb{R}</math> (remarque hors programme : un espace vectoriel suffirait).

La moyenne est le nombre x qui remplace le mieux <math>X_i</math> pour l'ensemble de la population quand on regarde l' '''erreur quadratique'''
donnée par la formule suivante (preuve facile en dérivant f):
<math>\displaystyle f(x) = \sum_{i \in \Omega} (X_i - x)^2</math>

On définit deux types d'erreurs :
# ''' l'erreur absolue ''' : <math> \sum_{i \in \Omega} \mid X_i -x \mid </math>
# ''' l'erreur quadratique ''' : <math> \sum_{i \in \Omega} (X_i -x)^2 </math>
On choisit la seconde car la première est plus compliquée.

L'erreur quadratique est aussi liée à la variance V(X) car:

<math>\displaystyle V(X) = \frac{\sum_{i \in \Omega} (X_i - E(X))^2}{Card(\Omega)} = \frac{f(E(x))}{Card(\Omega)}</math>

* Propriété de la moyenne (linéarité) : <math>E(X + Y) = E(X) + E(Y)</math> et <math>E(aX) = aE(X)</math>.
* Propriété de la variance : <math>V(X) = E(X^2) - E(X)^2</math> et <math>V(aX) = a^2 V(X)</math>

Notation:
*<math>i \mapsto ...</math> désigne la fonction qui a <math>i</math> associe le contenu des trois petits points. Cela évite de donner des noms à toutes les fonctions (et donc toutes les variables alétoires) ou d'utiliser trop de notations ambigües.

Démonstration de <math>V(X) = E(X^2) - E(X)^2</math>
<math>\begin{align}V(X) &= \frac{\sum_{i \in \Omega} (X_i - E(X))^2}{Card(\Omega)} \\
&= E(i \mapsto (X_i - E(X))^2) \\
&= E(i \mapsto X_i^2 - 2 X_i E(X) + E(X)^2) \\
&= E(i \mapsto X_i^2) - 2 E(X) E(i \mapsto X_i) + E(i \mapsto E(X)^2) \\
&= E(X^2) - 2 E(X)^2 + E(X)^2 \\
&= E(X^2) - E(X)^2
\end{align}</math>

* Définition d'estimateur et de biais :

Un '''estimateur''' est une "formule" permettant de donner une bonne approximation d'un paramètre statistique à partir de la variable aléatoire restreinte à un échantillon.

Un estimateur estime un paramètre P(X) si il converge vers P(X) lorsque la taille de l'échantillon tend vers la taille de la population
(cela n'a de sens que sur les populations infinies ...)

Un estimateur pour P(X) est '''sans biais''', si son espérance est égale à P(X) lorsqu'on le considère comme une variable aléatoire sur la population des échantillons de taille n fabriquées à partir de <math>\Omega</math> (notée <math>\Omega^{(n)}</math> si il s'agit d'échantillon
sans répétition (ou remise) et sans ordre et <math>\Omega^{n}</math> pour les échantillons avec répétitions (avec remise) et avec ordre).

Notation:
*<math>\hat{P}(X)</math> désigne la valeur du paramètre statistique <math>P</math> sur un échantillon (ici implicite).

 Estimateur de la moyenne : la moyenne sur l'échantillon est un estimateur sans biais de la moyenne sur la population entière.

Démonstration :
Soit <math>(A_1;...;A_n)</math> l'échantillon (avec ou sans répétition, la preuve est identique) et
<math>\hat{E}(X)=\frac{\sum_{i = 1}^n X_{A_i}}{n} </math> la moyenne sur l'échantillon.
On a:
<math>\begin{align}E(\hat{E}(X)) &= E\left(A \mapsto \frac{\sum_{i = 1}^n X_{A_i}}{n}\right) \\
&= \frac{1}{n} \sum_{i = 1}^n E(A \mapsto X_{A_i}) \\
&= \frac{1}{n} n E(X) = E(X)\end{align} </math>
Explication:
- La première égalité est juste le remplacement de <math>\hat{E}(X)</math> par sa ''vraie'' définition,
c'est à dire la variable aléatoire qui à l'échantillon <math>A</math> associe la moyenne de <math>X</math>
sur cet échantillon.
- La seconde égalité est juste la linéarité de l'espérance. On doit numéroter les éléments de l'échantillon
pour pouvoir faire cette étape sinon la preuve n'est pas tout à fait correcte.
- La troisième égalité vient du fait que pour chaque <math>i</math> on a <math>E(A \mapsto X_{A_i}) = E(X)</math>.
C'est intuitivement vrai, car prendre un échantillon de taille <math>n</math> pour ne retenir que sa i-ème valeur,
revient à juste prendre un individu. Si vous n'êtes pas convaincu, faite le calcul !

*Estimateur de la variance (avec et sans remise) :

Si on note <math>\hat{V}(X)</math> la variance d'un échantillon de taille n dans une population de taille N, on obtient un estimateur sans biais
de la variance avec les formules suivantes:

<math>\displaystyle \frac{n}{n-1}\hat{V}(X)</math> dans le cas de tirage avec remise de l'échantillon

<math>\displaystyle \frac{N-1}{N} \frac{n}{n-1}\hat{V}(X)</math> dans le cas de tirage sans remise (qui vaut bien <math>\sigma^2</math> lorque n = N).
Démonstration :
'' Calcul préalable : '' Soit X une variable aléatoire sur Ω, On définit <math>Y = (i,j) \mapsto X_i X_j</math> la variable aléatoire sur
<math>\Omega \times \Omega</math> (avec remise) ou sur <math>\Omega \times \Omega \setminus \{(i,i) \mid i \in \Omega\}</math> (sans remise).
* avec remise :
<math>\begin{align} E(Y) &= \frac{1}{N^2} \left( \sum_{i,j \in \Omega} X_iX_j \right) \\
&= \frac{1}{N^2} \left( \sum_{i \in \Omega} X_i \sum_{j \in \Omega} X_j \right) \\
&=E(X)^2
\end{align} </math>
* sans remise :
<math>\begin{align} E(Y)
&=\frac{\sum_{i,j \in \Omega ; i \neq j }X_iX_j}{N^2 - N} \\
&=\frac{\sum_{i,j \in \Omega}X_iX_j - \sum_{i \in \Omega}X_i^2}{N(N-1)} \\
&=\frac{ \left( \sum_{i \in \Omega} X_i \right) ^2 - \sum_{i \in \Omega }X_i^2}{N(N-1)} \\
&= E(X)^2 \frac{N}{N-1} - \frac{E(X^2)}{N-1}
\end{align}</math>
'' Fin de la démonstration :'' Soit Ω une population de taille N, soit X une variable aléatoire sur Ω, on s'intéresse aux échantillons de taille n.
On a V(X) variance de la population et <math>\hat{V}(X)</math> la variance d'un échantillon <math>A = \{a_1,\dots,a_n\}</math> de taille
<math>n</math>. Là encore, la notation <math>\hat{V}(X)</math> ne fait pas appraître le fait que cette quantité dépend de <math>A</math>. On a
<math>\begin{align}\hat{V}(X) &= \hat{E}(X^2) - \hat{E}(X)^2 \\
&= \frac{1}{n} \sum_{i = 1}^n X_{a_i}^2 - \frac{1}{n^2} \sum_{1 \leq i, j \leq n} X_{a_i}X_{a_j} \\
&= \frac{n-1}{n^2} \sum_{i = 1}^n X_{a_i}^2 - \frac{1}{n^2} \sum_{1 \leq i \neq j \leq n} X_{a_i}X_{a_j}
\end{align}</math>
D'où
<math>\begin{align} E(A \mapsto \hat{V}(X))
&=\frac{n-1}{n^2} \sum_{i = 1}^n E(A \mapsto X_{a_i}^2) - \frac{1}{n^2} \sum_{1 \leq i \neq j \leq n} E(A \mapsto X_{a_i}X_{a_j}) \\
&=\frac{n-1}{n} E(X^2) - \frac{n-1}{n} E(Y)
\end{align}</math>
Pour finir, on utilise le résultat du calcul préalable.
* avec remise : <math> E(A \mapsto \hat{V}(X))= \frac{n-1}{n} (E(X^2) - E(X)^2)= \frac{n-1}{n} V(X) </math>
* sans remise : <math> E(A \mapsto \hat{V}(X))= \frac{n-1}{n} (E(X^2) - E(X)^2 \frac{N}{N-1} + \frac{E(X^2)}{N-1})= \frac{n-1}{n} \frac{N}{N-1}V(X) </math>

On prend donc en général, pour estimateur sans biais de V(X) sur un échantillon <math>A \subset \Omega</math> la valeur appelée variance empirique de Y :
<math>\displaystyle \sigma'^2 = \frac{1}{Card(A)-1}\sum_{i \in A} (y_i - \overline y)^2</math>

Remarque: pour faire le calcul pour l'estimateur de variance, le point principal est de calculer l'espérance de <math>X_1X_2</math> où <math>X_1</math> et <math>X_2</math> sont deux variables aléatoires obtenues à partir d'une variable aléatoire X en choisissant deux individus au hasard. On a besoin de faire ce calcul à la fois pour un choix de deux individus avec remise et sans remise.

==Un peu de dénombrement==

* Cardinal du '''produit cartésien ''': le produit des cardinaux.

* Tirage '''sans ordre et sans remise ''' de p parmi n, c-à-d nombre de parties à p éléments d'un ensemble à n éléments :

<center><math>\displaystyle C^p_n</math></center>
Démonstration :
On veut choisir p+1 éléments parmi n+1, sans ordre, sans remise. Soit <math> E_n^p </math> l'ensemble des parties à p éléments de {1;...;n}.
<math> E_{n+1}^{p+1}= F_{n+1}^{p+1} \cup G_{n+1}^{p+1}</math> de sorte que <math> F_{n+1}^{p+1} </math> est l'ensemble des p+1 éléments qui contiennent n+1,
et <math> G_{n+1}^{p+1} </math> est l'ensemble des p+1 éléments qui ne contiennent pas n+1. On a <math> F_{n+1}^{p+1} \cap G_{n+1}^{p+1} = \emptyset</math>.
D'autre part <math> G_{n+1}^{p+1}=E_{n}^{p+1} </math>. Soit f: <math> E_n^p \rightarrow F_{n+1}^{p+1}</math>, <math> card(E_{n+1}^{p+1})=card(E_n^p) + card(E_n^{p+1})</math>
''Remarque : '' Deux ensembles en bijection ont le même cardinal.

* Tirage '''avec ordre et sans remise ''' de p parmi n, c-à-d nombre de p-uplets d'un ensemble à n éléments (nombre d'injections de {1;...;p} dans un ensemble à n éléments) :

<center> <math>\displaystyle A^p_n</math></center>
Démonstration:
Soit <math> A_n^p </math> le nombre d'injection, <math> A_n^1=n </math> et <math> A_{n+1}^{p+1}=(n+1) \times A_n^p</math>.
D'où <math> A_n^p= n A_{n-1}^{p-1}=n(n-1)(n-2) ... (n-p+1) </math>

* Tirage '''avec ordre et avec remise ''' de p parmi n, c-à-d nombre de tirage avec remise et avec ordre de p-élemnts parmis n (nombre d'applications de {1;...;p} dans un ensemble à n éléments) :

<center><math>n^p</math></center>
Démonstration :
<math> card(E \times E \times E \times ... \times E)=(cardE)^p=n^p </math>

* Tirage '''sans ordre et avec remise ''' de p parmi n :

<center><math>\displaystyle C^{p}_{n+p-1} = C^{n-1}_{n+p-1}</math></center>
Démonstration : 
On place n-1 jetons dans n+p-1 cases, il reste p cases libres. Il y a <math> C_{n+p-1}^{n-1}=C_{n-1+p}^{p}</math> choix.
Soit f: <math> E \rightarrow \begin{Bmatrix}0;\dots;p\end{Bmatrix} </math> soit f associe à x le nombre de fois où x a été choisi.
On a <math> \sum_{x \in E} f(x)=p</math>, ce qui revient à n-1 jetons et p cases vides.

<center> Choix de p éléments parmi n 
<table border="1">
<tr> <th> Ordre\Remise </th> <th> Sans (0≤p≤n) </th> <th> Avec (0≤p)</th>
</tr>
<tr> <th> Sans </th> <td> <math>\displaystyle C^p_n</math> </td> <td> <math>\displaystyle C^p_{n+p-1}</math></td> </tr>
<tr> <th> Avec </th> <td> <math>\displaystyle A^p_n</math> </td> <td> <math> n^p </math> </td> </tr>
</table>
</center>

'' Rappel des formules usuelles pour les coefficients binomiaux :''

* avec factorielle : <math>\displaystyle C^p_n = \frac{A^p_n}{p!} = \frac{n!}{(n-p)!p!} = \frac{n(n-1)...(n-p+1)}{p!}</math>
* triangle de Pascal : <math>\displaystyle C^0_n = C^n_n = 1, C^{n-p}_n = C^p_n</math> et <math>\displaystyle C^{p+1}_{n+1} = C^p_n + C^{p+1}_n (0 \leq p \leq n - 1)</math>
* Formule du binôme de Newton et applications comme <math>\displaystyle \sum_{p=0}^n C^p_n = 2^n</math>.

Démonstration : 
Soit <math> f(x)=(x+1)^n </math>, <math> f(x)= \sum_{p=0}^n C_n^p x^p</math>. En particulier, f(1)=2n.

==Probabilité et lois usuelles==

* ''' Probabilité ''' (ou loi de probabilité) sur un ensemble <math>\Omega</math>: un nombre associé P(E) aux sous-ensembles <math>E \subset \Omega</math> d'un ensemble (pas toujours tous les sous-ensembles) tel que :
** <math>P(\emptyset) = 0</math>
** <math>P(\Omega) = 1</math>
** <math>P(E \cup F) = P(E) + P(F)</math> si <math>E \cap F = \emptyset</math>
:: '' Conséquences : ''
:::μ (A C)=1- μ (A)
::: <math>[(A \Rightarrow B) \Leftrightarrow (A \subset B)] \Rightarrow \mu (B) \geq \mu (A)</math>
::: <math> \mu (A \cup B)= \mu (A) + \mu (B) - \mu (A \cap B)</math> si A et B non disjoints.
* ''' Évènements = Sous-ensemble ''' . Evénements certains, impossibles, incompatibles. Implication entre évènement et inégalité sur les probas.
* Cas des ensembles finis et probabilité uniforme :
: Pour '' définir une loi de probabilité sur un ensemble fini '' Ω, il suffit de donner la probabilité des singletons.
Démonstration : 
A={x1;...;xn} avec n=card(A). A={x1} ∪ {x2} ∪ ... ∪ {xn} où les singletons sont disjoints.
D'où μ (A)= μ (x1) + ... + μ (xn). Donner une loi sur Ω fini, c'est donner μ (x) pour tout x de Ω.

: La '' loi de probabilité uniforme '' sur Ω fini est l'unique probabilité sur Ω telle que μ (x)=p pour tout x dans Ω avec <math>p=\frac{1}{card(\Omega)} </math>.
Démonstration : 
Ω = {x1;...;xN} avec N=card(Ω). D'où μ (Ω)= μ (x1) + ... + μ (xN)=Np. Or μ (Ω)=1. Donc p=1/N.

: Si A ⊂ Ω et μ est une loi de probabilité uniforme sur Ω alors <math>\mu (A)=\frac{ card(A) }{card( \Omega )} </math>.
Démonstration : 
N=card(Ω) et n=card(A) où A={x1;...; xn</sub}.
On a <math> \mu (A)= \sum_{i=1}^n \mu (x_i)=\sum_{i=1}^n \frac{1}{N}=\frac{n}{N}</math>.

* ''' Loi image ''' (image réciproque d'un ensemble Ω dans Ω') :

Soit X une variable aléatoire sur Ω, à valeurs dans Ω' (X fonction de Ω dans Ω'). On a une loi μ sur Ω. On construit une loi sur Ω', image de μ par X et notée μX. On a pour A inclus dans Ω μ (A)=μ (X-1(A)).

Si Ω est un ensemble ordonné et μ une loi sur Ω, on définit F la ''' fonction de répartition ''' telle que <math> x \in \Omega , F(x)= \mu ( \{ a \in \Omega \mid a \leq x \} )</math>. F est croissante et tend vers 1.
Démonstration :
Si x ≤ y ∈ Ω et {a/ a ≤ x} ⊂ {a/a ≤ y } alors μ ({a/a ≤ x}) ≤ μ ({a/a ≤ y}); d'où F(x) ≤ F(y).

* ''' Variable aléatoire discrète '''
* Lois discrètes usuelles
** '''Loi indicatrice''' ou '''loi de Bernouilli ''' (I(p)) :

Soit X une variable aléatoire sur Ω à valeurs dans {0;1}. X(x)=1 si et seulement si x ∈ E ⊂ Ω (E=X-1(1)).

Cette loi est déterminée par μ X (1)= μ (E)=p (d'où μ X (0)= μ (EC)=1-p).

::: Espérance : E(X)=p
::: Variance : V(X)=p(1-p)
::: Ecart-type : <math>\sigma (X)=\sqrt{p(1-p)} </math>

** '''Loi de Pascal''' (Pa(p)) :

Ω est muni d'une loi uniforme, E ∈ Ω est un événement. On réalise plusieurs expériences '' indépendantes'' jusqu'à obtenir un succès. Soit X le nombre total d'expériences (succès inclus). X est à valeurs dans lN*.

Cette loi est déterminée par μ (E)=p ∈ ]0;1[; μ (X=k)=(1-p) k-1p ∈ ]0;1[.

::: Espérance : E(X)=1/p
::: Variance : V(X)=(1-p)/(p2)
::: Ecart-type : <math>\sigma (X)=\sqrt{1-p}/p </math>
** Loi binomiale
** Loi hypergéométrique
** Loi de Poisson
* Lois continues

==Théorème de la limite centrale==

==Intervalle de confiance==

[http://cvresumewritingservices.org/ Resumes]

INFO913 : Cryptologie et sécurité informatique

2011-05-30T10:07:12Z

Quentinscott :

== Quelques ressources pour l'étudiant ==

# Cours
#* Support de cours (presentation [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO913/Cours/cours.pdf PDF], article [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO913/Cours/article.pdf PDF])
# Fiches de TD
#* TDs 1 : cryptographie élémentaire [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO913/TDs/td-1.ps PDF]
# TPs et autres travaux pratiques [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO913/Tests/doc/html/index.html Pages des TPs]
# Autres ressources
#* Handbook of Applied Cryptology [http://www.cacr.math.uwaterloo.ca/hac/]
#* Cryptologie en ligne [http://www.apprendre-en-ligne.net/crypto/menu/index.html]

== Déroulement (2009/2010) ==

Les exposés se feront dans l'ordre suivant. Vous pouvez vous mettre d'accord entre vous pour échanger.

# Lundi 14/12 après-midi
#* La virtualisation, facteur de sécurité ou de vulnérabilité (ok) { DIMIER Cédric et CARRIE Antoine }
#* Comment Aircrack trouve les clés WEP des réseaux wifi (ok) { LANOISELIER Aurélien et MARCHANOFF Jérôme}
#* Présentation et explication d'une attaque historique (laquelle ?) { FLEUTIAUX Marc et AGUETTAZ Cédric}
#* La biométrie, une solution miracle pour l'authentification ? (ok) { FERNANDES PIRES Anthony et GAYET Eric}
#* Stéganographie(ok) { PONCET Johan et MARTIN Romain}
#* Stéganographie ou les signatures numériques (ok) { TARDY Camille et CASSAGNERES Pierre-André}
# Mardi 15/12 après-midi
#* Sécurité anti-piratage (ok) {CHEVALIER Daniel et REIGNIER David}
#* Tour d'horizon des attaques par Injection SQL. (ok) {MILLER Lucas et VIONNET Jean}
#* Tunneling, sécurisation et piratage (ok). {COLLEN Cyril et LAQUA Johann}
# Mercredi 16/12 après-midi
#* Attaques sur SSL. (ok) {Ferlay Mathieu et Six Lancelot}
#* Le Phreaking, piratage téléphonique (ok) {Rey Myriam}
#* Securité des réseaux sans fils (ok) {Tounkara Mounina et Philippe Monteiro}

== Exposés pour l'année 2009/2010 ==

# Sujets d'exposés
#* La virtualisation, facteur de sécurité ou de vulnérabilité (ok) { DIMIER Cédric et CARRIE Antoine }
#* Comment Aircrack trouve les clés WEP des réseaux wifi (ok) { LANOISELIER Aurélien et MARCHANOFF Jérôme}
#* Présentation et explication d'une attaque historique (laquelle ?) { FLEUTIAUX Marc et AGUETTAZ Cédric}
#* La biométrie, une solution miracle pour l'authentification ? (ok) { FERNANDES PIRES Anthony et GAYET Eric}
#* Stéganographie(ok) { PONCET Johan et MARTIN Romain}
#* Stéganographie ou les signatures numériques (ok) { TARDY Camille et CASSAGNERES Pierre-André}
#* Sécurité anti-piratage (ok) {CHEVALIER Daniel et REIGNIER David}
#* Tour d'horizon des attaques par Injection SQL. (ok) {MILLER Lucas et VIONET Jean}
#* Tunneling, sécurisation et piratage (ok). {COLLEN Cyril et LAQUA Johann}
#* Attaques sur SSL. (ok) {Ferlay Mathieu et Six Lancelot}
#* Le Phreaking, piratage téléphonique (ok) {Rey Myriam}
#* Fuites de donnée en entreprise (ok) {Tounkara Mounina et Philippe Monteiro}
#* PGP et la sécurité de l'information {Cyrille Mortier}

== Exposés pour l'année 2008/2009 ==

Les exposés auront lieu le vendredi 30/1 de 8h à 12h (4CANTONS - 64) et de 13h30 à 17h30 (4CANTONS - 65). Les exposés sont à faire par binôme (ou monôme) et doivent durer 20 minutes environ. Ils seront suivis de 5 à 10 minutes de questions. Tout le monde assiste à tous les exposés.

# Sujets d'exposés (propositions, à étoffer)
#* Les Protocoles de sécurité dans les réseaux WiFi (WEP et WPA) <<<< { Mickaël Wang & Arnaud Villevieille } [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO913/Prez-2008-2009/Securite-wifi.pdf PDF]
#* Les outils d'analyse de la sécurité des réseaux : renifleur, scanneurs de ports, outils de détection d'intruison { Anis HADJALI & Vlad VESA } [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO913/Prez-2008-2009/analyse-securite.pdf PDF]
#* Google Hacking { Julien ARNOUX & Jeremy DEPOIL } [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO913/Prez-2008-2009/ghack.pptx PPTX]
#* Virus et antivirus { Mehdi MECHELOUKH et Christophe M. }
#* 3DSecure { Natalia Lecoeur & Cindy Chiaberto } [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO913/Prez-2008-2009/3D_Secure.pdf PDF]
#* Sécurité sous Linux en entreprise { Joël Leroy Ebouele & Barbier Keller }
#* Techniques et outils de chiffrements de partitions [Valat Sebastien & Bouleis Romain]
#* IP Spoofing et DNS Spoofing { Alberic Martel & Fabien Dezempte ) [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO913/Prez-2008-2009/ip-dns-spoofing.ppt PPT]
#* PRA le Plan de Reprise d'Activité {Achraf AMEUR}
#* Les attaques médiatisées sur les systèmes informatiques {Renneville Guybert et Fabrice Noraz}
#* La gestion des DRM {Petithory Thomas & Paccard Charléric}
#* L'introduction SSL,SSH { Julien Roche & Yi Wang }

== Exposés pour l'année 2007/2008 ==

Exposés le mardi 26/2 de 8h15 à 11h30 et le mercredi 27/2 de 8h15 à 11h30. Les exposés sont à faire par binôme et doivent durer 25 minutes environ. Ils seront suivis de 5 à 10 minutes de questions. Tout le monde assiste à tous les exposés.

# Sujets d'exposés (propositions, à étoffer)
#* Vulnérabilité du protocole WEP et de RC4 pour les réseaux WiFi <<<< { PAVLOU, DALLACOSTA } [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO913/Prez-2007/Presentation_cryptologie_PAVLOU_DALLA_COSTA_512.mov MOV]
#* Vulnérabilité du protocole A5/1 des mobiles GSM. <<<<< {FERNANDES} [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO913/Prez-2007/Cryptologie_et_securite_informatique_-_Fernandes.pdf PDF]
#* Les attaques médiatisées sur les systèmes informatiques : Attaque de Mitnick, Morris Worm, DDOS Mafia Boy, etc <<<< { PIPARO, HUMBERT } [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO913/Prez-2007/Les_attaques_mediatisees_-_PIPARO_HUMBERT.pdf PDF]
#* La mise en place de la sécurité informatique au niveau national et international : CERTs, sites AntiSPAM
#* Attaques par injection de code XSS, parades <<<< { SERRA & ROCHE ) [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO913/Prez-2007/Expose_securite_sur_le_XSS_-_Roche_et_Serra.pdf PDF]
#* Virus et antivirus
#* Secure shell (SSH) : protocole, applications, tunnelling <<<< {BODIN}
#* Le tatouage d'image et de document (watermarking) <<<< {MAESEELE, CIMINERA } [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO913/Prez-2007/Watermarking_Ciminera_Maeseele.pdf PDF]
#* La gestion des DRM
#* Les certificats (PGP, X509) et les infrastructures de gestion de clés
#* IP Spoofing et DNS Spoofing <<<< { DEMOLIS & JUMEAU )
#* IPsec
#* Sécurité des réseaux sans fil : authentification, chiffrement, WEP, WPA =>Bugnard/Berthet
#* Les outils d'analyse de la sécurité des réseaux : renifleur, scanneurs de ports, outils de détection d'intruison
#* Sécuriser un réseau : pare-feu, zone démilitarisée, protection des serveurs, adressage local <<<<<< {FOLLIET et VIALA} [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO913/Prez-2007/presentation_VIALA_FOLLIET.pdf PDF]
#* OpenBSD : aspects sécurité <<<<<< (REVELIN et ERROCHDI) [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO913/Prez-2007/OpenBSD_-_Revelin-Errochdi.pdf PDF]
#* Sécurité GPRS <<<<<< (PEHME et REY) [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO913/Prez-2007/Securite_GPRS_-PEHME_REY.pdf PDF]
# Planning des exposés Mardi 12/2/2008
#* Vulnérabilité du protocole A5/1 des mobiles GSM. <<<<< {FERNANDES}
# Mardi 27/2/2008, 8h15 -> 11h30
#* OpenBSD : aspects sécurité <<<<<< (REVELIN et ERROCHDI)
#* Secure shell (SSH) : protocole, applications, tunnelling <<<< {BODIN}
#* Sécuriser un réseau : pare-feu, zone démilitarisée, protection des serveurs, adressage local <<<<<< {FOLLIET et VIALA}
#* Sécurité des réseaux sans fil : authentification, chiffrement, WEP, WPA =>Bugnard/Berthet
#* Vulnérabilité du protocole WEP et de RC4 pour les réseaux WiFi <<<< { PAVLOU, DALLACOSTA }
# Planning des exposés Mercredi 28/2/2008, 8h15 -> 11h30
#* Sécurité GPRS <<<<<< (PEHME et REY)
#* Les attaques médiatisées sur les systèmes informatiques : Attaque de Mitnick, Morris Worm, DDOS Mafia Boy, etc <<<< { PIPARO, HUMBERT }
#* IP Spoofing et DNS Spoofing <<<< { DEMOLIS & JUMEAU )
#* Attaques par injection de code XSS, parades <<<< { SERRA & ROCHE )
#* Le tatouage d'image et de document (watermarking) <<<< {MAESEELE, ??? }

[http://cvresumewritingservices.org/ Resume]

INFO817 : Sémantique des langages fonctionnels et objets, preuves de programmes

2011-05-30T10:07:11Z

Quentinscott :

'''Objectifs de ce cours''' :

Comprendre la sémantique (c'est à dire la manière dont les programmes s'évaluent) des langages fonctionnel (Lisp, SML, OCaml, Python, ...) et aussi des langages objets (OCaml, Java, C++, ...).

On commencera par parler des types de données, avant de donner la sémantique d'un langage minimaliste,
mais très riche, qui permettra d'illustrer les points généraux communs à tous les langages. On essayera aussi de traiter quelques particularités de langages réellement utilisés. Enfin, on montrera comment la connaissance de la sémantique d'un langage permet de raisonner sur les programmes et donc d'obtenir
des programmes sans bug.

== Objectif du cours ==

Il s'agit d'étudier la sémantique des langages de programmation (non impératif, cf cours d'INFO 815)

Qu'est ce que le sémantique :
* Sémantique dénotationnelle : que fait le programme (quel résultat retourne la fonction...) On ne s'interesse qu'à ce qui est observable de l'extérieur
* Sémantique opérationnelle : comment le programme le fait.

Pourquoi connaître la sémantique ? La question devrait plutôt être :
comment programmer sans savoir ce que fait le programme que l'on écrit ?

L'intérêt de la sémantique c'est de prendre du recul sur la programmation et l'algorithmique afin de maîtriser les concepts
et faire abstraction de la syntaxe des langages.

La sémantique devient aussi indispensable dans le cadre des méthodes formelles et tout particulièrement de la preuve de programme
(dans ce cas on doit écrire ce que le programme fait).

== Introduction : historique et classification des langages. ==

Historique des langages ML voir [http://www.levenez.com/lang/history.html l'arbre des langages]

Un langage est défini par différent "trait" de programmation:

* fonctionnel : les fonctions sont des objets de première classe (les fonctions peuvent prendre en paramètre d'autres fonctions) et peuvent être appliqué partiellement
Fortran : non, C et C++ : en partie, ML et LISP : oui

* langage à GC : la libération mémoire est prise en charge par le langage
Fortran : non, C et C++ : oui avec lc [http://www.hpl.hp.com/personal/Hans_Boehm/gc GC de Boehm], ML et LISP : oui

* langage impératif : on peut modifier plus d'une fois le contenu d'un bloc mémoire (on n'est pas limité aux structures
de donnée persistantes)
tout les langages : oui, sauf Haskell et encore, il y a les monades

* objets : notion de classes, d'objets, ...
oui pour Java, C++, Objective-C, OCaml

* modulaire : notion de module et parfois de foncteur
oui pour les langages de la famille ML, oui pour modula, mais pas de foncteur

Pour ce cours : illustration en OCaml et PML, et structure de donnée persistante uniquement.

== Des types de données. ==

Un modèle très simple (un peu trop pour programmer directement avec)

'''Qu'est ce qu'une donnée''' :
* modèle mémoire
* modèle de graphe orientée (on distingue le rôle des pointeurs/adresses)
* arbre dans le cas des données persistentes
* arbre à branchement borné
* donnée algébrique : 3 types de noeuds ((), (x,y), L(x), R(x))

Tout programme utilisant des arbres à branchement borné peut être réecrit
avec des données algébriques en perdant au plus un facteur constant en temps
et en mémoire.

Type de données = ensemble de données partageant certaines propriétés.

===Type de données algébrique===

0 | 1 | A <math>\times</math> B | A + B | <math>\mu</math> X.A(X)

* type vide : 0 = <math>\emptyset</math>
* type avec un seul élément : 1 = {()}
* produit cartésien : A <math>\times</math> B = {(a,b) | a <math>\in</math> A et b <math>\in</math> B} (A et B étant deux types)
* somme disjointe : A + B = {L(a) | a <math>\in</math> A} <math>\cup</math> {R(b) | b <math>\in</math> B} (A et B étant deux types)
* type inductif : <math>\mu</math> X.A(X) = A(0) \cup A(A(0)) \cup A(A(A(0))) \cup ... (A étant un type avec au moins un paramètre)
Une manière de voir les types inductifs est de voir que <math>\mu</math> X.A(X) est une solution de l'équation X = A(X) sur les types.

On a d'ailleurs le théorème suivant:

Considérons <math>A_1(X_1,...,X_n), ..., A_n(X_1,...,X_n)</math> n types algébriques avec au moins n paramètres
<math>X_1, ..., X_n</math>. Considérons le systèmes d'équation suivant:

<math>\left\{\begin{matrix} X_1 = A_1(X_1,...,X_n) \\ \vdots \\ X_n = A_n(X_1,...,X_n) \end{matrix}\right.</math>

Ce système admet toujours une unique solution que l'on peut calculer en posant

# <math>X_n=\mu X_n.A_n(X_1,...,X_n)</math> et en remplaçant <math>X_n</math> dans les autres équations si n > 1 et ainsi de suite.

Type de données algébrique usuel :

* booléens : <math>\mathbb{B}</math> = 1 + 1
* type à trois éléments = (1 + 1) + 1 ou 1 + (1 + 1)
* entiers en unaires : <math>\mathbb{N}</math> = <math>\mu</math> X.1 + X
* listes à éléments dans A : <math>\mathbb{L}</math>(A) = <math>\mu</math> X.1 + (A <math>times</math> X)
* entier en binaire : <math>\mathbb{L(B)}</math>
* arbre binaire : <math>\mu</math> X.1 + (X <math>times</math> X)

'''Exercices''' :
# Donner un type des listes.
# Donner un type des arbres binaires avec des données de type A au niveau des noeuds, un type des arbres binaires avec des données de type B au niveau des feuilles, un type des arbres binaires avec à la fois des données de type A au niveau des noeuds et des données de types B au niveau des feuilles.
# Donner un type des arbres à branchement fini.
# Donner un type des entiers binaires sans zéro inutile.

'''Solutions''' :
* Rappel sur les entiers unaire:
N sol de X=1+X
µ * (1+X)=1+0 U 1+(1+0) U 1+(1+(1+0)).
={L{()}; R(L{()}); R(R(L{()}) }.
* Rappel sur les entiers binaire : liste de bool
N = 1 + ( ( 1 + 1 ) x N)
N = 1 + ( N x N )
* Liste : LL(A)= 1+(A*LL(A)), liste peut être vide ou se constitue du premier élément A et de la suite de la liste.
* Arbre sans donnée : <math>\mathbb{A}</math>=1+(<math>\mathbb{A}</math>*A). Arbre ou le premier élément est vide et la suite constitue sous arbres.

A0=1+(0*0)=L{()}

A1=1+(1+0*0)*(1+0*0)=R(L(),L())

<math>\mathbb{A}</math>=1+(A*(<math>\mathbb{A}</math>*<math>\mathbb{A}</math>)) : arbre ou le premier élément est vide et la suite se constitue d’un element A et deux sous arbres.

* Arbre binaire avec donnée sur les nœuds <math>\mathbb{A}</math>(A) :

<math>\mathbb{A}</math>(X)=1+((<math>\mathbb{A}</math>(X)*X)*<math>\mathbb{A}</math>(X))+X*(<math>\mathbb{A}</math>(X)* <math>\mathbb{A}</math>(X)).

* Arbre binaire avec donnée sur les feuilles <math>\mathbb{A}</math>’(B) :

<math>\mathbb{A}</math>’(Y)=Y+<math>\mathbb{A}</math>’’(Y)*<math>\mathbb{A}</math>(Y). L’arbre n’est pas vide.

<math>\mathbb{A}</math>’(Y)=1+<math>\mathbb{A}</math>’’(Y). arbre vide.

* Arbre binaire avec donnée sur les noeuds feuilles <math>\mathbb{A}</math>’(B) :

<math>\mathbb{A}</math>(X,Y)= Y+X *(<math>\mathbb{A}</math>’(X,Y)*<math>\mathbb{A}</math>’(X,Y)).

<math>\mathbb{A}</math>(X,Y)=1+<math>\mathbb{A}</math>’(X,Y).

* Type des arbres à branchement fini.
<math>\mathbb{A}</math>F= LL(AF)

<math>\mathbb{A}</math>f=LL(Af)

=A+<math>\mathbb{A}</math>f*Af

=<math>\mathbb{A}</math>.

* type des entiers binaires sans zéro inutile
<math>\mathbb{N}</math>*=<math>\mathbb{N}</math>*+<math>\mathbb{N}</math>

RR=0.

RL=1

L=fin

Exemple : 100=RRRRRL().

Un entier <math>\mathbb{N}</math>=1+(<math>\mathbb{N}</math>*<math>\mathbb{N}</math>).
* Let rec eq n m = match n with
L()à(match m with L(-)àL()| R(-)àR())
R(n’)à (match m with
L(-)àR(-)
| R(m’)àeqn’m’)
* Let rec append LL’=match L with
L()->L’
R(P)->R(pi1(p),append pi2(p)L’)
R(a,L1)->R(a,appendL1L’)

===Destructeurs des types algébriques===

Les destructeurs servent à lire les données d'un type algébrique.

* x <math>\in</math> 0 : abort(x) (cas impossible)
* x <math>\in</math> 1 : pas de destructeur, un seul cas possible
* x <math>\in</math> A <math>\times</math> B : 2 projections : <math>\pi_1</math>(x) <math>\in</math> A et <math>\pi_2</math>(x) <math>\in</math> B
* x <math>\in</math> A + B, (<math>\forall a \in</math> A, c[y:=a]<math>\in</math> C) et (<math>\forall b \in</math> B, c'[z:=b] <math>\in</math> C) : match x with L(y) -> c| R(z) -> c'<math>\in</math> C
* Pour utiliser les types inductifs on définira des fonctions par récurrence. exemple :
let rec add x y = match x with L(x') -> y | R(x') -> R(add x' y)
Il n'y a donc pas de destructeur particuler aux types inductifs.

===Les fonctions===

Pour programmer il nous faut des fonctions :

* A <math>\rightarrow</math> B = {<math>\lambda</math> x.t | t <math>\in</math> B si on suppose x <math>\in</math> A} : ce type désigne de type des fonctions prenant des arguments de type A et rendant un résultat de type B et <math>\lambda x.t</math> désigne la fonction qui associe t à x. Par example <math>\lambda x.x</math> est la fonction identité.

On a bien sûr un destructeur pour les fonctions : l'application

* t v <math>\in</math> B si t <math>\in</math> A <math>\rightarrow</math> B et u <math>\in</math> A

Il nous faut aussi des fonctions récursives et mutuellement récursives. Les définitions récursives peuvent s'écrire directement,
ou avec un combinateur de point fixe Y, en remplaçant la définition récursive

<math>f = t</math> où f apparait dans t (sinon la définition n'est pas récursive) par <math>f = Y f.t</math>

Pour les types, on a Y t <math>\in</math> A si t <math>\in</math> A <math>\rightarrow</math> A

'''Exemples'''
* La fonction multiplier.

Let rec mul n m=match n with
L(-) | L()
R(n’) | add(mul n’m)m

Let rec eq n m = match n with
L()|(match m with L(-)|L()| R(-)|R())
R(n’) | (match m with
L(-)|R(-)
| R(m’)|eqn’m’)

Let rec append LL’= match L with
L()|L’
R(P)| R(pi1(p),append pi2(p)L’)
R(a,L1)|R(a,appendL1L’)

* entier N

type rec nat =[End[]|
Zero[nat] |
one[nat]]

* Fonction successeur

Nat -> nat’=

Fun End[]| one [End[]]

| Zero[n]| one[n]

|one[n]|zero[succ n]

prédécesseur n-|n-1

val rec pred : nat’->nat

=Fun One[n]|Zero[n]

|Zero[n]|One[pred n]
Fonction opposé
Val opp int ->int=Fun
Minus[n]|opp(pred’n)
|n|succ n
Hauteur d’une arbre en caml

let rec hauteur = function
| Feuille -> 0
| Branche (branche, _, branche') -> 1 + max (hauteur branche) (hauteur branche') ;;

map en caml
# List.map (fun i -> i * i) [0; 1; 2; 3; 4; 5] ;;
let apply_rev f x y = f y x;;
let g x y = (x,y);;
apply_rev g 64 16;;
apply_rev (fun x y -> x / y) 3 18;;
let rec f x = (x x);;

===Sémantique dénotationnelle===

Pour préciser comment s'évalue le langage, on définit une relation d'équivalence <math>\simeq</math> comme
la plus petite relation d'équivalence vérifiant :

* <math>\pi_1</math>(u,v) <math>\simeq</math> u
* <math>\pi_2</math>(u,v) <math>\simeq</math> v
* match L(a) with L(y) -> c | R(z) -> c' <math>\simeq</math> c[y:=a]
* match R(b) with L(y) -> c | R(z) -> c' <math>\simeq</math> c'[z:=b]
* <math>(\lambda x.t)u</math> <math>\simeq</math> t[x:=u]
* Y f.t <math>\simeq</math> t[f := Y t]

'''Exercices'''
# Ecrire des fonctions calculant l'addition et la multiplication pour les entiers unaires. Évaluer ces fonctions à la main sur de petits entiers.
# Ecrire quelques fonctions sur les listes (map, append, rev, rev_append). Évaluer ces fonctions à la main sur de petites listes.

'''Corrections'''

# addition pour les entiers unaires

* solution 1: let rec add n m = match n with L (_) -> m | R (n') -> add n'(R(m))
* solution 2: let rec add n m = match n with L (_) -> m | R (n') -> R(add n' m)
* exemple: add 2 3 = add (R R L()) (R R R L()) = add (R L()) R R R R L() = add (L()) R R R R R L() = R R R R R L() = 5

# multiplication pour les entiers unaires

* solution 1 ( utilisant la récursivité non terminale) : let rec mul n m = match n with L (_) -> L() | R (n') -> add (mul n' m) m
* solution 2 (récursivité terminale) : let mul n m = aux n m (L())
* let rec aux n m a = match n with L() -> a | R(n') -> aux n' m (add m a)

===Sémantique opérationelle===

Généralités sur l'appel par nom, l'appel par valeur et l'évaluation paresseuse.

Définition d'une sémantique opérationnelle pour l'appel par valeur par contexte d'évaluation.

* Valeur : La grammaire du mini langage peut-être réécrite en distinguant deux types les valeurs des programmes qui ne sont pas des valeurs:
<math>V = x \mid \lambda x.T \mid L V \mid R V \mid (V, V) \mid ()</math>
<math>T = V \mid T T \mid match T with L x -> T | R y -> T \mid \pi_1 T \mid \pi_2 T</math>

* Contexte d'évaluation
* La sémantique

Définition d'une sémantique opérationnelle pour l'appel par valeur avec une machine abstraite.

* Clôture
* Machine SECD
* Table de transition

'''Exercice''' : faire le même travail pour l'appel par nom. Pourquoi tout ceci serait plus compliqué pour l'évaluation paresseuse ?

===Quelques théorèmes===

* Préservation du type par réduction
* Existence d'un unificateur le plus général sur les types
* Inférence de type
* Théorème de Church-Rosser

== Présentation de la syntaxe et de la sémantique d'un petit langage. ==

== Encodage et sémantique des objets. ==

== Typage statique et dynamique. ==

== Quelques commentaires sur C, Java, C++, ... ==

== Vers la preuve de programmes. ==

== Bibliographie ==

"Foundations for Programming Languages" de John C. Mitchell

"The ZINC experiment, an economical implementation of the ML language" de Xavier Leroy. Rapport technique 117, INRIA, 1990. [http://caml.inria.fr/pub/papers/xleroy-zinc.pdf pdf]
Ce rapport contient une description du compilateur ZINC, dont l'évolution a ensuite donné naissance à Caml Light puis Objective Caml. Une grande partie de ce rapport est obsolète. Néanmoins, il garde un intérêt pour la description de la machine abstraite utilisée par Caml Light et (avec quelques simplifications et améliorations supplémentaires) par Objective Caml.

[http://customessays.ws/ Custom essays]

INFO517 : Programmation C

2011-05-30T10:07:08Z

Quentinscott :

Cours du semestre 5 de la licence STIC INFO.

* Responsable pour 2010--2011: [http://www.lama.univ-savoie.fr/~lachaud Jacques-Olivier Lachaud]
* Jacques-Olivier Lachaud (C/TD/TP), Xavier Provençal (TP)

Pensez à consulter les [[Comment compiler le C ?|indications pour compiler un petit programme sur une machine des salles de TP]].

== Quelques ressources pour l'étudiant (2010-2011) ==

# Notes de cours [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO517/Cours/notes-de-cours.ps PostScript] [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO517/Cours/notes-de-cours.pdf PDF]
# Fiches de TD
#* TD 1 et 2 : tableaux, entrées-sorties [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO517/TDs/td-1.ps PostScript] [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO517/TDs/td-1.pdf PDF]
#* TD 3 : exercices sur les pointeurs [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO517/TDs/td-2.ps PostScript] [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO517/TDs/td-2.pdf PDF]
# TPs et autres travaux pratiques [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO517/Tests/doc/html/index.html Pages des TPs]
#* Pour la première fois, on pourra aussi regarder la page [[Comment_compiler_le_C_%3F]]
#* Si vous n'accédez pas aux pages "manual" en salle TP, on les trouve en ligne : [[http://www.linux-france.org/article/man-fr/ Manual pages]]
# Autres ressources

N'hésitez pas à contribuer au wiki, et en particulier à cette page:
clarifications, compléments, exemples… Si vous n'avez pas compris un point
particulier, vous pouvez signaler votre problème sur la page de discussion
(onglet en haut de cette page) ou par les moyens habituels. Il sera ensuite
très positif de revenir sur cette page et de consigner ce qui vous posait
problème et ce qui vous a permis de mieux comprendre.

== Déroulement (2010-2011) ==

Ceci n'est qu'une prévision.

* (Cours 1): lundi 20 septembre. Langage C, intérêts et défauts. Compilation. Eléments de base du langage (types simples, variables, expressions). (=> I.5).
* (TD 1): mercredi 29 septembre. Instructions et structures de contrôle usuelles (conditionnelles, boucles) (=> I.10)
* (TD 2): jeudi 30 septembre. TD 1 tableaux, fonctions en C, E/S simples.
* (Cours 2): vendredi 1er octobre. Fonctions, passage de paramètres, pointeurs (=> II.5).
* (TD 3): vendredi 1er octobre. TD 1 tableaux, fonctions en C, E/S simples (II).
* (Cours 3): lundi 4 octobre. Fonctions, passage de paramètres, pointeurs, allocation dynamique (=> II.10)
* (Cours 4): lundi 4 octobre. Un exemple complet : les piles en C (II.11).
* (TP 1): mercredi 6 octobre. Boucles, puissance 4, tracés avec gnuplot, récursivité.
* (TD 4): vendredi 8 octobre. Exercices simples sur les pointeurs.
* (TD 5): lundi 11 octobre. Pile d'exécution. Structures auto-référents. Début skip-liste.
* (TP 2): mercredi 13 octobre. Tetris texte.
* (TD 6): vendredi 15 octobre. Skip-listes. Compilation séparée et bonnes habitudes de développement C.
* (TP 3): jeudi 21 octobre. Tetris graphique avec GTK.

== Historique ==

* Responsable pour 2009--2010: Emilie Charrier (C/TD/TP)
* Responsable pour 2008--2009: Lionel Vaux (C/TD/TP)

== Ressources pour l'étudiant (avant 2010) ==

Cet enseignement comprendra 10 séances de cours/TD (1h30) et 3 séances de TP (4h).

La distinction entre cours et TD restera floue. Je vous demanderai
généralement d'écrire quelques petits programmes d'une semaine sur l'autre.
Autant que possible, envoyez-moi vos fichiers sources à l'adresse
<tt>lionel.vaux@univ-savoie.fr</tt>, afin que je puisse évaluer le niveau de
chacun et ajuster le contenu des séances suivantes.

Et dites-moi si ça ne
va pas, ou je risque d'avancer trop vite.

=== Objectifs du cours ===

==== Cours/TD ====
* Principes généraux et particularités du langage: programmation impérative, typage fort à la compilation, adressage mémoire explicite
* Syntaxe de base
* Bibliothèque standard: entrée-sorties et interaction avec le système d'exploitation
* C avancé:
** allocation dynamique
** modèle mémoire (pile, tas, code)
** pointeurs sur structures
** pointeurs sur fonctions
* Bonnes pratiques

==== En TP ====
* un TP de mise en route et de précision de la notion de compilation en C
* un projet logiciel sur les deux dernières séances (8h)

==== Outils et concepts (survol théorique et utilisation optionnelle en TP) ====
* automatisation de la compilation (make),
* analyse de l'exécution et déboguage (gdb et DDD),
* boîte à outils graphique (gtk+)

=== Supports ===

* Exercices de TD :
*# la [http://www.lama.univ-savoie.fr/~vaux/ens/INFO517-TD1.pdf feuille 1] ;
*# la [http://www.lama.univ-savoie.fr/~vaux/ens/INFO517-TD2.pdf feuille 2] et une archive [http://www.lama.univ-savoie.fr/~vaux/ens/liste.tar.gz <tt>liste.tar.gz</tt>] comprenant une solution pour l'implémentation des listes et des listes triées (les piles ont été traitées en [[INFO517-cours7|séance 7]]).

* Devoir à la maison : le sujet [http://www.lama.univ-savoie.fr/~vaux/ens/INFO517-DM1.pdf <tt>INFO517-DM1.pdf</tt>] et les fichiers sources [http://www.lama.univ-savoie.fr/~vaux/ens/dm1.c <tt>dm1.c</tt>] et [http://www.lama.univ-savoie.fr/~vaux/ens/mat.c <tt>mat.c</tt>] associés.

* Examens :
*# sujet [http://www.lama.univ-savoie.fr/~vaux/ens/INFO517-Partiel1.pdf <tt>INFO517-Partiel1.pdf</tt>] et corrigé [http://www.lama.univ-savoie.fr/~vaux/ens/INFO517-Partiel1-correction.pdf <tt>INFO517-Partiel1-correction.pdf</tt>].
*# sujet [http://www.lama.univ-savoie.fr/~vaux/ens/INFO517-Partiel2.pdf <tt>INFO517-Partiel2.pdf</tt>] et corrigé [http://www.lama.univ-savoie.fr/~vaux/ens/INFO517-Partiel2-correction.pdf <tt>INFO517-Partiel2-correction.pdf</tt>].
*# sujet [http://www.lama.univ-savoie.fr/~vaux/ens/INFO517-Terminal.pdf <tt>INFO517-Terminal.pdf</tt>] et corrigé [http://www.lama.univ-savoie.fr/~vaux/ens/INFO517-Terminal-correction.pdf <tt>INFO517-Terminal-correction.pdf</tt>].
*# sujet [http://www.lama.univ-savoie.fr/~vaux/ens/INFO517-Rattrapage.pdf <tt>INFO517-Rattrapage.pdf</tt>] et corrigé [http://www.lama.univ-savoie.fr/~vaux/ens/INFO517-Rattrapage-correction.pdf <tt>INFO517-Rattrapage-correction.pdf</tt>].

=== Séances de Cours/TD ===

# [[INFO517-cours1|lundi 22 septembre 2008]].
#* mise en route: exemples de programmes simples et compilation;
#* syntaxe de base: types, déclarations, affectations, boucles, entrées et sorties simples (caractère par caractère);
# [[INFO517-cours2|lundi 29 septembre 2008]]
#* fonctions;
#* tableaux et chaînes;
#* récursion;
# [[INFO517-cours3|lundi 6 octobre 2008]]
#* exercices (feuille 1);
# [[INFO517-cours4|lundi 13 octobre 2008]]
#* adresses et pointeurs;
#* passage par adresse;
#* les tableaux comme pointeurs;
#* opérateur <tt>sizeof</tt>;
#* arithmétique de pointeurs;
#* allocation des variables locales: le problème des tableaux;
#* allocation dynamique: <tt>malloc()</tt>, <tt>free()</tt>, <tt>realloc()</tt>;
# [[INFO517-cours5|lundi 20 octobre 2008]]
#* modèle mémoire: pile, tas, segment de code;
#* différence entre déclaration de tableau et déclaration de pointeur;
#* affichage des données de la pile d'exécution, adresses de retour;
# [[INFO517-cours6|lundi 3 novembre 2008]]
#* types complexes: <tt>struct</tt>, <tt>union</tt>, <tt>enum</tt>;
#* premier partiel;
# [[INFO517-cours7|lundi 10 novembre 2008]]
#* pointeurs vers <tt>struct</tt>;
#* structures récursives;
#* exemple: les piles (FILO);
#* <tt>Makefile</tt>s;
#* exercices (feuille 2);
# [[INFO517-cours8|lundi 17 novembre 2008]]
#* correction du premier partiel;
#* exercices (suite de la feuille 2);
# [[INFO517-cours9|lundi 24 novembre 2008]]
#* préparation du TP1
#* entrées et sorties dans des fichiers
#* opérations bit-à-bit;
# [[INFO517-cours10|lundi 1er décembre 2008]]
#* deuxième partiel;
#* pointeurs sur fonctions;
#* une session DDD;

=== Séances de TP ===

Les sujets de TP se trouvent sur
[http://www.lama.univ-savoie.fr/~vaux/ens/INFO-517-TP cette page].

# mercredi 15 octobre 2008 : [http://www.lama.univ-savoie.fr/~vaux/ens/INFO-517-TP/TP0.html TP0 — Préliminaires]
# vendredi 28 novembre 2008 : [http://www.lama.univ-savoie.fr/~vaux/ens/INFO-517-TP/TP1.html TP1 — Formats d'image]
# vendredi 12 décembre 2008 : [http://www.lama.univ-savoie.fr/~vaux/ens/INFO-517-TP/TP2.html TP2 — Affichage et interface graphique]

==Références==

* ''The C programming language'', de Kernighan et Ritchie;
* ''Le langage C'', version française du précédent;
* Le polycopié de Bernard Cassagne, disponible [http://www-clips.imag.fr/commun/bernard.cassagne/Introduction_ANSI_C.html ici], au format [http://www-clips.imag.fr/commun/bernard.cassagne/Introduction_ANSI_C.html html] (consultable en ligne) ou [ftp://ftp.imag.fr/pub/labo-CLIPS/commun/C/Introduction_ANSI_C.pdf pdf];
* Le wikilivre [http://fr.wikibooks.org/wiki/Programmation_C ''Programmation C'']: un livre de cours sur le mode wikipedia.

[http://customessays.ws/ Custom essay]