Welcome to TiddlyWiki created by Jeremy Ruston, Copyright © 2007 UnaMesa Association
Cours: [[Algorithmique Avancée et Complexité|http://www.fil.univ-lille1.fr/portail/index.php?dipl=M1&sem=S7&ue=AAC&choix=pres]] (semestre septembre-févier 2008)
Responsable du cours: [[Sophie Tison|mailto:Sophie.Tison@lifl.fr]]
Quoi, Quand, et Où:
*TP, le mercredi 15h45 - 17h15, ~M5-A6
*TD, le jeudi 10h - 12h, ~M5-A12
[img[img/rss-icon.png][http://www.grappa.univ-lille3.fr/~staworko/AaC08.xml]] Le flux RSS a été déactivé après la fin du cours et il n'est plus disponible.
Quelques matériels:
# Solutions de quelques questions TD 1 ([[pdf|teaching/aac08/rec01.pdf]]).
# Sources Java et un testeur pour [[Distance d'édition]] sont disponibles. //(la dernière mise à jour le 16 octobre, 2008)//
# [[Big Numbers]] en Java. Analyse de la complexité logarithmique de quelques opérations arithmétiques.
# Implémentation d'[[Exercice 7|teaching/aac08/Bag.cs]] de TD 1 en C#.
# [[Transformée de Fourier Rapide]] implémentée en C# en plusieurs versions.
# Corrigé de [[DS|http://www.fil.univ-lille1.fr/~tison/AAC/Cours/DScor.pdf]] (Sophie Tison).
# Corrigé d'[[Exercice 4|http://www.fil.univ-lille1.fr/~tison/AAC/td/td3exo4cor.pdf]] de TD 3 (Sophie Tison).
# Corrigé d'[[Exercice 3|http://www.fil.univ-lille1.fr/~tison/AAC/td2008/td6ex3c.pdf]] et [[Exercice 4|http://www.fil.univ-lille1.fr/~tison/AAC/td2008/td6ex4c.pdf]] de TD 6 (~Marie-Emillie Voge et Sophie Tison).
''Dates limites importantes'':
# 22/10/2008 -- devoir maison facultatif: faire x ($0\leq x\leq 3$) exercices parmi les trois derniers de [[TD1|http://www.fil.univ-lille1.fr/~tison/AAC/td2008/td1.pdf]]. (à retourner pendant TD)
# 8:00AM 24/10/2008 -- vos solutions de [[TP1|http://www.fil.univ-lille1.fr/~tison/AAC/td2008/td1.pdf]] (à retourner en utilisant PROF)
# 8:00AM 20/12/2008 -- vos solutions de ~TP2: [[partie 1|http://www.fil.univ-lille1.fr/~tison/AAC/tp2008/TP2-1.pdf]] et [[partie 2|http://www.fil.univ-lille1.fr/~tison/AAC/tp2008/TP2-2.pdf]]. (à retourner en utilisant PROF)
<!--{{{-->
<div class='toolbar' macro='toolbar [[ToolbarCommands::EditToolbar]]'></div>
<div class='title' macro='view title'></div>
<div class='editor' macro='edit title'></div>
<div macro='annotations'></div>
<div class='editor' macro='edit text'></div>
<div class='editor' macro='edit tags'></div>
<div class='editorFooter'>
<span macro='message views.editor.tagPrompt'></span>
<span macro='tagChooser'></span>
</div>
<!--}}}-->
Your username for signing your edits:
<<option txtUserName>>
<<option chkSaveBackups>> Save backups
<<option chkAutoSave>> Auto-save
<<option chkRegExpSearch>> Regular expressions search
<<option chkCaseSensitiveSearch>> Case sensitive search
<<option chkAnimate>> Enable animations
<<option chkSinglePageMode>> Single page mode
<<option chkFilterPublicTagsSearch>> Filter public tags in search results
<<option chkInsertTabs>> Insert Tab characters
<<option chkUnixFileSystem>> Unix file system
----
Also see AdvancedOptions
<!--{{{-->
<div class='header' macro='gradient vert [[ColorPalette::PrimaryLight]] [[ColorPalette::PrimaryMid]]'>
<div class='headerShadow'>
<span class='siteTitle' refresh='content' tiddler='SiteTitle'></span>
<span class='siteSubtitle' refresh='content' tiddler='SiteSubtitle'></span>
</div>
<div class='headerForeground'>
<span class='siteTitle' refresh='content' tiddler='SiteTitle'></span>
<span class='siteSubtitle' refresh='content' tiddler='SiteSubtitle'></span>
</div>
</div>
<div id='mainMenu' refresh='content' tiddler='MainMenu'></div>
<div id='sidebar'>
<div id='sidebarOptions' refresh='content' tiddler='Author.SideBarOptions'></div>
<div id='sidebarTabs' refresh='macro' force='true' macro='slider chkSideBarTabs Author.SideBarTabs "index »" "display lists of tiddlers"'></div>
</div>
<div id='displayArea'>
<div id='messageArea'></div>
<div id='tiddlerDisplay'></div>
</div>
<!--}}}-->
<<search>><<closeAll>><<permaview>><<newTiddler>><<saveChanges>><<slider chkSliderOptionsPanel Author.OptionsPanel "options »" "Change TiddlyWiki advanced options">>
<<tabs txtMainTab "Main" "Principal index" Index.All "Timeline" "Timeline" TabTimeline "All" "All tiddlers" TabAll "Tags" "All tags" TabTags "More" "More lists" TabMore>>
<!--{{{-->
<div class='toolbar' macro='toolbar [[ToolbarCommands::ViewToolbar]]'></div>
<div class='title' macro='view title'></div>
<div class='tagged' macro='tags'></div>
<div class='viewer' macro='view text wikified'></div>
<div class='tagClear'></div>
<!--}}}-->
!LLNST10
{{{
@inproceedings{LLNST10,
Author = {Laurence, G. and Lemay, A. and Niehren, J. and Staworko, S. and Tommasi M.},
Title = {Linear Top-Down Tree-to-Word Transducers: Characterization and Minimization},
Booktitle = {Rewriting Techniques and Applications (RTA)},
Year = {2010},
Month = {July},
Publisher = {LIPIcs}}
}}}
!StBoGr10
{{{
@inproceedings{StBoGr10,
Author = {Staworko, S. and Boneva, I. and Groz, B.},
Title = {The View Update Problem for XML},
Booktitle = {EDBT Workshops (Updates in XML)},
Year = {2010},
Month = {March},
Publisher = {ACM}}
}}}
!StChMa09
{{{
@article{StChMa09,
Author = {Staworko, S. and Chomicki, J. and Marcinkowski, J.},
Journal = {Annals of Mathematics and Artificial Intelligence},
Note = {Submitted.},
Title = {Prioritized Repairing and Consistent Query Answering in Relational Databases}}
}}}
!ChMaSt04b
{{{
@inproceedings{ChMaSt04b,
Author = {Chomicki, J. and Marcinkowski, J. and Staworko, S.},
Booktitle = {International Conference on Information and Knowledge Management (CIKM)},
Month = {November},
Pages = {417-426},
Publisher = {ACM Press},
Title = {Computing Consistent Query Answers Using Conflict Hypergraphs},
Year = {2004}}
}}}
!StCh10
{{{
@article{StCh10,
Author = {Staworko, S. and Chomicki, J.},
Journal = {Information Systems},
Number = {1},
Pages = {1-22},
Title = {Consistent Query Answers in the Presence of Universal Constraints},
Volume = {35},
Year = {2010}}
}}}
!Staworko07
{{{
@phdthesis{Staworko07,
Author = {Staworko, S.},
School = {State University of New York at Buffalo},
Title = {Declarative Inconsistencies Handling in Relational and Semi-structured Databases},
Year = {2007}}
}}}
!ChMaSt04a
{{{
@inproceedings{ChMaSt04a,
Author = {Chomicki, J. and Marcinkowski, J. and Staworko, S.},
Booktitle = {International Conference on Extending Database Technology (EDBT)},
Month = {March},
Note = {System demo.},
Pages = {841-844},
Publisher = {Springer LNCS 2992},
Title = {Hippo: A System for Computing Consistent Answers to a Class of {SQL} Queries},
Year = {2004}}
}}}
!StChMa06
{{{
@inproceedings{StChMa06,
Author = {Staworko, S. and Chomicki, J. and Marcinkowski, J.},
Booktitle = {EDBT Workshops (IIDB)},
Pages = {318-335},
Publisher = {Springer LNCS 4254},
Title = {Preference-Driven Querying of Inconsistent Relational Databases},
Year = {2006}}
}}}
!StCh05
{{{
@techreport{StCh05,
Author = {Staworko, S. and Chomicki, J.},
Institution = {arXiv.org e-Print archive},
Month = {June},
Number = {cs.DB/0506063},
Title = {Priority-Based Conflict Resolution in Inconsistent Relational Databases},
Type = {Technical Report},
Year = {2005}}
}}}
!StFiCh08
{{{
@inproceedings{StFiCh08,
Author = {Staworko, S. and Filiot, E. and Chomicki, J.},
Booktitle = {International Workshop on Logic in Databases (LiD)},
Title = {Querying Regular Sets of {XML} Documents},
Year = {2008}}
}}}
!StCh06
{{{
@inproceedings{StCh06,
Author = {Staworko, S. and Chomicki, J.},
Booktitle = {EDBT Workshops (dataX)},
Pages = {164-177},
Publisher = {Springer LNCS 4254},
Title = {Validity-Sensitive Querying of {XML} Databases},
Year = {2006}}
}}}
!GSCRT09
{{{
@inproceedings{GSCRT09,
Author = {Groz, B. and Staworko, S. and Caron, A.-C. and Roos, Y. and Tison, S.},
Booktitle = {International Symposium on Database Programming Languages (DBPL)},
Month = {August},
Publisher = {Springer LNCS 5708},
Title = {{XML} Security Views Revisited},
Year = {2009}}
}}}
!SLLN09
{{{
@inproceedings{SLLN09,
Author = {Staworko, S. and Laurence, G. and Lemay, A. and Niehren, J.},
Booktitle = {International Symposium on Fundamentals of Computation Theory (FCT)},
Month = {August},
Pages={310-322},
Publisher = {Springer LNCS 5699},
Title = {Equivalence of Deterministic Nested Word to Word Transducers},
Year = {2009},
}
}}}
Je vais présenter une implémentation de quelques simples opérations arithmétiques sur la représentation binaire de nombres entiers. Vous pouvez télécharger le //[[code source|teaching/aac08/BigNumbers.java]]// et expérimenter.
D'abord nous allons définir la structure qui permettra de stocker la représentation binaire d'un nombre.
{{{
class big
{
int[] t = new int[100];
int size = 0;
}
}}}
La table {{{t}}} sera utilisée pour stocker les bits du nombre et {{{size}}} indiquera //la taille// de ce nombre, i.e. le nombre de cellules (bites) qui sont utilisées. Remarquez qu'ici la taille d'un nombre est différente de la longueur de {{{t}}}. Pour simplicité, nous allons travailler avec des tables d'une longueur fixe en supposant que ça va aller. Ça nous permettra d'éviter beaucoup de détail techniques. Pour avoir une vraie représentation, il faudrait changer dynamiquement la longueur de {{{t}}}.
La façon de représentation d'un nombre avec {{{big}}} est illustrée dans l'exemple suivant.
''Exemple''. Le nombre {{{13 = 1*8 + 1*4 + 0*2 + 1*1}}} est représenté avec {{{ t={1,0,1,1} }}} et le nombre de cellules utilisées est {{{size=4}}}. Plus précisément, {{{t[0]=1, t[1]=0, t[2]=1, t[3]=1}}}. Observez qu'une nouvelle instance de {{{big}}} est initialisée avec le valeur {{{0}}} (i.e. {{{size=0}}}).
Nous allons utiliser deux constantes {{{ZERO}}} et {{{ONE}}} qui représentent des nombres {{{0}}} et {{{1}}} respectivement.
Deux grands nombres sont inégal si leur taille est différente ou s'ils sont pas égaux à un des bits. Ça nous donne une simple procédure pour tester l'égalité de deux nombres:
{{{
boolean equal(big a, big b)
{
if (a.size != b.size)
return false;
for (int i = 0; i < a.size; i++) {
if (a.t[i] != b.t[i])
return false;
}
return true;
}
}}}
''Complexité'': linéaire, i.e. //O(a.size)//.
L'addition est effectuée bit par bit. A chaque fois il faut garder le surplus ({{{carry}}}) et l'ajouter à l'opération sur le bit suivant. ''Rappel'': en Java pour deux entiers {{{x}}} et {{{y}}}, la division est effectuée avec {{{x/y}}} et le reste de division avec {{{x%y}}}.
{{{
big add(big a, big b)
{
big c = ZERO;
int carry = 0;
int i = 0;
while (i < max(a.size,b.size) || carry == 1) {
c.t[i] = (a.t[i] + b.t[i] + carry) % 2;
carry = (a.t[i] + b.t[i] + carry) / 2;
i++;
}
c.size = i;
return c;
}
}}}
''Complexité'': linéaire, i.e. //O(a.size+b.size)//
''Taille de la sortie'': //~max(a.size,b.size)//
L'opération de décalage à gauche d'un nombre {{{a}}} par {{{s}}} bits est simple.
{{{
big shift(big a, int s)
{
big b = new big();
for (int i = 0; i < a.size; i++)
b.t[i+s] = a.t[i];
b.size = a.size+s;
return b;
}
}}}
''Complexité'': linéaire, i.e //O(size)//
''Taille de la sortie'': //a.size+s//
Et maintenant, la multiplication avec la méthode de l'école.
{{{
big mult(big a, big b)
{
big c = new big();
for (int i = 0; i < b.size; i++) {
if (b.t[i] == 1)
c = add(c,a);
a = shift(a,1);
}
return c;
}
}}}
''Complexité'': //O(a.size*b.size)//
''Taile de la sortie'': //~a.size+b.size//
L'exponentiation naïve est faite comme ça:
{{{
big exp(big a, int k)
{
big b = ONE;
for (int i = 0; i < k; i++) {
b = mult(b,a);
}
return b;
}
}}}
''Complexité'': Nous allons poursuivre l'exécution de cette procédure en notant le temps de multiplication {{{mult(b,a)}}} et la taille de {{{b}}} en chaque l'itération de la boucle {{{for}}}. C'est parti...
|{{{i}}}|{{{mult(b,a)}}}|{{{b.size}}}|
|-1 | - | 1|
| 1 | a.size | a.size |
| 2 | a.size^2 | 2*a.size |
| 3 | 2*a.size^2 | 3*a.size |
| 4 | 3*a.size^2 | 4*a.size |
| ... | ... | ... |
| i | (i-1)*a.size^2 | i*a.size |
| ... | ... | ... |
| k | (k-1) *a.size^2 | k*a.size |
En somme, le temps est égal à //a.size+(1+2+...+(k-1))*a.size^2=O(k^2*a.size^2)//
''La taille de la sortie'': Évidement, //~k*a.size//
Par contre, on peut utiliser //la méthode de monoïde// pour calculer l'exponentiation plus vite:
{{{
big exp-fast(big a, int k)
{
if (k < 0)
throw IllegalArgumentException("Hmmm...");
if (k == 0)
return ONE;
if (k == 1)
return a;
big b = exp-fast(a,k/2);
big c = mult(b,b);
if ( k%2 == 0)
return c;
else
return mult(c,a);
}
}}}
L'analyse de complexité //est votre devoir//.
Background: #eef
Foreground: #000
PrimaryPale: #8cf
PrimaryLight: #18f
PrimaryMid: #04b
PrimaryDark: #014
SecondaryPale: #ffc
SecondaryLight: #fe8
SecondaryMid: #db4
SecondaryDark: #841
TertiaryPale: #eee
TertiaryLight: #ccc
TertiaryMid: #999
TertiaryDark: #666
Error: #f88
PageTemplate
|>|>|SiteTitle - SiteSubtitle|
|MainMenu|DefaultTiddlers<br><br><br><br>ViewTemplate<br><br>EditTemplate|SideBarOptions|
|~|~|OptionsPanel|
|~|~|AdvancedOptions|
|~|~|<<tiddler Configuration.SideBarTabs>>|
''StyleSheet:'' StyleSheetColors - StyleSheetLayout - StyleSheetPrint
SiteUrl
SideBarTabs
|[[Timeline|TabTimeline]]|[[All|TabAll]]|[[Tags|TabTags]]|>|>|[[More|TabMore]] |
|>|>||[[Missing|TabMoreMissing]]|[[Orphans|TabMoreOrphans]]|[[Shadowed|TabMoreShadowed]]|
!!!!Email
[[slawomir.staworko@inria.fr|mailto:slawomir.staworko@inria.fr]]
!!!!INRIA Lille - Nord Europe
INRIA Lille - Nord Europe ([[map|http://maps.google.com/maps/ms?ie=UTF8&hl=en&msa=0&msid=108140276224441622275.00047a9e96d8bf5f6fb5f&ll=50.605943,3.144064&spn=0.009655,0.017467&t=h&z=16]])
Parc Scientifique de la Haute Borne
Park Plaza - Bât A - 40 avenue Halley
59650 Villeneuve d'Ascq
FRANCE
Office: 117
Phone: (33 | 0) 3.59.57.79.22
Fax: (33 | 0) 3.59.57.78.50
!!!!Université ~Charles-de-Gaulle Lille 3
U.F.R. IDIST
Université de Charles de Gaulle - Lille 3
59653 Villeneuve d'Ascq CEDEX
FRANCE
Office: INRIA research suite, Building M (Modulaire M) ([[map|http://maps.google.com/maps/ms?ie=UTF8&hl=en&msa=0&msid=108140276224441622275.00047a9ea4fa4b8afadab&t=h&z=17]])
Phone: (33 | 0) 3.20.41.61.79
Fax: (33|0) 3.20.41.61.71
This material is presented to ensure timely dissemination of scholarly and technical work. Copyrights and all rights therein are retained by authors or by other copyright holders. All persons copying this material are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works cannot be reposted or commercially distributed without the explicit permission of the copyright holder.
''ACM COPYRIGHT NOTICE'':
Copyright © 199x by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted.
Le matériel disponible:
* un archive avec des sources Java à remplir: [[zip|teaching/aac08/tp1.zip]] ou [[tar.gz|teaching/aac08/tp1.tar.gz]]
* une classe Java qui permet de tester vos solutions: [[testeur|teaching/aac08/TesterTP1.class]] //(la dernière mise à jour 16 octobre)//
Utilisation de Testeur:
# Téléchargez et sauvegardez le [[testeur|teaching/aac08/TesterTP1.class]] dans le même répertoire que les fichiers Java avec votre solution.
# Remplissez les fichier avec votre code. Il n'est pas nécessaire de résoudre tous les problèmes pour tester. Seulement les solutions qui réussissent à compiler seront testées. ''Quelques remarques importantes:''
#*Ne définissiez pas de constructeurs dans vos //solvers//. Si vous en avez besoin, définissez aussi le constructeur //default// (prenant zéro paramètres). Le constructeur //default// est utilisé par le testeur pour créer les instance de vos //solvers//.
#*Ne mettez pas vos solutions dans un package dédié. Le testeur va essayer de charger que des //solvers// qui appartiennent au package //default//, i.e. les solvers qui n'utilisent pas le mot clé {{{package}}}. Pourtant, il est possible de tester des //solvers// appartenants à d'autres packages en utilisant les paramètres de testeur.
# Compilez les fichiers Java avec {{{javac *.java}}}
# Si vous voulez tester vos solutions avec grandes données, supprimez {{{SolverNaifRec.class}}}. Sinon, seulement le test avec des données jouets {{{"abcbab"}}} et {{{"acbbb"}}} sera effectué. (Utile pour trouver des bugs)
# Faites exécuter le testeur avec {{{java TesterTP1}}}
# Le testeur génère aléatoirement deux chaînes de la taille ~1000 et dont la distance est ~50. (Seulement si la class {{{SolverNaifRec}}} n'est pas présente)
# Puis chaque de vos //solvers// est testé et le résultat est affiché sur la console. Le testeur dit si le //solver// a réussi à bien calculer la distance, pendant combien de temps et en utilisant combien de mémoire. La consommation de mémoire est calculée avec des méthodes standards de Java et alors le résultat est presque toujours absurde.
# Pour référence, les chaînes sont sauvegarder dans le répertoire curant sur les noms {{{u.txt}}} et {{{v.txt}}}. Vos //solvers// ne doivent pas essayer d'accéder ces fichiers. Pour les voir sans les bloquer, utilisez les commandes {{{cat u.txt}}} et {{{cat v.txt}}}.
# Quelques remarques (options avancées):
#*Le testeur essaie de tester toutes les classes (dans le répertoire curant) qui implémentent l'interface {{{Solver}}}. Pour ça, le tester utilise le chargeur de classes standard. Remarquez qu'il n'est pas nécessaire que tous vos //solvers// aient été bien compilés.
#*Pour démarrer, le testeur a besoin des fichiers {{{Solver.class}}} et {{{PbDiff.class}}}. Vérifiez que les fichiers {{{Solver.java}}} et {{{PbDiff.class}}} ont bien compilé.
#*Le fonctionnement de testeur peut être configure avec paramètres. Des paramètres suivants sont acceptés:
#** {{{--string-size=n}}} La taille des chaînes à générer (par défaut: //1000//)
#** {{{--string-dist=n}}} La distance entre les deux chaînes (par défaut: //50//)
#** {{{--write-data=b}}} Écrire des données (par défaut: //true//)
#** {{{--u-file-name=str}}} Le nom de fichier pour la première chaîne (par défaut: //u.txt//)
#** {{{--v-file-name=str}}} Le nom de fichier pour la deuxième chaîne (par défaut: //v.txt//)
#** {{{--ignore-solver=str}}} Le nom de //solver// à ignorer; Utilisez plusieurs fois pour ignorer de multiple //solvers//
#** {{{--only-solver=str}}} Tester uniquement le //solver// donné; Utilisez plusieurs fois pour spécifier de multiple //solvers//
#** {{{--toy-data=b}}} Utiliser des données jouets (par défaut: //false//); des données jouets seront toujours utilisées si //~SolverRecNaif// est présent
#** {{{--toy-data-u=str}}} La première chaîne jouet (par défaut: //abcbab//)
#** {{{--toy-data-v=str}}} La deuxiéme chaîne jouet (par défaut: //acbbb//)
#** {{{--quiet=b}}} Supprimer des messages (sauf erreurs) (par défaut: //false//)
#** {{{--verbose=b}}} Afficher des valeurs de paramètres (par défaut: //false//)
#** {{{--help}}} Imprimer la liste de paramètres acceptés.
#* Exemples d'utilisation:
#** {{{java TesterTP1}}}<br>Tester tous les //solvers//. Si //~SolverNaifRec// est present, données jouets sont utilisées; sinon le testeur génère de grandes données.
#** {{{java TesterTP1 --ignore-solver=SolverNaifRec --ignore-solver=SolverDynRec}}}<br>Tester tous les //solvers// sauf ~SolverNaifRec et ~SolverDynRec
#** {{{java TesterTP1 --only-solver=SolverDynRec --only-solver=SolverDynIter}}}<br>Tester seulement sur ~SolverDynRec et ~SolverDynIter
#** {{{java TesterTP1 --toy-data=true --toy-data-u=abba --toy-data-v=aabab}}}<br>Tester tous les //solvers// en utilisant les chaînes "abba" et "abab"
#** {{{java TesterTP1 --string-size=100 --string-dist=10}}}<br>Tester tous les //solvers//. La première chaîne est générée aléatoirement et compris 100 caractères. La deuxième chaîne est une copie de la première déformée avec 10 opération d'édition (insertion, délétion et modification)
#N'hésitez pas à me contacter (par email) s'il y a des problèmes avec le testeur.
#Le [[code source|teaching/aac08/TesterTP1.java]] de Testeur est disponible (la partie qui calcule la distance a été supprimée).
* 2009-2010, 2e semestre
** CM/TD [[Structuration de l'information|SQL10]] (Master ICD)
** TD [[Technologie du Web|http://grappa.univ-lille3.fr/~gonzalez/enseignement/2009-2010/technoweb/]] (License MIASHS)
* 2009-2010, 1er semestre
** CM/TD [[Information et Langage Informatique|ILI09]] (Master ICD)
** TD [[Bases de Données|http://grappa.univ-lille3.fr/~gonzalez/enseignement/2009-2010/bd/]] (License MIASHS)
* 2008-2009, 1er semestre
** TP/TD [[Algorithmique Avancée et Complexité|AaC08]] (Master 1)
¤ Alfred Tarski (1924)
¤ ¤ Andrzej Mostowski (1938)
¤ ¤ ¤ [[Wiktor Marek|http://www.cs.engr.uky.edu/~marek]] (1968)
¤ ¤ ¤ ¤ Witold Lipski, Jr. (1974)
¤ ¤ ¤ ¤ ¤ [[Tomasz Imielinski|http://www.cs.rutgers.edu/~imielins]] (1981)
¤ ¤ ¤ ¤ ¤ ¤ [[Jan Chomicki|http://www.cse.buffalo.edu/~chomicki]] (1990)
¤ ¤ ¤ ¤ ¤ ¤ ¤ Sławek Staworko (2007)
[>img[img/staworko-face-by-mfalski.jpg]]I'm an Assistant Professor at the [[University of Lille 3|http://www.univ-lille3.fr/fr/]] and a member of the [[INRIA Lille - Nord Europe|http://www.inria.fr/lille]] project [[Mostrare|http://mostrare.lille.inria.fr]]. My current research topics include //Machine Learning of XML Transformations//, //Security of XML Databases//, and //Consistency Management and Database Repairing//.
Currently, I participate in two INRIA collaboration projects: [[Enumeration|https://gforge.inria.fr/plugins/wiki/index.php?EnumerationProject&id=267&type=g]] and [[Access|http://acxml.gforge.inria.fr/index.php]]
----
//Nothing in life is to be feared, it is only to be understood.
Now is the time to understand more, so that we may fear less.//
Marie Skłodowska-Curie
1867-1934, ~Polish-French chemist & physicist
Cours: ''Information et Langage Informatique''
Responsable du cours: Slawek Staworko
Contenu du cours:
# L'informatique et l'ordinateur
# Les donnée et le codage de texte
# Le document éléctronique et sa structirization
# Le revue des format du document structuré
# Le Web (et l'Internet)
# La programmation
Examen:
* le 4 Novembre 2009
* [[Corrigé|teaching/ili09/exam1-corrige.pdf]]
Devoir Maison:
# [[Votre site web et CV|teaching/ili09/dm1.pdf]] ([[2e session|teaching/ili09/dm1-2e-session.pdf]])
# [[Programmation Robot|teaching/ili09/dm2.pdf]] ([[2e session|teaching/ili09/dm2-2e-session.pdf]])
Projet Document Electronique:
* [[Descriptif|teaching/ili09/projet.pdf]] ([[2e session|teaching/ili09/projet-2e-session.pdf]])
* Exemple (presque complet)
** [[Livre de cuisine|teaching/ili09/cuisinage-projet.zip]]
TD:
# [[Premiers pas en Linux|teaching/ili09/td1.pdf]] ([[tex|teaching/ili09/td1.tex]])
#* Fichier pour l'exercice 3 ([[aleatoire.txt|teaching/ili09/aleatoire.txt]])
#* [[Corrigé|teaching/ili09/td1-corrige.pdf]] ([[tex|teaching/ili09/td1-corrige.tex]])
#* [[Ubuntu|http://www.ubuntu.com/]] ([[version francaise|http://www.ubuntu-fr.org/]])
#**[[Instalation d'Ubuntu sur une clé USB|https://wiki.ubuntu.com/LiveUsbPendrivePersistent]] (en anglais)
# [[Introduction à LaTeX|teaching/ili09/td2.pdf]]
#* [[LaTeX en 84 minutes|teaching/ili09/flshort-3.20.pdf]] (en français, 109 pages)
#* [[Aide-memoire|teaching/ili09/latexsheet.pdf]] (en anglais, 2 pages)
# [[Langages de document Web|teaching/ili09/td3.pdf]]
#* exemples XHTML ([[hello world|teaching/ili09/helloworld.html]],[[journal|teaching/ili09/journal.html]],[[list|teaching/ili09/list.html]],[[table|teaching/ili09/table.html]],[[links|teaching/ili09/links.html]],[[references|teaching/ili09/references.html]])
#* Page [[TiddlyWiki|teaching/ili09/tiddlywiki.html]] à télécharger (en tappant la touche droite sur le lien et "Enregistrer sous...")
#* aide-mémoire de syntaxe [[Wiki|teaching/ili09/wiki.pdf]] (dialecte ~TiddlyWiki)
#* aide-mémoire [[TiddlyWiki|http://tiddlypocketbook.com/]] (en anglais)
#* la page française de [[TiddlyWiki|http://www.tiddlywiki.fr]]
# [[CSS dans XHTML|teaching/ili09/td4.pdf]]
# [[XML, DTD et XSLT|teaching/ili09/td5.pdf]]
#* [[Tutoriel XML|http://www.zvon.org/xxl/XMLTutorial/General_fre/book.html]]
#* [[Tutoriel DTD|http://www.zvon.org/xxl/DTDTutorial/General_fre/book.html]]
#* [[Tutoriel XPath|http://www.zvon.org/xxl/XPathTutorial/General_fre/examples.html]]
#* [[Tutoriel XSLT|http://www.zvon.org/xxl/XSLTutorial/Output_fre/index.html]]
#* Fichier XML avec un livre de cuisine [[cuisinage.xml|teaching/ili09/cuisinage.xml]]
#* Fichier DTD avec schema du livre de cuisine [[cuisinage.dtd|teaching/ili09/cuisinage.dtd]]
#* Fichier XSLT pour transformer le fichier XML au ficher HTML [[cuisinage.xsl|teaching/ili09/cuisinage.xsl]]
#* Fichier HTML obtenu après la transformation [[cuisinage.html|teaching/ili09/cuisinage.html]]
# [[Programmation avec le Robot|teaching/ili09/td6.pdf]] (basé sur le [[matériel|http://www.grappa.univ-lille3.fr/~torre/Enseignement/TPs/robot.php]] de Fabien Torre)
#* [[Le Robot|teaching/ili09/Robot.zip]] (archive zip)
#[[Programmation en Pascal|teaching/ili09/td7.pdf]]
#* [[Programmes|teaching/ili09/pascal1.zip]] (archive zip)
<<list filter "[tag[index]]">>
<<list filter "[tag[teaching]]">>
[[Home]]
[[Contact Information]]
[[Personal Information]]
[[Publications]]
[[Teaching|Enseignement]] (in French)
|''Name''|MainTheme|
|''Description''|main theme limiting access of ReadOnly users|
!Author Mode
|PageTemplate|Author.PageTemplate|
|ViewTemplate|Author.ViewTemplate|
|EditTemplate|Author.EditTemplate|
|StyleSheet|StyleSheet|
|ColorPalette|ColorPalette|
!Read-Only Mode
|PageTemplateReadOnly|ReadOnly.PageTemplate|
|ViewTemplateReadOnly|ReadOnly.ViewTemplate|
|EditTemplateReadOnly|ReadOnly.ViewTemplate|
|StyleSheetReadOnly|StyleSheet|
|ColorPalette|ColorPalette|
!StyleSheet
/*{{{*/
#sidebarTabs {
display: none;
}
/*}}}*/
Education:
* 2002 to 2007 Ph.D. in Computer Science, University at Buffalo, Buffalo, New York, USA. Dissertation topic: [[Declarative Inconsistency Handling in Relational and Semi-structured Databases|papers/staworko-phd-thesis.pdf]]. Supervisor: [[Jan Chomicki|http://www.cse.buffalo.edu/~chomicki]].
* 1998 to 2002 M.S./B.S in Computer Science, Wroclaw University, Wroclaw, Poland. Thesis title: Effective Implementation of Priority Queues (in Polish.)
My CV is available [[here|papers/staworko-cv.pdf]].
A list of my scientific ancestors can be found <<slider genealogy [[Genealogy]] here>>
/***
Hijicking (and overloading) the core search functions
***/
//{{{
config.macros.search.doSearch = function(txt)
{
if(txt.value.length > 0) {
story.search(txt.value,config.options.chkCaseSensitiveSearch,config.options.chkRegExpSearch,config.options.chkFilterPublicTagsSearch);
txt.setAttribute("lastSearchText",txt.value);
}
};
Story.prototype.search = function(text,useCaseSensitive,useRegExp,filterPublicTags)
{
this.closeAllTiddlers();
highlightHack = new RegExp(useRegExp ? text : text.escapeRegExp(),useCaseSensitive ? "mg" : "img");
var matches = store.search(highlightHack,"title","excludeSearch",false,filterPublicTags);
this.displayTiddlers(null,matches);
highlightHack = null;
var q = useRegExp ? "/" : "'";
if(matches.length > 0)
displayMessage(config.macros.search.successMsg.format([matches.length.toString(),q + text + q]));
else
displayMessage(config.macros.search.failureMsg.format([q + text + q]));
};
// Return an array of tiddlers matching a search regular expression
TiddlyWiki.prototype.search = function(searchRegExp,sortField,excludeTag,match,filterPublicTags)
{
var candidates = this.reverseLookup("tags",excludeTag,!!match);
var results = [];
for(var t=0; t<candidates.length; t++) {
if (!(filterPublicTags && !candidates[t].isTagged("public")))
if((candidates[t].title.search(searchRegExp) != -1) ||
(candidates[t].text.search(searchRegExp) != -1))
results.push(candidates[t]);
}
if(!sortField)
sortField = "title";
results.sort(function(a,b) {return a[sortField] < b[sortField] ? -1 : (a[sortField] == b[sortField] ? 0 : +1);});
return results;
};
//}}}
/***
|Name|Plugin: jsMath|
|Created by|BobMcElrath|
|Email|my first name at my last name dot org|
|Location|http://bob.mcelrath.org/tiddlyjsmath.html|
|Version|1.5.1|
|Requires|[[TiddlyWiki|http://www.tiddlywiki.com]] ≥ 2.0.3, [[jsMath|http://www.math.union.edu/~dpvc/jsMath/]] ≥ 3.0|
!Description
LaTeX is the world standard for specifying, typesetting, and communicating mathematics among scientists, engineers, and mathematicians. For more information about LaTeX itself, visit the [[LaTeX Project|http://www.latex-project.org/]]. This plugin typesets math using [[jsMath|http://www.math.union.edu/~dpvc/jsMath/]], which is an implementation of the TeX math rules and typesetting in javascript, for your browser. Notice the small button in the lower right corner which opens its control panel.
!Installation
In addition to this plugin, you must also [[install jsMath|http://www.math.union.edu/~dpvc/jsMath/download/jsMath.html]] on the same server as your TiddlyWiki html file. If you're using TiddlyWiki without a web server, then the jsMath directory must be placed in the same location as the TiddlyWiki html file.
I also recommend modifying your StyleSheet use serif fonts that are slightly larger than normal, so that the math matches surrounding text, and \\small fonts are not unreadable (as in exponents and subscripts).
{{{
.viewer {
line-height: 125%;
font-family: serif;
font-size: 12pt;
}
}}}
If you had used a previous version of [[Plugin: jsMath]], it is no longer necessary to edit the main tiddlywiki.html file to add the jsMath <script> tag. [[Plugin: jsMath]] now uses ajax to load jsMath.
!History
* 11-Nov-05, version 1.0, Initial release
* 22-Jan-06, version 1.1, updated for ~TW2.0, tested with jsMath 3.1, editing tiddlywiki.html by hand is no longer necessary.
* 24-Jan-06, version 1.2, fixes for Safari, Konqueror
* 27-Jan-06, version 1.3, improved error handling, detect if ajax was already defined (used by ZiddlyWiki)
* 12-Jul-06, version 1.4, fixed problem with not finding image fonts
* 26-Feb-07, version 1.5, fixed problem with Mozilla "unterminated character class".
* 27-Feb-07, version 1.5.1, Runs compatibly with TW 2.1.0+, by Bram Chen
!Examples
|!Source|!Output|h
|{{{The variable $x$ is real.}}}|The variable $x$ is real.|
|{{{The variable \(y\) is complex.}}}|The variable \(y\) is complex.|
|{{{This \[\int_a^b x = \frac{1}{2}(b^2-a^2)\] is an easy integral.}}}|This \[\int_a^b x = \frac{1}{2}(b^2-a^2)\] is an easy integral.|
|{{{This $$\int_a^b \sin x = -(\cos b - \cos a)$$ is another easy integral.}}}|This $$\int_a^b \sin x = -(\cos b - \cos a)$$ is another easy integral.|
|{{{Block formatted equations may also use the 'equation' environment \begin{equation} \int \tan x = -\ln \cos x \end{equation} }}}|Block formatted equations may also use the 'equation' environment \begin{equation} \int \tan x = -\ln \cos x \end{equation}|
|{{{Equation arrays are also supported \begin{eqnarray} a &=& b \\ c &=& d \end{eqnarray} }}}|Equation arrays are also supported \begin{eqnarray} a &=& b \\ c &=& d \end{eqnarray} |
|{{{I spent \$7.38 on lunch.}}}|I spent \$7.38 on lunch.|
|{{{I had to insert a backslash (\\) into my document}}}|I had to insert a backslash (\\) into my document|
!Code
***/
//{{{
// AJAX code adapted from http://timmorgan.org/mini
// This is already loaded by ziddlywiki...
if(typeof(window["ajax"]) == "undefined") {
ajax = {
x: function(){try{return new ActiveXObject('Msxml2.XMLHTTP')}catch(e){try{return new ActiveXObject('Microsoft.XMLHTTP')}catch(e){return new XMLHttpRequest()}}},
gets: function(url){var x=ajax.x();x.open('GET',url,false);x.send(null);return x.responseText}
}
}
// Load jsMath
jsMath = {
Setup: {inited: 1}, // don't run jsMath.Setup.Body() yet
Autoload: {root: new String(document.location).replace(/[^\/]*$/,'jsMath/')} // URL to jsMath directory, change if necessary
};
if (!jsMath.Font) {jsMath.Font = {}}
jsMath.Font.Message = function () {};
var jsMathstr;
try {
jsMathstr = ajax.gets(jsMath.Autoload.root+"jsMath.js");
} catch(e) {
alert("jsMath was not found: you must place the 'jsMath' directory in the same place as this file. "
+"The error was:\n"+e.name+": "+e.message);
throw(e); // abort eval
}
try {
window.eval(jsMathstr);
} catch(e) {
alert("jsMath failed to load. The error was:\n"+e.name + ": " + e.message + " on line " + e.lineNumber);
}
jsMath.Setup.inited=0; // allow jsMath.Setup.Body() to run again
// Define wikifers for latex
config.formatterHelpers.mathFormatHelper = function(w) {
var e = document.createElement(this.element);
e.className = this.className;
var endRegExp = new RegExp(this.terminator, "mg");
endRegExp.lastIndex = w.matchStart+w.matchLength;
var matched = endRegExp.exec(w.source);
if(matched) {
var txt = w.source.substr(w.matchStart+w.matchLength,
matched.index-w.matchStart-w.matchLength);
if(this.keepdelim) {
txt = w.source.substr(w.matchStart, matched.index+matched[0].length-w.matchStart);
}
e.appendChild(document.createTextNode(txt));
w.output.appendChild(e);
w.nextMatch = endRegExp.lastIndex;
}
}
config.formatters.push({
name: "displayMath1",
match: "\\\$\\\$",
terminator: "\\\$\\\$\\n?", // 2.0 compatability
termRegExp: "\\\$\\\$\\n?",
element: "div",
className: "math",
handler: config.formatterHelpers.mathFormatHelper
});
config.formatters.push({
name: "inlineMath1",
match: "\\\$",
terminator: "\\\$", // 2.0 compatability
termRegExp: "\\\$",
element: "span",
className: "math",
handler: config.formatterHelpers.mathFormatHelper
});
var backslashformatters = new Array(0);
backslashformatters.push({
name: "inlineMath2",
match: "\\\\\\\(",
terminator: "\\\\\\\)", // 2.0 compatability
termRegExp: "\\\\\\\)",
element: "span",
className: "math",
handler: config.formatterHelpers.mathFormatHelper
});
backslashformatters.push({
name: "displayMath2",
match: "\\\\\\\[",
terminator: "\\\\\\\]\\n?", // 2.0 compatability
termRegExp: "\\\\\\\]\\n?",
element: "div",
className: "math",
handler: config.formatterHelpers.mathFormatHelper
});
backslashformatters.push({
name: "displayMath3",
match: "\\\\begin\\{equation\\}",
terminator: "\\\\end\\{equation\\}\\n?", // 2.0 compatability
termRegExp: "\\\\end\\{equation\\}\\n?",
element: "div",
className: "math",
handler: config.formatterHelpers.mathFormatHelper
});
// These can be nested. e.g. \begin{equation} \begin{array}{ccc} \begin{array}{ccc} ...
backslashformatters.push({
name: "displayMath4",
match: "\\\\begin\\{eqnarray\\}",
terminator: "\\\\end\\{eqnarray\\}\\n?", // 2.0 compatability
termRegExp: "\\\\end\\{eqnarray\\}\\n?",
element: "div",
className: "math",
keepdelim: true,
handler: config.formatterHelpers.mathFormatHelper
});
// The escape must come between backslash formatters and regular ones.
// So any latex-like \commands must be added to the beginning of
// backslashformatters here.
backslashformatters.push({
name: "escape",
match: "\\\\.",
handler: function(w) {
w.output.appendChild(document.createTextNode(w.source.substr(w.matchStart+1,1)));
w.nextMatch = w.matchStart+2;
}
});
config.formatters=backslashformatters.concat(config.formatters);
window.wikify = function(source,output,highlightRegExp,tiddler)
{
if(source && source != "") {
if(version.major == 2 && version.minor > 0) {
var wikifier = new Wikifier(source,getParser(tiddler),highlightRegExp,tiddler);
wikifier.subWikifyUnterm(output);
} else {
var wikifier = new Wikifier(source,formatter,highlightRegExp,tiddler);
wikifier.subWikify(output,null);
}
jsMath.ProcessBeforeShowing();
}
}
//}}}
''Journals''
#[[Prioritized Repairing and Consistent Query Answering in Relational Databases|papers/staworko-amai09.pdf]], //Accepted to the special SUM'08 issue of Annals of Mathematics and Artificial Intelligence//, (with J. Chomicki and J. Marcinkowski) <<slider bibtexStChMa09 [[BibTeX##StChMa09]] bibtex>>
#[[Consistent Query Answers in the Presence of Universal Constraints|papers/staworko-is09.pdf]], //Information Systems//, Volume 35(1), 2010, pp. 1-22 (with J. Chomicki) <<slider bibtexStCh10 [[BibTeX##StCh10]] bibtex>>
''Conferences and Workshops''
# [[The View Update Problem for XML|papers/staworko-wuxml10.pdf]], //EDBT/ICDT Workshops (Updates in XML)//, March 2010, Lausanne, Switzerland (with I. Boneva, B. Groz) <<slider bibtexStBoGr10 [[BibTeX##StBoGr10]] bibtex>>
# [[XML Security Views Revisited|papers/staworko-dbpl09.pdf]], //Database Programming Languages (DBPL)//, August 2009, Lyon, France (with B. Groz, A.-C. Caron, Y. Roos, and S. Tison) ([[slides|papers/staworko-dbpl09-talk.pdf]])<<slider bibtexGSCRT09 [[BibTeX##GSCRT09]] bibtex>>
# [[Equivalence of Deterministic Nested Word to Word Transducers|papers/staworko-fct09.pdf]], //Fundamentals of Computation Theory (FCT)//. September 2009, Wroclaw, Poland (with G. Laurence, A. Lemay, and J. Niechren)<<slider bibtexSLLN09 [[BibTeX##SLLN09]] bibtex>>
# [[Querying Regular Sets of XML Documents|papers/staworko-lid08.pdf]], //~LiD Workshop//. May 2008, Rome. (with E. Filiot and J. Chomicki)<<slider bibtexStFiCh08 [[BibTeX##StFiCh08]] bibtex>>
# [[Validity Sensitive Querying of XML Databases|papers/staworko-datax06.pdf]], //EDBT Workshops (dataX)//. March 2006, Munich, Germany. (with J. Chomicki) ([[slides|papers/staworko-datax06-talk.pdf]])<<slider bibtexStCh06 [[BibTeX##StCh06]] bibtex>>
# [[Preference-Driven Querying of Inconsistent Relational Databases|papers/staworko-iidb06.pdf]], //EDBT Workshops (IIDB)//. March 2006, Munich, Germany. (with J. Chomicki and J. Marcinkowski) ([[slides|papers/staworko-iidb06-talk.pdf]])<<slider bibtexStChMa06 [[BibTeX##StChMa06]] bibtex>>
# [[Computing Consistent Query Answers using Conflict Hypergraphs|papers/staworko-cikm04.pdf]], //Information and Knowledge Management (CIKM)//. November 2004, Washington, D.C. (with J. Chomicki and J. Marcinkowski)<<slider bibtexChMaSt04b [[BibTeX##ChMaSt04b]] bibtex>>
# [[Hippo: a System for Computing Consistent Query Answers to a Class of SQL Queries|papers/staworko-edbt04-demo.pdf]], // International Conference on Extending Database Technology//. (EDBT), March 2004, Heraklion, Greece. //System demo//. (with J. Chomicki and J. Marcinkowski)<<slider bibtexChMaSt04a [[BibTeX##ChMaSt04a]] bibtex>>
''Manuscripts''
#[[Priority-Based Conflict Resolution in Inconsistent Relational Databases|papers/staworko-arxiv-cqa-preferences.pdf]], //arXiv.org e-Print archive//, cs/0506063, June 2005 (with J. Chomicki) <<slider bibtexStCh05 [[BibTeX##StCh05]] bibtex>>
# [[Declarative Inconsistency Handling in Relational and Semi-structured Databases|papers/staworko-phd-thesis.pdf]], //Ph.D. thesis dissertation//, University at Buffalo, May 2007. ([[slides|papers/staworko-phd-talk.pdf]])<<slider bibtexStaworko07 [[BibTeX##Staworko07]] bibtex>>
<<slider copyright [[Copyright]] "Copyright Notice">>
Options are saved in your browser:
<<option chkRegExpSearch>> Regular expression search
<<option chkCaseSensitiveSearch>> Case sensitive search
<<option chkAnimate>> Enable animations
<<option chkSinglePageMode>> Single page mode
<!--{{{-->
<div class='header' macro='gradient vert [[ColorPalette::PrimaryLight]] [[ColorPalette::PrimaryMid]]'>
<div class='headerShadow'>
<span class='siteTitle' refresh='content' tiddler='SiteTitle'></span>
<span class='siteSubtitle' refresh='content' tiddler='SiteSubtitle'></span>
</div>
<div class='headerForeground'>
<span class='siteTitle' refresh='content' tiddler='SiteTitle'></span>
<span class='siteSubtitle' refresh='content' tiddler='SiteSubtitle'></span>
</div>
</div>
<div id='mainMenu' refresh='content' tiddler='MainMenu'></div>
<div id='sidebar'>
<div id='sidebarOptions' refresh='content' tiddler='ReadOnly.SideBarOptions'></div>
<div id='sidebarTabs' refresh='macro' force='true' macro='slider chkSideBarTabs ReadOnly.SideBarTabs "index »" "display lists of tiddlers"'></div>
</div>
<div id='displayArea'>
<div id='messageArea'></div>
<div id='tiddlerDisplay'></div>
</div>
<!--}}}-->
<<search>><<closeAll>><<permaview>><<slider chkSliderOptionsPanel ReadOnly.OptionsPanel "options »" "Change TiddlyWiki options">>
<<tabs txtMainTab "All" "All entries" Index.All "Enseignement" "Enseignement" Index.Teaching>>
<!--{{{-->
<!--div class='toolbar' macro='toolbar [[ToolbarCommands::ViewToolbar]]'></div-->
<div class='title' macro='view title'></div>
<!--div class='subtitle'><span macro='view modifier link'></span>, <span macro='view modified date'></span> (<span macro='message views.wikified.createdPrompt'></span> <span macro='view created date'></span>)</div-->
<!--div class='tagging' macro='tagging'></div-->
<!--div class='tagged' macro='tags'></div-->
<div class='viewer' macro='view text wikified'></div>
<div class='tagClear'></div>
<!--}}}-->
Cours: Structuration de l'Information
Responsable du cours: Slawek Staworko
Contenu du cours:
# Diagrames ER (~Entity-Relationship)
# Model relationnel de bases de données.
# Algèbre relationele
# Requêtes SQL (Structured Query Language)
TD:
# Création et gestion de ~BDs avec ~OpenOffice.
# Requêtes (QBE)
#* BD Resource Humaines ([[RH.odb|teaching/sql10/RH.odb]], [[RH.sql|teaching/sql10/RH.sql]]) <<slider QBE.RH [[SQL10Sliders##QBE.RH]] Requêtes>>
#* BD Discothèque ([[Discotheque.odb|teaching/sql10/Discotheque.odb]], [[discotheque.sql|teaching/sql10/discotheque.sql]]) <<slider QBE.RH [[SQL10Sliders##QBE.Discotheque]] Requêtes>>
Projet:
# [[Description|teaching/sql10/projet.pdf]] ([[2e session|teaching/sql10/projet-2e-session.pdf]])
# Exemple de l'inclusion d'un fichier PNG dans ~LaTeX ([[fourmiliere.zip|teaching/sql10/fourmiliere.zip]])
!QBE.RH
# Afficher les noms et prénoms de tous les employés.
# Afficher les noms et prénoms de tous les employés dont la salaire est inférieure à 15000.
# Afficher les noms, prénoms et salaires de tous les employés embauchés dans la première moitié de 2000.
# Idem + ordonner les résultats par la salaire (en ordre croissant).
# Afficher tous les titres sans répétition.
# Idem + le montant moyen de salaire pour tout titre.
# Idem + le montant minimum et maximum de salaire pour tout titre.
# Afficher les noms et prénoms des employés qui travaillent à Lille.
# Idem + ou à Marseille.
# Afficher les noms et prénoms des employés qui travaillent à Paris et gagnent moins de 20000.
# Afficher les noms et prénoms des employés qui travaillent à Paris où à Lille et qui gagnent moins de 20000.
# Afficher les noms et prénoms des employés qui travaillent à Paris et gagnent moins de 20000 où qui travaillent à Lille.
# Afficher les nom de tous les départements.
# Idem + le montant moyen de salaire pour tout département.
# Afficher les nom de tous les villes avec le montant moyen de salaire.
# Pour tout employé afficher son nom et prénom suivit par le ID de son supérieur.
# Pour tout employé afficher son nom et prénom suivit par le nom et prénom de son supérieur.
# Pour tout employé lister le nombre des employés dont il est responsable.
# Idem + le montant moyen de salaire des employés dont il est responsable.
# Pour tous employé afficher son nom et prénom avec le nom et prénom du supérieur de son supérieur.
!QBE.Discotheque
# Projection avec sélection.
## Afficher les titres des disques dont le prix est inférieur de 11.
## Idem + en ordre croissant du prix.
## Afficher les titres des disques dont le prix est entre 11 et 12.
## Afficher les titres des disques sortis en 1999.
## Afficher les titres des disques sortis dans les années 90
## Idem + en ordre décroissant de l'année et puis en croissant du prix (dans un groupe de disques sortis en même année).
## Afficher les titres des disques sortis entre 1995 et 1998 dont le prix est entre 11 et 13.
## Afficher les titres des disques endommagés.
## Idem + en ordre décroissant du prix
## Idem + en ordre croissant du l'année de sortie.
## Afficher les titres des disques endommagés, sortis en 1998 et dont le prix est inférieur à 13
## Afficher les titres des disques qui sont pas neufs.
# Agrégation simple
## Afficher le nombre total de disques.
## Afficher le nombre de disques endommagés.
## Afficher le nombre total de chansons.
## Afficher le nombre total d'artistes.
## Afficher la somme totale des prix de tous les disques.
## Afficher la somme des prix de tous les disques détruits.
## Afficher l'année moyenne de disques neufs.
## Afficher l'année moyenne de tous les
## Afficher le prix minimum et maximum de tous les disques.
## Idem + le prix moyen.
# Jointures
## Pour toute chanson afficher son titre et son genre.
## Afficher les titres des chansons Blues (faire ça en utilisant une jointure).
## Afficher les titres des chansons dont le genre est soit New Age soit Jazz.
## Afficher les titres des chansons interprétées par Gothic Slam (Idem pour DJ Ray et The Police).
## Afficher les titres des disques avec des chansons interprétées par Le Tigre.
## IDEM + ordonner les résultats par le titre en ordre alphabétique croissant (A,B,C,...,Z).
## Afficher les noms d'artistes qui interprètent une des chansons sur le disque intitulé "Il faut tourner l'apache" (sans répétition).
## Afficher les noms des disques contenant la chanson "(I can't get no) Satisfaction" (Idem pour "Brown Sugar" et "Je t'aime... Moi non plus")
## Afficher pour tout artiste tous les genres dont il interprète des chansons.
# Jointures + Agrégation
## Calculer le prix moyen de disque contenant des chansons de genre Rock. (Idem + avec tous les genres)
## Afficher pour tout genre le nombre de chansons de ce genre.
## Afficher pour tout disques son titre et nombre de chansons qu'il contient, ordonner les résultat par le nombre de chansons (en ordre décroissant)
## Trouver le 10 artistes avec le plus de chansons interprétées.
## Pour tout genre afficher l'année moyenne, minimum et maximum de disques contenant des chansons de ce genre.
/***
|Name|SinglePageModePlugin|
|Source|http://www.TiddlyTools.com/#SinglePageModePlugin|
|Documentation|http://www.TiddlyTools.com/#SinglePageModePluginInfo|
|Version|2.9.6|
|Author|Eric Shulman|
|License|http://www.TiddlyTools.com/#LegalStatements|
|~CoreVersion|2.1|
|Type|plugin|
|Requires||
|Overrides|Story.prototype.displayTiddler(), Story.prototype.displayTiddlers()|
|Options|##Configuration|
|Description|Show tiddlers one at a time with automatic permalink, or always open tiddlers at top/bottom of page.|
This plugin allows you to configure TiddlyWiki to navigate more like a traditional multipage web site with only one tiddler displayed at a time.
!!!!!Documentation
>see [[SinglePageModePluginInfo]]
!!!!!Configuration
<<<
<<option chkSinglePageMode>> Display one tiddler at a time
><<option chkSinglePagePermalink>> Automatically permalink current tiddler
><<option chkSinglePageKeepFoldedTiddlers>> Don't close tiddlers that are folded
><<option chkSinglePageKeepEditedTiddlers>> Don't close tiddlers that are being edited
<<option chkTopOfPageMode>> Open tiddlers at the top of the page
<<option chkBottomOfPageMode>> Open tiddlers at the bottom of the page
<<option chkSinglePageAutoScroll>> Automatically scroll tiddler into view (if needed)
Notes:
* The "display one tiddler at a time" option can also be //temporarily// set/reset by including a 'paramifier' in the document URL: {{{#SPM:true}}} or {{{#SPM:false}}}.
* If more than one display mode is selected, 'one at a time' display takes precedence over both 'top' and 'bottom' settings, and if 'one at a time' setting is not used, 'top of page' takes precedence over 'bottom of page'.
* When using Apple's Safari browser, automatically setting the permalink causes an error and is disabled.
<<<
!!!!!Revisions
<<<
2008.10.17 [2.9.6] changed chkSinglePageAutoScroll default to false
| Please see [[SinglePageModePluginInfo]] for previous revision details |
2005.08.15 [1.0.0] Initial Release. Support for BACK/FORWARD buttons adapted from code developed by Clint Checketts.
<<<
!!!!!Code
***/
//{{{
version.extensions.SinglePageModePlugin= {major: 2, minor: 9, revision: 6, date: new Date(2008,10,17)};
//}}}
//{{{
config.paramifiers.SPM = { onstart: function(v) {
config.options.chkSinglePageMode=eval(v);
if (config.options.chkSinglePageMode && config.options.chkSinglePagePermalink && !config.browser.isSafari) {
config.lastURL = window.location.hash;
if (!config.SPMTimer) config.SPMTimer=window.setInterval(function() {checkLastURL();},1000);
}
} };
//}}}
//{{{
if (config.options.chkSinglePageMode==undefined)
config.options.chkSinglePageMode=true;
if (config.options.chkSinglePagePermalink==undefined)
config.options.chkSinglePagePermalink=true;
if (config.options.chkSinglePageKeepFoldedTiddlers==undefined)
config.options.chkSinglePageKeepFoldedTiddlers=false;
if (config.options.chkSinglePageKeepEditedTiddlers==undefined)
config.options.chkSinglePageKeepEditedTiddlers=false;
if (config.options.chkTopOfPageMode==undefined)
config.options.chkTopOfPageMode=false;
if (config.options.chkBottomOfPageMode==undefined)
config.options.chkBottomOfPageMode=false;
if (config.options.chkSinglePageAutoScroll==undefined)
config.options.chkSinglePageAutoScroll=false;
//}}}
//{{{
config.SPMTimer = 0;
config.lastURL = window.location.hash;
function checkLastURL()
{
if (!config.options.chkSinglePageMode)
{ window.clearInterval(config.SPMTimer); config.SPMTimer=0; return; }
if (config.lastURL == window.location.hash) return; // no change in hash
var tids=decodeURIComponent(window.location.hash.substr(1)).readBracketedList();
if (tids.length==1) // permalink (single tiddler in URL)
story.displayTiddler(null,tids[0]);
else { // restore permaview or default view
config.lastURL = window.location.hash;
if (!tids.length) tids=store.getTiddlerText("DefaultTiddlers").readBracketedList();
story.closeAllTiddlers();
story.displayTiddlers(null,tids);
}
}
if (Story.prototype.SPM_coreDisplayTiddler==undefined)
Story.prototype.SPM_coreDisplayTiddler=Story.prototype.displayTiddler;
Story.prototype.displayTiddler = function(srcElement,tiddler,template,animate,slowly)
{
var title=(tiddler instanceof Tiddler)?tiddler.title:tiddler;
var tiddlerElem=document.getElementById(story.idPrefix+title); // ==null unless tiddler is already displayed
var opt=config.options;
var single=opt.chkSinglePageMode && !startingUp;
var top=opt.chkTopOfPageMode && !startingUp;
var bottom=opt.chkBottomOfPageMode && !startingUp;
if (single) {
story.forEachTiddler(function(tid,elem) {
// skip current tiddler and, optionally, tiddlers that are folded.
if ( tid==title
|| (opt.chkSinglePageKeepFoldedTiddlers && elem.getAttribute("folded")=="true"))
return;
// if a tiddler is being edited, ask before closing
if (elem.getAttribute("dirty")=="true") {
if (opt.chkSinglePageKeepEditedTiddlers) return;
// if tiddler to be displayed is already shown, then leave active tiddler editor as is
// (occurs when switching between view and edit modes)
if (tiddlerElem) return;
// otherwise, ask for permission
var msg="'"+tid+"' is currently being edited.\n\n";
msg+="Press OK to save and close this tiddler\nor press Cancel to leave it opened";
if (!confirm(msg)) return; else story.saveTiddler(tid);
}
story.closeTiddler(tid);
});
}
else if (top)
arguments[0]=null;
else if (bottom)
arguments[0]="bottom";
if (single && opt.chkSinglePagePermalink && !config.browser.isSafari) {
window.location.hash = encodeURIComponent(String.encodeTiddlyLink(title));
config.lastURL = window.location.hash;
document.title = wikifyPlain("SiteTitle") + " - " + title;
if (!config.SPMTimer) config.SPMTimer=window.setInterval(function() {checkLastURL();},1000);
}
if (tiddlerElem && tiddlerElem.getAttribute("dirty")=="true") { // editing... move tiddler without re-rendering
var isTopTiddler=(tiddlerElem.previousSibling==null);
if (!isTopTiddler && (single || top))
tiddlerElem.parentNode.insertBefore(tiddlerElem,tiddlerElem.parentNode.firstChild);
else if (bottom)
tiddlerElem.parentNode.insertBefore(tiddlerElem,null);
else this.SPM_coreDisplayTiddler.apply(this,arguments); // let CORE render tiddler
} else
this.SPM_coreDisplayTiddler.apply(this,arguments); // let CORE render tiddler
var tiddlerElem=document.getElementById(story.idPrefix+title);
if (tiddlerElem&&opt.chkSinglePageAutoScroll) {
// scroll to top of page or top of tiddler
var isTopTiddler=(tiddlerElem.previousSibling==null);
var yPos=isTopTiddler?0:ensureVisible(tiddlerElem);
// if animating, defer scroll until after animation completes
var delay=opt.chkAnimate?config.animDuration+10:0;
setTimeout("window.scrollTo(0,"+yPos+")",delay);
}
}
if (Story.prototype.SPM_coreDisplayTiddlers==undefined)
Story.prototype.SPM_coreDisplayTiddlers=Story.prototype.displayTiddlers;
Story.prototype.displayTiddlers = function() {
// suspend single/top/bottom modes when showing multiple tiddlers
var opt=config.options;
var saveSPM=opt.chkSinglePageMode; opt.chkSinglePageMode=false;
var saveTPM=opt.chkTopOfPageMode; opt.chkTopOfPageMode=false;
var saveBPM=opt.chkBottomOfPageMode; opt.chkBottomOfPageMode=false;
this.SPM_coreDisplayTiddlers.apply(this,arguments);
opt.chkBottomOfPageMode=saveBPM;
opt.chkTopOfPageMode=saveTPM;
opt.chkSinglePageMode=saveSPM;
}
//}}}
/***
|Name|SinglePageModePluginInfo|
|Source|http://www.TiddlyTools.com/#SinglePageModePlugin|
|Documentation|http://www.TiddlyTools.com/#SinglePageModePluginInfo|
|Version|2.9.6|
|Author|Eric Shulman|
|License|http://www.TiddlyTools.com/#LegalStatements|
|~CoreVersion|2.1|
|Type|documentation|
|Requires||
|Overrides||
|Description|Documentation for SinglePageModePlugin|
Normally, as you click on the links in TiddlyWiki, more and more tiddlers are displayed on the page. The order of this tiddler display depends upon when and where you have clicked. Some people like this non-linear method of reading the document, while others have reported that when many tiddlers have been opened, it can get somewhat confusing. SinglePageModePlugin allows you to configure TiddlyWiki to navigate more like a traditional multipage web site with only one item displayed at a time.
!!!!!Usage
<<<
When the plugin is enabled, only one tiddler will be displayed at a time and the browser window's titlebar is updated to include the current tiddler title. The browser's location URL is also updated with a 'permalink' for the current tiddler so that it is easier to create a browser 'bookmark' for the current tiddler. Alternatively, even when displaying multiple tiddlers //is// permitted, you can still reduce the potential for confusion by forcing tiddlers to always open at the top (or bottom) of the page instead of being displayed following the tiddler containing the link that was clicked.
<<<
!!!!!Configuration
<<<
<<option chkSinglePageMode>> Display one tiddler at a time
><<option chkSinglePagePermalink>> Automatically permalink current tiddler
><<option chkSinglePageKeepFoldedTiddlers>> Don't close tiddlers that are folded
><<option chkSinglePageKeepEditedTiddlers>> Don't close tiddlers that are being edited
<<option chkTopOfPageMode>> Open tiddlers at the top of the page
<<option chkBottomOfPageMode>> Open tiddlers at the bottom of the page
<<option chkSinglePageAutoScroll>> Automatically scroll tiddler into view (if needed)
Notes:
* {{block{
The "display one tiddler at a time" option can also be //temporarily// set/reset by including a 'paramifier' in the document URL: {{{#SPM:true}}} or {{{#SPM:false}}}. You can also use {{{SPM:expression}}}, where 'expression' is any javascript statement that evaluates to true or false. This allows you to create hard-coded links in other documents that can selectively enable/disable the use of this option based on various programmatic conditions, such as the current username. For example, using
{{{#SPM:config.options.txtUserName!="SomeName"}}}
enables 'one tiddler at a time' display for all users //other than// "~SomeName")}}}
* If more than one display mode is selected, 'one at a time' display takes precedence over both 'top' and 'bottom' settings, and if 'one at a time' setting is not used, 'top of page' takes precedence over 'bottom of page'.
* When using Apple's Safari browser, automatically setting the permalink causes an error and is disabled.
<<<
!!!!!Revisions
<<<
2008.10.17 [2.9.6] changed chkSinglePageAutoScroll default to false
2008.06.12 [2.9.5] corrected 'scroll to top of page' logic in auto-scroll handling
2008.06.11 [2.9.4] added chkSinglePageKeepEditedTiddlers option
2008.06.05 [2.9.3] in displayTiddler(), bypass single/top/bottom mode handling if startingUp. Allows multiple tiddlers to be displayed during startup processing (e.g., #story:DefaultTiddlers), even if single/top/bottom mode is enabled.
2008.04.18 [2.9.2] in displayTiddler() and checkLastURL(), handling for Unicode in tiddler titles (remove explicit conversion between Unicode and UTF, as this is apparently done automatically by encode/decodeURIComponent, resulting in double-encoding!
2008.04.08 [2.9.1] don't automatically add options to AdvancedOptions shadow tiddler
2008.04.02 [2.9.0] in displayTiddler(), when single-page mode is in use and a tiddler is being edited, ask for permission to save-and-close that tiddler, instead of just leaving it open.
2008.03.29 [2.8.3] in displayTiddler(), get title from tiddler object (if needed). Fixes errors caused when calling function passes a tiddler *object* instead of a tiddler *title*
2008.03.14 [2.8.2] in displayTiddler(), if editing specified tiddler, just move it to top/bottom of story *without* re-rendering (prevents discard of partial edits).
2008.03.06 [2.8.1] in paramifier handler, start 'checkURL' timer if chkSinglePageMode is enabled
2008.03.06 [2.8.0] added option, {{{config.options.chkSinglePageKeepFoldedTiddlers}}}, so folded tiddlers won't be closed when using single-page mode. Also, in checkURL(), if hash is a ''permaview'' (e.g., "#foo bar baz"), then display multiple tiddlers rather than attempting to display "foo bar baz" as a single tiddler
2008.03.05 [2.7.0] added support for "SPM:" URL paramifier
2008.03.01 [2.6.0] in hijack of displayTiddler(), added 'title' argument to closeAllTiddlers() so that target tiddler isn't closed-and-reopened if it was already displayed. Also, added config.options.chkSinglePageAutoScrolloption to bypass automatic 'scroll into view' logic (note: core still does it's own ensureVisible() handling)
2007.12.22 [2.5.3] in checkLastURL(), use decodeURIComponent() instead of decodeURI so that tiddler titles with commas (and/or other punctuation) are correctly handled.
2007.10.26 [2.5.2] documentation cleanup
2007.10.08 [2.5.1] in displayTiddler(), when using single-page or top-of-page mode, scrollTo(0,0) to ensure that page header is in view.
2007.09.13 [2.5.0] for TPM/BPM modes, don't force tiddler to redisplay if already shown. Allows transition between view/edit or collapsed/view templates, without repositioning displayed tiddler.
2007.09.12 [2.4.0] added option to disable automatic permalink feature. Also, Safari is now excluded from permalinking action to avoid bug where tiddlers don't display after hash is updated.
2007.03.03 [2.3.1] fix typo when adding BPM option to AdvancedOptions (prevented checkbox from appearing)
2007.03.03 [2.3.0] added support for BottomOfPageMode (BPM) based on request from DaveGarbutt
2007.02.06 [2.2.3] in Story.prototype.displayTiddler(), use convertUnicodeToUTF8() for correct I18N string handling when creating URL hash string from tiddler title (based on bug report from BidiX)
2007.01.08 [2.2.2] use apply() to invoke hijacked core functions
2006.07.04 [2.2.1] in hijack for displayTiddlers(), suspend TPM as well as SPM so that DefaultTiddlers displays in the correct order.
2006.06.01 [2.2.0] added chkTopOfPageMode (TPM) handling
2006.02.04 [2.1.1] moved global variable declarations to config.* to avoid FireFox 1.5.0.1 crash bug when assigning to globals
2005.12.27 [2.1.0] hijack displayTiddlers() so that SPM can be suspended during startup while displaying the DefaultTiddlers (or #hash list). Also, corrected initialization for undefined SPM flag to "false", so default behavior is to display multiple tiddlers
2005.12.27 [2.0.0] Update for TW2.0
2005.11.24 [1.1.2] When the back and forward buttons are used, the page now changes to match the URL. Based on code added by Clint Checketts
2005.10.14 [1.1.1] permalink creation now calls encodeTiddlyLink() to handle tiddler titles with spaces in them
2005.10.14 [1.1.0] added automatic setting of window title and location bar ('auto-permalink'). feature suggestion by David Dickens.
2005.10.09 [1.0.1] combined documentation and code in a single tiddler
2005.08.15 [1.0.0] Initial Release
<<<
http://www.grappa.univ-lille3.fr/~staworko/
/***
This fixes a problem with the tabs slider
***/
/*{{{*/
#sidebarTabs .button {
margin:0em 0.2em;
padding:0.2em 0.3em;
display:block;
}
/*}}}*/
/***
Toolbar
***/
/*{{{*/
.toolbar {color:[[ColorPalette::Background]];}
.toolbar a {color:[[ColorPalette::Background]];}
/*}}}*/
/***
Bigger fonts
***/
/*{{{*/
.viewer {
line-height: 125%;
/* font-family: serif;*/
font-size: 12pt;
}
/*}}}*/
/*{{{*/
@media print {
#mainMenu, #sidebar, #messageArea, .toolbar, #backstageButton, #backstageArea {display: none ! important;}
#displayArea {margin: 1em 1em 0em 1em;}
/* Fixes a feature in Firefox 1.5.0.2 where print preview displays the noscript content */
noscript {display:none;}
}
/*}}}*/
|~ViewToolbar|closeTiddler > closeOthers +editTiddler fields syncing permalink references jump|
|~EditToolbar|+saveTiddler -cancelTiddler deleteTiddler|
Ici, vous pouvez trouver quelques implémentations de la Transformée de Fourier Rapide (FFT de l'ang. Fast Fourier Tranform). La FFT est largement utilisée dans la domaine de traitement de signal. Pourtant, j'ai suivi la présentation utilisée dans le chapitre 32 de "//Intorduction to Algorithms//" par T. Cormen où elle est introduite pour multiplier vite deux polynômes. La méthode directe de multiplication de deux polynômes prend $O(n^2)$ de temps. Cependant, FFT permet de le faire en temps $O(n log n).$
Le package que j'ai préparé comprend 5 méthodes de calculer une convolution de deux vecteurs (le nom formel associé avec multiplication des polynômes):
* Méthode directe qui est exacte mais pour de grandes données n'est pas très efficace
* Méthode basée sur l'interpolation et l'évaluation des polynômes.
* 3 Méthodes basées sur FFT:
** FFT Récursive qui est vite.
** FFT Itérative qui est même plus vite grâce à l'élimination des appelles récursives.
** FFT Parallèle qui permet de profiter de plusieurs processeurs.
Tous les algorithmes ont été implémentés en C#. J'ai utilisé le compiler [[Mono|http://www.mono-project.com]] et le système [[Doxygen|http://www.doxygen.org]] . Les [[sources|teaching/aac08/fft-src.tar.gz]], la [[documentation d'API|teaching/aac08/fft-doc/index.html]] et l'[[exécutable|teaching/aac08/FFT.exe]] sont disponibles.
/***
Some set-up for read-only users
***/
//{{{
if (readOnly)
config.options.chkFilterPublicTagsSearch = true;
//}}}
/***
Set the main theme
***/
//{{{
config.options.txtTheme = "MainTheme";
//}}}