WiKi informatique - tc_info

2018-2019

Anonymous (anonymous@undisclosed.example.com) — 2019-07-31T08:55:42+00:00

Tronc Commun Informatique * Remplissez vos parties et mettez vos fichiers tex et autres ressources sur votre visible avec un lien ici (ex : omis 2018). * lien vers : sujet TD/TP/ corrigé. * ici que le plan de la partie ou séance. * 33 séances dont :

2019-2020

Anonymous (anonymous@undisclosed.example.com) — 2020-09-21T10:10:50+00:00

* 33 séances dont : * 7 CM * 13 TD * 13 TP * 6 groupes CM1 Complexité(s) TD1 Complexité corrigé TP1 Rappels Python corrigé CM2 Graphes TD2 Graphes corrigé TP2 Graphes corrigé CM3 Données non structurées TD3 Arbres corrigé TP3 Arbres corrigé TD4 Flots corrigé TP4 Flots corrigé TDA1 Les tris corrigé TPA1 corrigé [CM4 Fichiers et indexation] TD5 Algos texte corrigé TP5 Algos texte corrigé CM5 TODO TD6 Indexation corrigé TP6 I…

2020_cm_ana

Anonymous (anonymous@undisclosed.example.com) — 2021-01-19T12:29:29+00:00

Analyse des données L’analyse des données a pour but de recomposer l’information contenue dans les données recueillies afin d’en fournir une vue plus synthétique, ou d’extraire des informations qui n’apparaissent pas de façon explicite dans la série de mesures initiale.$R$$d$$id(d)$$$\text{ref} : \text{id} \rightarrow d = \text{ref}(\text{id}) $$$d$$D$$n$$i < n$$D[i]$$$I = ((\text{id}_1, d_1), (\text{id}_2, d_2), ..., (\text{id}_n, d_n))$$$\text{id}_1 < \text{id}_2 < ... < \text{id}_N$$$ I = \{…

2020_cm_index

Anonymous (anonymous@undisclosed.example.com) — 2021-01-27T20:46:51+00:00

Fichiers et indexation * Il s'agit par définition des informations qui doivent être conservées entre deux exécutions. * Avec l’augmentation des capacités de stockage et leur mise en réseau, les quantités de données conservées ont considérablement augmenté au cours des dernières décennies. $N$$$B = \underset{0}{0}{10010100100.....}\underset{n-1}{01}$$$n$$k < n$$d$$i < n$$m$$i$$m$$d$$m$$B$$d$$k(d)$$d_1$$d_2$$d_1 = d_2$$k(d_1)=k(d_2)$$k(d_1) = k(d_2)$$d_1=d_2$$d$$I$$k$$i$$I : k \rightarrow…

2020_cm_relation

Anonymous (anonymous@undisclosed.example.com) — 2024-06-28T13:18:11+00:00

Bases de données relationnelles On introduit dans ce chapitre le modèle relationnel qui sert de fondation à la conception de bases de données. Les différents modèles utiles en représentation des connaissances reposent sur des notions de base de la théorie des ensembles :$$ t = (a_1, ..., a_m) $$$R$$R$$R(A_1, ..., A_m)$$\text{dom}(A_i)$$A_i$$t$$R = (A_1,...,A_m)$$r$$R$$\text{dom}(A_1) \times ... \times \text{dom}(A_m)$$$ r = \{t_1, ..., t_n\} = \{ (a_{11}, ..., a_{1m}), ..., (a_{n1}, ..., a_{n…

2020_cm_ri

Anonymous (anonymous@undisclosed.example.com) — 2024-12-20T08:21:56+00:00

Recherche d'information Rappel : modèle relationnel tablestuplesvaleurs * Une base de données est un ensemble de tables (parfois appelées relations). * Une table est un ensemble de tuples (parfois appelés enregistrements). * Un tuple est un ensemble de $\pi$$\sigma$$r$$R$$S$$S$$R$$\pi_S(r)$$S$$r$$S$$$\pi_S(r) = \{t(S)|t \in r\}$$$t(S)$$t$$S$$$u = \pi_\text{nom_fournisseur, adresse_fournisseur} (\text{Catalogue})$$$\rightarrow$$R (A_1, …, A_n)$$F$$R$$A_1$$A_n$$$ F = (A_1 = 3) ∧ (A_1 >…

2020_cm_textes

Anonymous (anonymous@undisclosed.example.com) — 2025-04-23T08:59:41+00:00

Algorithmes sur les Textes 1 Données texte 1.1 Encodage des données On distingue classiquement deux grandes catégories de données : * données quantitatives: * numérique entier ou réel, discrètes ou continues, bornées ou non. ex: poids, taille, âge, taux d’alcoolémie,$O(m \times k)$$\Sigma$$\Sigma$$\Sigma$$S$$A : S \times \Sigma \rightarrow S \times \Sigma'$$s_0 \in S$$\Sigma = \{0, 1\}²$$\Sigma' = \{0, 1\}$$S = \{1, 2\}$$s_0 = 1$$ab$$\Sigma = \{a, b\}$$n_{max}$$|V|\times n_{max}$$p \su…

2020_cpp_1-1-1

Anonymous (anonymous@undisclosed.example.com) — 2020-10-01T07:46:50+00:00

Il ne faut pas oublier la retenue Un nombre n'est qu'une suite de chiffres (on peut additionner deux nombres sans connaître leur valeur) Il faut lire les nombre de la droite vers la gauche. Solution

2020_cpp_1-1-2

Anonymous (anonymous@undisclosed.example.com) — 2020-10-01T07:45:44+00:00

$A$ & $B$ sont deux tableaux de $n$ chiffres, la solution sera un tableau $C$, lui aussi à $n$ chiffres. $A[0]$ & $B[0]$ correspondent au chiffre le plus à droite. $retenue$ $\gets 0$ for $i \gets 0$ to $n-1$: $\;\;\;\;$ $C[i] \gets A[i] + B[i] + retenue$ $\;\;\;\;$ $retenue \gets 0$ $\;\;\;\;$ if $C[i] > 9$: $\;\;\;\;\;\;\;\;$ $C[i] \gets C[i] - 10 $ $\;\;\;\;\;\;\;\;$ $retenue \gets 1 $ if $retenue = 0$: $\;\;\;\;$ return $C$ return None

2020_cpp_1-1

Anonymous (anonymous@undisclosed.example.com) — 2020-10-01T07:46:39+00:00

Quand on fait une addition à la main, on part d'opérations élémentaires que l'on connait par cœur (elles sont "cablées" — ce sont les opérations de chiffres, de $0+0$ à $9+9$) que l'on insère dans un algorithme (celui qu'on vous demande d'écrire) qui vous permet de calculer facilement $432678449 + 765345129$

2020_cpp_1-2-1

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T09:21:50+00:00

$x$ & $y$ sont les deux nombres à additionner. $r$ est le résultat $r \gets x$ for $i \gets 1$ to $y$: $\;\;\;\;$ $r \gets succ(r)$ return $r$

2020_cpp_1-2

Anonymous (anonymous@undisclosed.example.com) — 2020-10-01T07:47:51+00:00

On peut utiliser comme opération de base le "successeur": $succ(x) := x + 1$ Solution

2020_cpp_1-3-1

Anonymous (anonymous@undisclosed.example.com) — 2020-10-01T07:49:48+00:00

Cet algorithme semble polynomial. En fait, ce n'est pas du tout le cas. La complexité d'une algorithme n'est pas simplement le nombre d'opérations que celui-ci exécute. C'est la fonction qui relie ce nombre d'opérations à la taille (de l'instance) du problème (des données).$x$$y$$\log x + \log y$$\log$$n_y$$y$$O(2^{n_y})$

2020_cpp_1-3

Anonymous (anonymous@undisclosed.example.com) — 2020-10-01T07:50:17+00:00

Le premier algorithme (le "classique") est en $O(n)$. Le deuxième est en $O(y)$ ATTENTION (IMPORTANT)

2020_cpp_2-1-1

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T10:01:49+00:00

$r \gets 1$ for $i \gets 1$ to $y$: $\;\;\;\;$ $r \gets r \times y$ $\;\;\;\;$ # Ligne A return $r$

2020_cpp_2-1-2

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T09:49:54+00:00

def puissance($x, y$): $\;\;\;\;$if $y = 0$: $\;\;\;\;$ $\;\;\;\;$ return 1 $\;\;\;\;$ return $x \times$ puissance($x, y-1$)

2020_cpp_2-2

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T09:55:38+00:00

$O(y)$

2020_cpp_2-3

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T11:24:44+00:00

Pour le récursif : rien à faire. Pour l'itératif: à la ligne "Ligne A", $r$ vaut $x^i$.

2020_cpp_3-1

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T11:32:01+00:00

$T$ est un tableau de $n$ nombres $maximum$ $\gets -\infty$ for $i\gets 0$ to $n-1$: $\;\;\;\;$ if $maximum < T[i]$: $\;\;\;\;$ $\;\;\;\;$ $maximum \gets T[i]$ return $maximum$

2020_cpp_3-2

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T11:38:37+00:00

def $maximum(T)$: $\;\;\;\;$ if $T = [\,]$: $\;\;\;\;\;\;\;\;$ return $-\infty$ return $\max (T[0], maximum(T[1:]))$

2020_cpp_3-3

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T11:40:57+00:00

La version itérative compare la valeur de l'"élément courant" avec le maximum des valeurs déjà vues, alors que le récursif compare l'élément courant avec les éléments que l'on verra par la suite.

2020_cpp_4-1-2

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T12:03:44+00:00

$A^B$

2020_cpp_4-1

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T12:03:10+00:00

Essayez pour des petites valeurs (2 & 3) de $A$ & $B$. Solution

2020_cpp_4-2-1-2

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T13:00:31+00:00

Le cas le plus rapide correspond à utiliser systématiquement $y \gets y/2$.On passe de $B$ à 1 en $\log_2 B$ étapes. L'algorithme est donc en $O(\log B)$.

2020_cpp_4-2-1

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T12:57:52+00:00

Une itération de boucle prend un temps constant. Il faut donc compter les itérations. On part de $y = B$ & on va jusqu'à $y=0$ (en passant par $y=1$). Le cas le meilleur correspond donc à la descente la plus rapide. Solution

2020_cpp_4-2-2-1

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T13:04:41+00:00

On ne peut passer au maximum qu'une fois sur deux par $y\gets y-1$, donc on passe au moins une fois sur deux par $y \gets y/2$. Dans le cas le pire, l'algorithme est donc aussi en $O(\log B)$.

2020_cpp_4-2-2

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T13:03:24+00:00

Le cas le pire correspond à la descente la plus lente, c'est à dire quand on passe le plus de fois possible par $y \gets y -1$. Solution

2020_cpp_4-2

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T13:19:46+00:00

Il faut "remarquer" que $x^y \times r$ est un invariant de boucle. Il est en effet évident que sa valeur ne change pas entre les lignes 2 & 3. Donc sa valeur ne change pas entre les lignes 1 & 4. À la ligne 1, sa valeur est $A^B$. À la ligne 4, comme $y=0$ (on est sorti de la boucle), sa valeur est $r$

2020_cpp_5-1

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T13:28:51+00:00

Quand on examine la case $T[i]$, le début du tableau (des cases $T[0]$ à $T[i-1]$) est trié. Il contient les $i$ plus petits éléments pour le tri par sélection, & les $i$ premiers pour le tri par insertion.

2020_cpp_6-1

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T13:47:17+00:00

Voici un algorithme qui reconnait les palindromes. En entrée, on a une liste. def $palindrome(L)$: $\;\;\;\;$ return ($T[0] == T[-1]$) and $palindrome(L[1: -1])$ La relation de récurrence sur le nombre d'opérations est : $t(n) = 1 + t(n-2)$, cet algorithme est donc en $O(n)$. ATTENTION (IMPORTANT)

2020_cpp_6-2

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T13:44:16+00:00

Le calcul de la complexité est FAUX. Indications

2020_cpp_6-3

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T13:47:43+00:00

Quand on écrit $L[1: -1]$, on effectue une recopie de la partie "centrale "de la liste, qui prend un temps $O(n)$. La relation de récurrence est donc $t(n) = n + t(n-2)$, & l'algorithme en $O(n^2)$. Il est possible d'éviter la recopie & donc de l'écrire en $O(n)$. Solution(correcte)

2020_cpp_7

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T13:58:14+00:00

Regardez sur internet, par exemple sur wikipédia.

2020_cpp-6-4

Anonymous (anonymous@undisclosed.example.com) — 2020-10-01T07:57:47+00:00

def $palindrome(L)$: $\;\;\;\;$ return $palin(L,\, 0,\, len(L)$ def $palin(L,\, deb,\, fin)$: $\;\;\;\;$ if $fin -deb \leq 1$: $\;\;\;\;\;\;\;\;$ return True $\;\;\;\;$ return $(L[deb] == L[fin-1])$ and $palin(L,\, deb + 1,\, fin -1)$

2020_indexation

Anonymous (anonymous@undisclosed.example.com) — 2020-12-10T21:04:23+00:00

* TD indexation * corrigé * TP indexation * Corrigé

2020_td_comp

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T13:57:41+00:00

TD "Complexité & Preuves de Programmes" 1. Addition Donnez deux algorithmes qui additionnent deux nombres entiers. * Un premier qui est celui utilisé quand on fait une addition "à la main" Indications * Un deuxième qui utilise d'autres "fonctions de base" $x$$y$$x^y$$misterioso(A, B)$$\;\;\;\;$$A$$B$$\;\;\;\;$$x \gets A ;\, y \gets B ;\, r \gets 1$$\;\;\;\;$$\;\;\;\;$$y \neq 0$$\;\;\;\;$$\;\;\;\;$$\;\;\;\;$$\;\;\;\;$$y$$\;\;\;\;$$\;\;\;\;$$\;\;\;\;$$r \gets r \times x$$\;\;\;\;$$\;\;\;\;…

2020_td-tp_abr_exo1_indic-indic-sol

Anonymous (anonymous@undisclosed.example.com) — 2020-10-05T12:33:53+00:00

Sur un arbre vide, le nombre de feuilles, le nombre de sommets & la hauteur valent 0. Sur un arbre fait d'un seul sommet, le nombre de feuilles, le nombre de sommets & la hauteur valent 1. Sur un arbre quelconque, avec deux fils $F_{G}$ & $F_{D}$ : * le nombre de sommets $N_S$$N_S(F_{G}) + N_S(F_{D}) + 1$$N_F$$N_F(F_{G}) + N_F(F_{D})$$H$$\max(H(F_{G}), H(F_{D}))$

2020_td-tp_abr_exo1_indic-indic

Anonymous (anonymous@undisclosed.example.com) — 2020-10-05T11:57:56+00:00

Il suffit de trouver une formule récursive qui donne les nombre de sommets (ou feuilles, ..) d'un arbre, selon les trois cas qui s'appliquent ici (un arbre peut être vide, réduit à une feuille ou constitué d'une racine & de deux sous-arbres). Solution

2020_td-tp_abr_exo1_indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-06T15:14:15+00:00

Il est conseillé d'utiliser la récursivité Plus de détails

2020_td-tp_abr_exo2_indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-06T17:31:34+00:00

Il faut utiliser un crayon.

2020_td-tp_abr_exo3_indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-06T16:05:38+00:00

Les parcours Pré-Ordre & Post-Ordre ne donnent rien (de spécial).

2020_td-tp_abr_exo4-1_indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-06T16:17:05+00:00

Il s'agit de créer un nouveau sommet de l'arbre. Ce nouveau sommet est toujours une feuille (Pourquoi ?). On pourra remarquer que l'insertion ressemble (forcément (Pourquoi ?)) à la recherche.

2020_td-tp_abr_exo4-2_indic-indic-indic-2

Anonymous (anonymous@undisclosed.example.com) — 2020-08-06T17:28:07+00:00

L'appel récursif se fait sur un sommet qui a au plus un fils.

2020_td-tp_abr_exo4-2_indic-indic-indic-indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-06T16:45:33+00:00

Une valeur qui "va bien" est le plus petit des descendants droits (ou, symétriquement, le plus grand des descendants gauches); Celui-ci se trouve très facilement (faire quelques essais si on ne voit pas).

2020_td-tp_abr_exo4-2_indic-indic-indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-06T16:43:14+00:00

Cette valeur doit déjà être dans l'arbre (il faut supprimer une valeur, pas en insérer une) & être dans le sous-arbre de racine le sommet à supprimer. Toujours des détails.

2020_td-tp_abr_exo4-2_indic-indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-06T17:27:17+00:00

Contrairement aux deux cas simples où on supprime effectivement le sommet de l'arbre. Ici, on va dans un premier temps remplacer la valeur à supprimer par une valeur qui va bien (Encore des détails), puis on supprimera l'occurrence d'origine de cette valeur. Combien d'appels récursifs (de la suppression) doit-on faire pour une suppression effective ?

2020_td-tp_abr_exo4-2_indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-06T16:33:06+00:00

La suppression d'une valeur (& donc du sommet correspondant) dans un arbre de recherche est beaucoup plus délicate que son insertion. L'idée de base esr de considérer trois cas : * L'élément à supprimer est une feuille (très simple), * L'élément à supprimer n'a qu'un seul fils (simple),

2020_td-tp_abr_exo5-1_indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-06T16:49:57+00:00

Il s'agit simplement d'une suite d'insertions.

2020_td-tp_abr_exo5-2_indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-06T16:52:24+00:00

Il s'agit de QuickSort. Pourquoi ?

2020_td-tp_abr_exo8_indic-indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-06T17:21:00+00:00

Il faut d'abord remarquer que s'arrêter dès que possible n'est pas gratuit (il faut deux tests au lieu d'un à chaque étape). À partir de là, on peut se demander quelle est la probabilité que l'on s'arrête "rapidement".

2020_td-tp_abr_exo8_indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-06T17:17:15+00:00

Il est plus efficace d'aller, systématiquement, jusqu'à un tableau de taille 1. Pourquoi ? Indication

2020_td-tp_abr_exo9_indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-06T17:45:06+00:00

Si le nombre d'éléments ne varie pas, il vaut mieux utiliser un tableau, c'est plus simple (une fois le tableau trié, on ne fait que des recherches dichotomiques). Si le nombre d'éléments varie, il vaut mieux utiliser un arbre de recherche : il n'est pas possible, dans un tableau trié, d'insérer ou supprimer un élément de manière efficace.

2020_td-tp_abr

Anonymous (anonymous@undisclosed.example.com) — 2020-08-09T12:18:36+00:00

TD-TP "Arbres Binaires de Recherche" Ce "TD-TP" est, comme son nom l'indique, constitué une partie TD à faire sur papier (il est conseillé de faire aussi l'exercice 7 sur machine) & d'une partie TP à faire sur machine. Il n'est pas nécessaire de faire tout le TD avant d'attaquer le TP, néanmoins, avant de programmer un algorithme, il faut l'écrire à la main.$s$$s$$s$$x$$x$$x$

2020_td-tp_flo_exo1_indic_indi

Anonymous (anonymous@undisclosed.example.com) — 2020-08-08T11:38:09+00:00

Sa capacité doit donc être $+\infty$ (à peu près).

2020_td-tp_flo_exo1_indic-1

Anonymous (anonymous@undisclosed.example.com) — 2020-08-08T11:35:48+00:00

L'intérêt de cet arc est double : * Faire en sorte que la loi des nœuds soit aussi respectée en $s$ & $p$. * La valeur du flot sur cet arc est ce que l'on veut maximiser.

2020_td-tp_flo_exo1_indic-2-indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-08T12:30:55+00:00

Si l'ancien flux est réalisable, le nouveau flux l'est aussi. En effet : * Les contraintes de capacités (qui ne changent que sur $P$) sont toujours satisfaites (par définition des capacités résiduelles & puisque $\hat{c}$ est la plus petite d'entre elles).

2020_td-tp_flo_exo1_indic-2

Anonymous (anonymous@undisclosed.example.com) — 2020-08-08T11:38:34+00:00

Cet arc (& sa capacité) ne doit créer aucune nouvelle contraintes. Réponse

2020_td-tp_flo_exo1_indic-3

Anonymous (anonymous@undisclosed.example.com) — 2020-08-08T12:25:41+00:00

Soit $P$ un chemin de $s$ à $p$ (dans $G_\phi$), & $\hat{c}$ la plus petite capacité (résiduelle) des arcs de $P$. On peut augmenter, sur tous les arcs du chemin, la valeur du flux de $\hat{c}$ (pourquoi ? Réponse), & on augmente le flux total de $\hat{c}$.

2020_td-tp_flo_exo1_indic-4

Anonymous (anonymous@undisclosed.example.com) — 2020-08-08T12:46:54+00:00

$\Phi \gets$ Flot nul tant que $\exists$ chemin $P : s \mapsto p$ dans $G_\Phi$: $\;\;$ Augmenter le flux sur $P$ de $\hat{c}$ $\,$ $\,$ $\,$ Pour plus de détails, voir la partie TP.

2020_td-tp_flo_exo2_indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-08T13:08:20+00:00

$G=(V,A)$, avec : $V = \{s, p\} \cup H \cup F$, où $H$ est l'ensemble des hommes & $F$ celui des femmes. $A$ = $\{(s,h) : h\in H \} \cup \{(f, p) : f \in F\} \cup \{(h,f) : \{h,f\}$ est un couple compatible$\}$ Tous les arcs sont de capacité 1.

2020_td-tp_flo_exo3_indic-indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-08T13:55:39+00:00

Pour cela, on va remplacer chaque ville $A$ par $K+1$ villes $A_0$, $A_1$, ..., $A_K$ correspondant à la ville $A$ aux instants 0, 1, ..., $K$. $\,$ Il faut aussi adapter les arcs. Indication

2020_td-tp_flo_exo3_indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-08T13:33:19+00:00

On peut remplacer chaque arête $xy$ de capacité $c$ par deux arcs ($(x,y)$ & $(y,x)$) de capacité $c$. $\,$ On peut aussi construire le graphe d'écart ainsi : Si, dans une arête $u = xy$ de capacité $c_u$, un flux $\phi_u$ va de $x$ à $y$, le graphe d'écart contiendra un arc $(x,y)$ de capacité $c_u - \phi_u$ & un arc $(y,x)$$c_u + \phi_u$$\,$

2020_td-tp_flo_exo4_indic-indic-indic-indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-08T14:05:21+00:00

Le puit est la marne à l'instant $K$. La source est un nouveau sommet $s$, que l'on relie à chaque ville $A_0$ par un arc de capacité le nombre de taxis présents au départ dans la ville $A$.

2020_td-tp_flo_exo4_indic-indic-indic

Anonymous (anonymous@undisclosed.example.com) — 2020-10-01T12:09:11+00:00

Une route de capacité $c$ qui permet d'aller d'une ville $A$ à une ville $B$ en un temps $t$ va être représentée par $K-t + 1$ arcs, un qui va de $A_0$ à $B_t$, un qui va de $A_1$ à $B_{t+1}$, ..., un qui va de $A_{K-t}$ à $B_K$, tous de capacité $c$. $\,$ Chaque ville $A_t$ est reliée à $A_{t+1}$ par un arc de capacité $p_A$$\,$

2020_td-tp_flo_exo4_indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-08T13:49:32+00:00

La difficulté de ce problème est qu'il fait intervenir à la fois des contraintes temporelles ($\mapsto$ chemins) & des contraintes de capacité ($\mapsto$ flots). On va favoriser les flots; On va donc "sortir" les contraintes temporelles des arcs (qui alors n'auront plus que des capacités).

2020_td-tp_flo_exo5_indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-08T14:46:56+00:00

À un arc $u$ de longueur $l_u$, on associe un arc identique, de coût $l_u$, de capacité minimale 0 & maximale $\infty$. On rajoute un arc $(y,x)$ de capacité minimale 1, maximale $\infty$ & de coût nul.

2020_td-tp_flo_exo6_indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-08T15:15:16+00:00

Il peut exister plusieurs flots maximums mais, si les capacités sont entières, au moins un est à valeur entière. C'est évident d'après le fonctionnement de l'algorithme des graphes d'écart. $\,$ Ce résultat a beaucoup d'importance d'un point de vue pratique.

2020_td-tp_flo_tp_exo1_indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-08T15:33:26+00:00

Ce graphe a 6 sommets (numérotés de 1 à 6). Le Sommet 1 a 2 voisins (les sommets 2 & 3 — par contre 1 n'est voisin ni de 2 ni de 3) L'arc entre 1 & 2 est de capacité 5.

2020_td-tp_flo_tp_exo2_indic

Anonymous (anonymous@undisclosed.example.com) — 2020-08-08T15:36:22+00:00

Il ne reste en fait qu'à programmer la fonction donnée en solution de l'exercice 1 de la partie TD.

2020_td-tp_flo

Anonymous (anonymous@undisclosed.example.com) — 2020-10-01T12:03:42+00:00

TD-TP sur les Flots Ce "TD-TP" est, comme son nom l'indique, constitué une partie TD à faire sur papier & d'une partie TP à faire sur machine. Il n'est pas nécessaire de faire tout le TD avant d'attaquer le TP, néanmoins, avant de programmer un algorithme, il faut l'écrire à la main.$G=(V,A)$$u$$c_u$$u$$\Phi = (\phi_u, u\in A)$$\Phi$$\forall u \in A, 0\leq \phi_u \leq c_u$$\Phi$$\forall v \in V, \sum_{u \in \Gamma^+(v)}{\phi_u} = \sum_{u \in \Gamma^-(v)}{\phi_u}$$\Gamma^+(v)$$v$$v'$$v$$\Gamma…

2023_texte

Anonymous (anonymous@undisclosed.example.com) — 2023-11-27T11:31:23+00:00

* TD énoncé * TD correction * TP énoncé * TP correction

2023-td-texte-corr

Anonymous (anonymous@undisclosed.example.com) — 2023-12-01T08:49:32+00:00

Exercice 1 : Chercher un mot Soit une chaîne de caractères d de longueur n et un mot t de longueur m

2023-td-texte

Anonymous (anonymous@undisclosed.example.com) — 2023-11-30T13:51:46+00:00

Algorithmes sur les textes Exercice 1 : Chercher un mot Soit une chaîne de caractères d de longueur n et un mot t de longueur m

2023-tp-texte-corr

Anonymous (anonymous@undisclosed.example.com) — 2023-12-04T08:47:30+00:00

Arbre de complétion Un algorithme de complétion est un mécanisme logique permettant d'anticiper la saisie et de proposer des mots automatiquement pour faciliter les recherches dans un formulaire sur une page web par exemple. On utilise pour cela une structure de données arborescente, où chaque nœud de l'arbre est une étape de lecture et chaque arête correspond à la lecture d'une lettre. Les nœuds sont indexés par les lettres suivantes possibles du mot, avec un compteur par nœud pour savoir si …

2023-tp-texte

Anonymous (anonymous@undisclosed.example.com) — 2024-12-03T22:53:42+00:00

Arbre lexicographique Un algorithme de complétion est un mécanisme logique permettant d'anticiper la saisie et de proposer des mots automatiquement pour faciliter les recherches dans un formulaire sur une page web par exemple. On utilise pour cela une structure de données arborescente, où chaque nœud de l'arbre est une étape de lecture et chaque arête correspond à la lecture d'une lettre. Les nœuds sont indexés par les lettres suivantes possibles du mot, avec un compteur par nœud pour savoir s…

2024_cm_modeles

Anonymous (anonymous@undisclosed.example.com) — 2024-12-20T07:58:55+00:00

Données et modélisation 1. Données persistantes * Il s'agit par définition des informations qui doivent être conservées entre deux exécutions. * Avec l’augmentation des capacités de stockage et leur mise en réseau, les quantités de données conservées ont considérablement augmenté au cours des dernières décennies. $R$$$ t = (a_1, ..., a_m) $$$d$$k(d)$$d_1$$d_2$$d_1 = d_2$$k(d_1)=k(d_2)$$k(d_1) = k(d_2)$$d_1=d_2$$L$$|k| << |d|$$|L| << |D|$$2^{4 \times 8} \simeq 4\times10^9$$d$$I$$k$$i$$I…

cm-todo

Anonymous (anonymous@undisclosed.example.com) — 2019-11-27T15:07:31+00:00

cm

Anonymous (anonymous@undisclosed.example.com) — 2024-06-28T13:18:11+00:00

CM 1. Complexité(s) TODO * Complexité : * Définition. intérêt. * Complexité dans le cas le pire, le meilleur * Complexité des algos récursifs (exemples : factorielle, coefficients binomiaux, tri par fusion) * Complexité en moyenne (exemple du tri par insertion (simple) & de quicksort (un peu plus dur))$O(m \times k)$$\Sigma$$\Sigma$$\Sigma$$S$$A : S \times \Sigma \rightarrow S \times \Sigma'$$s_0 \in S$$\Sigma = \{0, 1\}²$$\Sigma' = \{0, 1\}$$S = \{1, 2\}$$s_0 = 1$$ab$$\Sigma …

cm1

Anonymous (anonymous@undisclosed.example.com) — 2018-11-26T17:03:44+00:00

1 - Cours, Magistral, n°1 : Bonjour complexité·s ! * Complexité : * Définition. intérêt. * Complexité dans le cas le pire, le meilleur * Complexité des algos récursifs (exemples : factorielle, coefficients binomiaux, tri par fusion)

cm2

Anonymous (anonymous@undisclosed.example.com) — 2018-11-19T22:17:41+00:00

CM2 : Données et fichiers Les données numériques sont une des composantes essentielles des programmes informatiques. * Il s'agit par définition des informations qui doivent être conservées entre deux exécutions. * Avec l’augmentation des capacités de stockage et leur mise en réseau, les quantités de données conservées ont considérablement augmenté au cours des dernières décennies. $$ t = (a_1, ..., a_m) $$

cm3

Anonymous (anonymous@undisclosed.example.com) — 2019-11-20T11:22:32+00:00

CM3 : Données non structurées 3. Données non structurées TBD * chaine de caractères * fichiers textes (stockage, utf8, lecture et ecriture) * expressions régulières 3.1 Données texte 3.1.1 Codage des caractères x = 'a' * x une variable de type caractère$O(m \times k)$

cm4

Anonymous (anonymous@undisclosed.example.com) — 2018-11-26T17:04:26+00:00

Cours, Magistral, n°4 : graphes les transparents

cm5

Anonymous (anonymous@undisclosed.example.com) — 2024-06-28T13:18:11+00:00

CM5 : Indexation / Modèle relationnel 5. L'indexation Rappel donnée informatique * Consultable/manipulable/échangeable par des programmes informatiques * Possibilité de la conserver sur un support de stockage numérique (CD-ROM, disque dur, SSD, $d$$k(d)$$d_1$$d_2$$k(d_1) = k(d_2)$$d_1=d_2$$d$$I$$k$$i$$I : k \rightarrow i$$k$$i = I(k)$$d = D[i]$$$L = ((k_1, i_1), (k_2, i_2), ..., (k_N, i_N))$$$k_1 < k_2 < ... < k_N$$L$$|k| << |d|$$|L| << |D|$$2^{4 \times 8} \simeq 4\times10^9$$\mathcal{E}…

cm6

Anonymous (anonymous@undisclosed.example.com) — 2024-06-28T13:18:11+00:00

7 - Bases de données relationnelles en interactionsystème 7.1 Modèle ensembliste Une base de donnée est constituée de plusieurs ensembles d'objets et d'opérateurs participant au bon fonctionnement d'un système: Exemple 1 : * Ensembles d'employés$E_1$$E_k$$E_1 \times ... \times E_k$$\{..., (t_1,…,t_k), …\}$$t_1 \in E_1,…, t_k \in E_k$$k$$[b_\text{inf},b_\text{sup}]$$A$$\mathcal{E}$$$ A : \mathcal{E} \rightarrow D(A) $$$B$$\mathcal{E} \times \mathcal{F}$$$ B : \mathcal{E}\times \mathcal{F}\r…

cm7

Anonymous (anonymous@undisclosed.example.com) — 2018-12-13T07:22:04+00:00

TODO Analyse des données Définitions: * Données aggrégées : données regroupées en classes (clusters), éventuellement organisées de façon hiérarchique. Possibilité d’appartenances à de multiples hiérarchies (cubes de données). * $R$

private_s5-tpa2

Anonymous (anonymous@undisclosed.example.com) — 2020-12-11T10:01:13+00:00

Fonctions de hachage Rappel Soit $E$ un ensemble de messages de taille quelconque. On souhaite indexer ces messages à l'aide d'une fonction d'encodage $H$ qui va de $\mathcal{M}$ (l'ensemble des messages possibles) vers l'intervalle $[0,...,n[$. La fonction de hachage : * "calcule" la valeur de l'identifiant à partir du message de départ. $n$$2^h$$>h$$h$$n = 2^{32} = 4294967296$$n$$n$$n = 2^{32} = 4294967296$$n$$n$$n$$n = 67280421310721$$n$$n$$n = 67280421310721$$n$$n$$m > n$$i$$i+1$$[0, ..…

td1

Anonymous (anonymous@undisclosed.example.com) — 2019-10-02T15:20:36+00:00

TD1 : complexité TBD : PP * listes et complexité ajout/suppression simple * addition * pile/file Enoncé

td2-2018-2019

Anonymous (anonymous@undisclosed.example.com) — 2019-07-31T09:01:04+00:00

TD5 : Tableaux statiques [version imprimable] Exercice 1 On considère un ensemble de k données stockés dans un tableau de données statique T de N cases (avec 0≤k ≤ N). Remarques : * Les cases du tableau sont numérotées de 0 à N-1 * Les données sont de type quelconque mais chaque case ne peut contenir qu'une donnée

td2

Anonymous (anonymous@undisclosed.example.com) — 2019-11-20T12:26:28+00:00

TD6 : Structures de données version imprimable Partie A : Tableaux statiques Exercice 1 On considère un ensemble de k données stockés dans un tableau de données statique T de n cases (avec 0≤k ≤ n). Remarques : * Les cases du tableau sont numérotées de

td3

Anonymous (anonymous@undisclosed.example.com) — 2019-11-14T10:02:26+00:00

TD5 : Algorithmes sur les textes [ Version imprimable] Exercice 1 : Chercher un mot Soit une chaîne de caractères d de longueur n et un mot t de longueur m

td4-2018-2019

Anonymous (anonymous@undisclosed.example.com) — 2019-07-31T09:03:29+00:00

[Le sujet] Partie A $U$clés$E$$h:U\to \{0,\ldots m-1\}$fonction de hachagehashcodetable de hachage$T[0 \ldots m-1]$$T[i]$$x$$E$$h(x)=i$$E$collision Exercice 0 Donnez des algorithmes pour rechercher, insérer & supprimer un élément dans une table de hachage. Donnez leur complexité dans le cas le meilleur, le pire & en moyenne.$m$$n$$h(x) = x \: \mathrm{mod}\: m$$h(k) = E(m\cdot \mathrm{Frac}(x\cdot A))$$A$$[0\ldots1]$$E$$(\mathrm{Frac}(x)=x-E(x))$$m$$A$$x$$h(x)$$y\ne x$$h(y) = h(x)$$E$$E$$T$$T$…

td4

Anonymous (anonymous@undisclosed.example.com) — 2019-07-31T08:51:45+00:00

[Le sujet] Partie A Partie C Exercice 8 Table d'allocation On considère un tableau $T$ de taille $n$ dans lequel * $p

td5

Anonymous (anonymous@undisclosed.example.com) — 2019-10-02T15:19:38+00:00

TD2 : parcours graphes Enoncé

td6

Anonymous (anonymous@undisclosed.example.com) — 2018-11-20T20:20:16+00:00

Enoncé ici

td7-alt

Anonymous (anonymous@undisclosed.example.com) — 2019-04-30T10:44:40+00:00

TD7 : hash TBD : PP * hash * adressage ouvert * du nombre au dictionnaire Indexation pseudo-aléatoire et Hash sets Soit $E$ un ensemble de $n$ messages de taille quelconque. On souhaite indexer ces messages à l'aide d'une fonction d'encodage $H$ qui va de $\mathcal{M}$$[0,...,2^h[$$h$$n$$< 2^h$$m_1$$m_2$$H(m_1) = H(m_2)$$1/2^h$$[0,...,2^h[$$m$$i$$j$$|i-j|=1$$|H(i) - H(j)| >> 1$$2^h$$n$$m$$E$$n$$p < n$$d$$i < n$$m$$n$$$B = \underset{0}{0}{10010100100.....}\underset{n-1}{01}$$$f(B,i)$$B$…

td7

Anonymous (anonymous@undisclosed.example.com) — 2019-10-02T15:18:37+00:00

TD3 : arbre de recherche Énoncé :

td7b

Anonymous (anonymous@undisclosed.example.com) — 2019-11-25T12:27:04+00:00

td8

Anonymous (anonymous@undisclosed.example.com) — 2022-12-12T15:44:54+00:00

TD 7 : Dépendances fonctionnelles Exercice 1 Soient: * L'ensemble d'attributs {A, B, C, D, E} * Les dépendances fonctionnelles : * A --> B, C * D --> E * C, D --> A 1. Montrer, à l'aide des axiomes d'Armstrong, que {A, D} est une clé de ce schéma.

td9

Anonymous (anonymous@undisclosed.example.com) — 2023-01-01T18:16:30+00:00

TD8 : modèle entité/association [Version imprimable] Exercice A. Dessiner les mini-problèmes suivants sous la forme de diagrammes entité/association, en précisant les contraintes de cardinalité. Tous les attributs nécessaires doivent être indiqués sur le schéma. N’oubliez pas de souligner les clés primaires de chaque ensemble d’entités.

td10

Anonymous (anonymous@undisclosed.example.com) — 2021-06-07T13:42:54+00:00

TD Algèbre relationnelle : Recherche d’information Exercice 1 On considère la base de données académique vue au TD9 : * Enseignant(e-mail-ens, nom, prénom, tel,) * UE(code_UE, intitulé, semestre, nb_crédits, e-mail-ens) * Séance(id_séance

tda1

Anonymous (anonymous@undisclosed.example.com) — 2019-11-27T16:14:57+00:00

* [Monolignes] * [ |QCM Algo janvier 2018]

tda2

Anonymous (anonymous@undisclosed.example.com) — 2019-05-13T14:25:31+00:00

L'énoncé

tda3

Anonymous (anonymous@undisclosed.example.com) — 2019-01-15T12:07:06+00:00

TD en autonomie 3 : révisions Exercice 1 : Dépendances fonctionnelles Soit un restaurant. Au cours d’un service, décrit par sa date et son heure, les clients s’installent à des tables, commandent des plats et sont servis par des serveurs. Un plat appartient à une catégorie (entrée, principal, dessert, …). Soient les attributs {date, heure, id_client, id_serveur, num_table, id_plat, catégorie}.

tp1

Anonymous (anonymous@undisclosed.example.com) — 2019-09-19T09:30:53+00:00

Environnement de travail * Tutoriels : * Unix : * [Initiation Unix] * Environnement Unix * Python : * [Python] * Python et son environnement * Java : * Java et son environnement * Coder mieux : * [Les tests unitaires] * Environnements de programmation: * [Installer Python et Pycharm chez soi] * [ Utiliser Pycharm] A savoir * Si tu n'est pas à l'aise en Python:

tp2

Anonymous (anonymous@undisclosed.example.com) — 2020-12-18T10:50:46+00:00

TP6 : Lecture/Ecriture Nous souhaitons dans cet exercice travailler en lecture et en écriture sur un fichier de clients. Soit le fichier [clients.txt] contenant une liste de clients: 2823 Paul Henriot, 59 rue de l'Abbaye, 51100 Reims, France Daniel Da Cunha, 27 rue du Colonel Pierre Avia, 75508 Paris, France Julie Young, 78934 Hillside Dr., 90003 Pa…

tp3

Anonymous (anonymous@undisclosed.example.com) — 2019-11-20T11:15:21+00:00

TP5 : Expressions régulières Le TP sera réalisé en python. La librairie re de python permet d’utiliser les [expressions régulières] pour effectuer de la recherche dans les textes. import re Exercice 1.1 : recherche de motifs La recherche dans un texte nécessite de définir un motif. Ce motif est défini dans une chaîne brute (qui n’interprète pas les caractères spéciaux). Une chaîne brute est préfixée par un

tp4

Anonymous (anonymous@undisclosed.example.com) — 2019-05-01T20:22:50+00:00

TP7 : json/xml/dictionnaires TBD : Manu / Cathy * fichiers [json] * structure dictionnaires / ensemble Exercice 1 : format json et dictionnaires Le format json - JavaScript Object Notation ... * Il obéit au format texte (donc éditable dans un éditeur de textes)

tp5

Anonymous (anonymous@undisclosed.example.com) — 2019-02-14T14:25:03+00:00

TP2 S'habiller le matin. Un ensemble de contraintes possibles : Le but de ce TP est de résoudre ce problème en proposant un ordre d'habillage possible. Préparatifs Un début * Ajoutez au graphe un sommet de départ, voisin de tout les sommets du graphe sur lesquels aucun autre sommet ne pointe$i$$i$

tp6

Anonymous (anonymous@undisclosed.example.com) — 2019-09-28T14:34:01+00:00

TP4 Le but de ce TP est d'appliquer la théorie des flots dans les graphes à des problèmes concrets. encore & toujours Les graphes seront représentés "mathématiquement" par des listes d'adjacence, & plus précisément/concrètement par des dictionnaires de dictionnaires de dictionnaires. Par exemple :

tp7_old

Anonymous (anonymous@undisclosed.example.com) — 2019-09-28T14:17:15+00:00

tp7

Anonymous (anonymous@undisclosed.example.com) — 2019-09-28T14:17:47+00:00

Arbre Binaire de Recherche (ABR) Un arbre binaire est ici défini comme suit : * un arbre vide correspond à la valeur None * La racine d'un arbre non vide est une liste constituée de 3 éléments * la valeur * la racine du sous-arbre gauche

tp7b

Anonymous (anonymous@undisclosed.example.com) — 2019-11-28T08:38:27+00:00

TP7 : deques/tri par paquets/ Fibonacci EXO1 Afin de manipuler correctement les deques il est demandé de programmer les différentes fonctions vues en TD dans l'exos sur les TODO listes. 1) Base de travail Ecrire les fonctions de base de cette structure de données.

tp8

Anonymous (anonymous@undisclosed.example.com) — 2018-12-18T08:18:29+00:00

Travaux Pratiques, huitième séance Le TP sera réalisé en Python. 1. Introduction On considère une série d’enregistrements concernant des ventes réalisées par un exportateur de véhicules miniatures. Pour chaque vente, il entre dans son registre de nombreuses informations :

tp9

Anonymous (anonymous@undisclosed.example.com) — 2019-05-27T19:37:10+00:00

TP 9 : SQL Nous allons travailler sur une base de données biblio décrivant des emprunts de livres au sein d'un réseau de bibliothèques. Le schéma relationnel de la base est le suivant : * Membre (IdMembre, nomMembre, adrMembre, cpMembre) *

tp10

Anonymous (anonymous@undisclosed.example.com) — 2019-01-17T08:31:35+00:00

TP 10 : Persistance des données De nombreux programmes utilisent des données situées sur une base de données séparée du programme lui-même. Le programme qui effectue les requêtes est appelé le “client”, le programme qui répond aux requêtes est le “serveur”. Le serveur est en général situé sur une machine distante, accessible par son adresse IP. Ici, pour des raisons de simplicité, nous travaillerons sur une base locale gérée par le programme sqlite.

tpa1

Anonymous (anonymous@undisclosed.example.com) — 2019-12-09T15:49:56+00:00

TPA2 : Tic tac toe Le but de ce TP en autonomie est programmer le jeu du Tic tac toe : un joueur contre l'ordinateur. * tout d'abord : les fonctions de base * puis la stratégie et les fonctions associées * le programme principal Le jeu est représenté dans le programme par une liste de 10 ' '. Les neuf cases du jeu se trouvent aux indices de 1 à 9, l'indice 0 ne sert pas.

tpa2

Anonymous (anonymous@undisclosed.example.com) — 2019-10-22T10:53:07+00:00

TP en autonomie Le sujet But du TP On vous demande ici de programmer avec plein de petites fonctions qui effectuent une tâche unique dont le nom permet de comprendre la fonction. On essayera ainsi de décomposer les algorithmes en tâches que l'on pense insécables.$\mathcal{O}(n^2)$$\mathcal{O}(n \log((n))$

tpa3

Anonymous (anonymous@undisclosed.example.com) — 2019-11-29T13:32:29+00:00

TP4 : analyse de données avec Pandas TBD : Manu / Ronan * lecture / ecriture dans fichier plat et fichier csv * lecture sequentielle / flux de données * extraction / mise en forme / tableaux pandas Installation et importation de modules Les notebooks Jupyter

truc

Anonymous (anonymous@undisclosed.example.com) — 2018-05-14T07:57:25+00:00

test