presentationpstl.tex

\documentclass{beamer}
\mode<presentation>
{\usetheme[left]{Goettingen}
\useinnertheme[shadow]{rounded}
}
\usefonttheme{serif}

\usepackage[french]{babel}

\usepackage[utf8]{inputenc}

\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage{array}
\usepackage{rotating}
\usepackage{graphicx}
\usepackage{hyperref} 


\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{txfonts}

\usepackage{color}
\usepackage{multicol}
\usepackage{multirow}
\usepackage{qtree}
\usepackage{dot2texi}
\usepackage{listings}
\lstset{%
language=python,
basicstyle=\scriptsize\ttfamily
}


\hypersetup{
     backref=true,    %permet d'ajouter des liens dans...
     pagebackref=true,%...les bibliographies
     hyperindex=true, %ajoute des liens dans les index.
     colorlinks=true, %colorise les liens
     breaklinks=true, %permet le retour à la ligne dans les liens trop longs
     urlcolor= blue,  %couleur des hyperliens
     linkcolor= , %couleur des liens internes
     bookmarks=true,  %créé des signets pour Acrobat
     bookmarksopen=true,            %si les signets Acrobat sont créés,
                                    %les afficher complètement.
     pdftitle={Présentation colour numbers of complete graphs}, %informations apparaissant dans
     pdfauthor={Marguerite Zamansky},     %dans les informations du document
     }



\title	
{Outils de combinatoire analytique en sage}
\subtitle{Projet STL}

\author
{Matthieu Dien \and Marguerite Zamansky}

\institute
{Université Pierre et Marie Curie}

\date{\today}

\AtBeginSection[]
{
\begin{frame}<beamer>{Sommaire}
    \tableofcontents[currentsection]
   \end{frame}
   }

\begin{document}

\begin{frame}
\titlepage
\end{frame}

\begin{frame}{Objectifs}
\begin{itemize}
\item Fournir un outil de calcul symbolique pour des séries multivariées,
\item de préférence libre :
\item offrir une alternative à Mapple et porter les fonctionnalités de Gfun vers Sage.
\end{itemize}
\end{frame}

\section{Sage}
\begin{frame}{Sage}

\begin{figure}
\includegraphics[width=4cm]{sage_logo_new.jpeg}
\end{figure}

\begin{itemize}
\item logiciel libre de calcul formel num\'erique et symbolique
\item regroupe des outils déjà connus et éprouvés (GP/PARI, GAP, Singular, Maxima)
\item et ses propres paquets (combinat, rings, matrix ...)
\item le tout interfacé par un top-level Python
\end{itemize}

\end{frame}
\section{Combinatoire analytique}

\begin{frame}{Définitions}
\begin{block}{Série génératrice multivariée}
Une série génératrice $A$ associée à une classe combinatoire $\mathcal{A}$ :%s et $k$ paramètres scalaires $\chi_j$ : 
$$ A(X_1, \ldots, X_k) = \sum_{i_1, \ldots ,i_k \ge 0}^{+\infty} a_{i_1, \ldots , i_k} \ X_1^{i_1} \cdots X_k^{i_k} $$
permet de compter le nombre d'élément de $\mathcal{A}$. %: $a_{i_1, \ldots , i_k} = \mathrm{Card}( e \in \mathcal{A}, \  \chi_j(e)=i_j, \ \forall j \in \llbracket 1 , k \rrbracket )$
\note{On utilise des séries formelles, on n'a pas besoin d'avoir un rayon de convergence non nul, plus l'infini se traduit par un lazy}
\end{block}

\end{frame}


\begin{frame}{S\'eries G\'en\'eratrices Multivari\'ees}{Exemple}

\centering
Arbres binaires-ternaires :
$$\mathcal{ABT} = \{z\} \cdot \{w\} + \{z\} \cdot
\{u\} \cdot \mathcal{ABT}^2 + \{z\} \cdot \{v\} \cdot \mathcal{ABT}^3$$


\includegraphics[scale=0.3]{abttree.pdf}


\end{frame}

\begin{frame}{Exemple}
\begin{center}
\footnotesize{\begin{tabular}{c|c}
$ABT(z,u,v,w) =$ & \\
\hline
$z \cdot w \ + $ & $z\cdot w$ \\
 & \\
$z^3 \cdot u \cdot w^2 \ +$ & \Tree [.$z\cdot u$ $z\cdot w$ $z\cdot w$ ] \\
 & \\
$z^4 \cdot v \cdot w^3 \ +$ & \Tree [.$z\cdot v$ $z\cdot w$ $z\cdot w$ $z\cdot
  w$ ]\\
 & \\
$2 \cdot z^5 \cdot u^2 \cdot w^3 \ +$ & 
\Tree [.$z\cdot u$ [.$z\cdot u$ $z\cdot w$ $z\cdot w$ ] $z\cdot w$ ]
\hspace{0.2cm}
\Tree [.$z\cdot u$ $z\cdot w$ [.$z\cdot u$ $z\cdot w$ $z\cdot w$ ] ] \\
% & \\
$ \ldots $ & $ \ldots $\\
\end{tabular}
}
\end{center}
\end{frame}



\section{Implémentation}

\begin{frame}{Impl\'ementation}
\begin{block}{Difficultés}
\begin{itemize}
\item Représenter les séries formelles en mémoire
\item S'intégrer à un projet de grande envergure
\end{itemize}
\end{block}
\pause
\bigskip
\begin{block}{Solutions}
\begin{itemize}
\item Utilisation de streams (programmation paresseuse).
\item Générateurs python
\end{itemize}
\end{block}
\end{frame}

\begin{frame}[containsverbatim]{Générateurs Python}
\begin{block}{}
\begin{itemize}
\item Permet de créer des objets itérables
\item \texttt{yield}
\end{itemize}
\end{block}
\bigskip
\begin{block}{exemple : itérer sur les entiers}
  \begin{center}
    \begin{lstlisting}
def integers_definition():
    i = 0
    while True :
        yield i
        i += 1

for n in integers_definition():
    if n % 2 == 0:
        print("%d est pair"%n)
    else :
        print("%d est impair"%n)
    \end{lstlisting}
  \end{center}
\end{block}
\end{frame}  

\begin{frame}[containsverbatim]{Représentation}
 \small{Un stream de listes de couples formés d'un entier et d'un $n$-uplet.}
 
\begin{center}
\tiny{ \begin{tabular}{|c|l|}
\hline
entrée  &  mémoire \\
\hline
\texttt{F}
&
\begin{lstlisting}
[]
\end{lstlisting}
 \\
\hline
\texttt{F.coefficients(2); F}
&
\begin{lstlisting}
[[], 
 [],
 [(1,[0,0,1,1])]]
\end{lstlisting} \\
\hline
\texttt{F.coefficients(14); F}
&
\begin{lstlisting}
[[], 
 [],
 [(1,[0,0,1,1])],
 [], 
 [],
 [],
 [(1,[1,0,2,3])],
 [],
 [(2,[0,1,3,4])],
 [],
 [(2,[2,0,3,5])],
 [],
 [(5,[1,1,4,6])],
 [],
 [(5,[3,0,4,7]),
  (3,[0,2,5,7])]]
\end{lstlisting}
\\
\hline
\end{tabular}}
\end{center}
\end{frame}
  
\begin{frame}{Démonstration}{Arbres binaires-ternaires}
\begin{block}{Ce qu'on écrit dans Sage,}
\includegraphics[width=9cm]{binterspec}
\end{block}
\pause
\bigskip
\begin{block}{le résultat qu'on obtient.}
  \includegraphics[width=9cm]{binterres}
\end{block}
\end{frame}

\begin{frame}{Conclusion}
\begin{block}{Opérateurs implémentés}
\begin{itemize}
\item Addition
\item Produit
\item Séquence
\item Dérivée
\item Composition
\item Cast en polynôme
\end{itemize}
\end{block}
\pause
\begin{block}{Contribution}
\begin{itemize}
\item Patch bug dans Sage
\item Proposition du package
\end{itemize}
\end{block}
\end{frame}

\begin{frame}{Perspectives}
Continuer l'impl\'ementation pour avoir les fonctionnalit\'es disponibles dans Gfun :
\begin{itemize}
\item comme les algorithmes \textit{algfuntoalgeq, algeqtodiffeq, diffeqtorec}
\item Sage days, du 17 au 21 juin
\end{itemize}
\end{frame}
\end{document}