177 |
177 |
178 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
178 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
179 \begin{frame}[c] |
179 \begin{frame}[c] |
180 \frametitle{Why Bother?} |
180 \frametitle{Why Bother?} |
181 |
181 |
182 \begin{columns}[b] |
182 \begin{columns}[t] |
183 \begin{column}{.5\textwidth} |
183 \begin{column}{.5\textwidth} |
184 Ruby, Python\\ and Others\bigskip\\ |
184 Ruby, Python, Java\medskip\\ |
185 \begin{tikzpicture}[y=.08cm, x=.10cm] |
185 \begin{tikzpicture}\footnotesize |
186 %axis |
186 \begin{axis}[ |
187 \draw (0,0) -- coordinate (x axis mid) (30,0); |
187 xlabel={$n$}, |
188 \draw (0,0) -- coordinate (y axis mid) (0,30); |
188 x label style={at={(1.05,0.0)}}, |
189 %ticks |
189 ylabel={time in secs}, |
190 \foreach \x in {0,5,...,30} |
190 enlargelimits=false, |
191 \draw (\x,1pt) -- (\x,-3pt) node[anchor=north] {\footnotesize\x}; |
191 xtick={0,5,...,30}, |
192 \foreach \y in {0,5,...,30} |
192 xmax=33, |
193 \draw (1pt,\y) -- (-3pt,\y) node[anchor=east] {\footnotesize\y}; |
193 ymax=35, |
194 %labels |
194 ytick={0,5,...,30}, |
195 \node[below=0.6cm] at (x axis mid) {\footnotesize number of \texttt{a}s}; |
195 scaled ticks=false, |
196 \node[rotate=90,left=1cm] at (y axis mid) {\footnotesize time in secs}; |
196 axis lines=left, |
197 %plots |
197 width=5.5cm, |
198 \draw[color=blue] plot[mark=*] |
198 height=4cm, |
199 file {re-python.data}; |
199 legend entries={Python,Ruby}, |
200 \draw[color=brown] plot[mark=triangle*] |
200 legend pos=north west, |
201 file {re-ruby.data}; |
201 legend cell align=left] |
202 %legend |
202 \addplot[blue,mark=*] table {re-python.data}; |
203 \begin{scope}[shift={(4,20)}] |
203 \addplot[brown,mark=triangle*] table {re-ruby.data}; |
204 \draw[color=blue] (0,0) -- |
204 \end{axis} |
205 plot[mark=*] (0.25,0) -- (0.5,0) |
205 \end{tikzpicture} |
206 node[right]{\small Python}; |
206 \begin{tikzpicture}\footnotesize |
207 \draw[yshift=-\baselineskip, color=brown] (0,0) -- |
207 \begin{axis}[ |
208 plot[mark=triangle*] (0.25,0) -- (0.5,0) |
208 xlabel={$n$}, |
209 node[right]{\small Ruby}; |
209 x label style={at={(1.05,0.0)}}, |
210 \end{scope} |
210 ylabel={time in secs}, |
|
211 enlargelimits=false, |
|
212 xtick={0,5,...,30}, |
|
213 xmax=33, |
|
214 ymax=35, |
|
215 ytick={0,5,...,30}, |
|
216 scaled ticks=false, |
|
217 axis lines=left, |
|
218 width=5.5cm, |
|
219 height=4cm, |
|
220 legend entries={Java}, |
|
221 legend pos=north west, |
|
222 legend cell align=left] |
|
223 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; |
|
224 \end{axis} |
|
225 \end{tikzpicture} |
|
226 |
|
227 \end{column} |
|
228 \begin{column}{.5\textwidth} |
|
229 Us (after next lecture)\medskip\\ |
|
230 \begin{tikzpicture}\footnotesize |
|
231 \begin{axis}[ |
|
232 xlabel={$n$}, |
|
233 x label style={at={(1.07,0.0)}}, |
|
234 ylabel={time in secs}, |
|
235 enlargelimits=false, |
|
236 xtick={0,4000,...,12000}, |
|
237 xmax=13000, |
|
238 ymax=35, |
|
239 ytick={0,5,...,30}, |
|
240 scaled ticks=false, |
|
241 axis lines=left, |
|
242 width=5.5cm, |
|
243 height=4cm] |
|
244 \addplot[green,mark=square*,mark options={fill=white}] table {re2b.data}; |
|
245 \addplot[black,mark=square*,mark options={fill=white}] table {re3.data}; |
|
246 \end{axis} |
|
247 \end{tikzpicture} |
|
248 \begin{tikzpicture}\footnotesize |
|
249 \begin{axis}[ |
|
250 xlabel={$n$}, |
|
251 x label style={at={(1.07,0.0)}}, |
|
252 ylabel={time in secs}, |
|
253 enlargelimits=false, |
|
254 ymax=35, |
|
255 ytick={0,5,...,30}, |
|
256 scaled ticks=false, |
|
257 axis lines=left, |
|
258 width=5.5cm, |
|
259 height=4cm] |
|
260 \addplot[black,mark=square*,mark options={fill=white}] table {re3a.data}; |
|
261 \end{axis} |
211 \end{tikzpicture} |
262 \end{tikzpicture} |
212 \end{column} |
263 \end{column} |
213 \begin{column}{.5\textwidth} |
264 \end{columns}\bigskip |
214 Us (after next lecture)\\\mbox{}\bigskip\\ |
265 |
215 \begin{tikzpicture}[y=.08cm, x=.0003cm] |
266 \small\centering |
216 %axis |
267 matching \texttt{[a?]\{n\}[a]\{n\}} and \texttt{[a*]*b} |
217 \draw (0,0) -- coordinate (x axis mid) (12000,0); |
268 against $\underbrace{\texttt{a}...\texttt{a}}_n$ |
218 \draw (0,0) -- coordinate (y axis mid) (0,30); |
|
219 %ticks |
|
220 \foreach \x in {0,4000,...,12000} |
|
221 \draw (\x,1pt) -- (\x,-3pt) node[anchor=north] {\footnotesize\x}; |
|
222 \foreach \y in {0,5,...,30} |
|
223 \draw (1pt,\y) -- (-3pt,\y) node[anchor=east] {\footnotesize\y}; |
|
224 %labels |
|
225 \node[below=0.6cm] at (x axis mid) {\footnotesize number of \texttt{a}s}; |
|
226 \node[rotate=90, left=1cm] at (y axis mid) {\footnotesize time in secs}; |
|
227 |
|
228 %plots |
|
229 \draw[color=green] plot[mark=square*, mark options={fill=white} ] |
|
230 file {re2b.data}; |
|
231 \draw[color=black] plot[mark=square*, mark options={fill=white} ] |
|
232 file {re3.data}; |
|
233 \end{tikzpicture} |
|
234 \end{column} |
|
235 \end{columns}\bigskip\medskip |
|
236 |
|
237 \hspace{2cm}matching \texttt{[a?]\{n\}[a]\{n\}} against |
|
238 $\underbrace{\texttt{a}...\texttt{a}}_n$ |
|
239 \end{frame} |
269 \end{frame} |
240 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
270 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
271 |
|
272 |
241 |
273 |
242 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
274 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
243 \begin{frame}[c] |
275 \begin{frame}[c] |
244 \frametitle{Lectures 1 - 5} |
276 \frametitle{Lectures 1 - 5} |
245 |
277 |
660 \frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] |
692 \frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] |
661 Regular Expression\end{tabular}} |
693 Regular Expression\end{tabular}} |
662 |
694 |
663 \begin{textblock}{15}(1,4) |
695 \begin{textblock}{15}(1,4) |
664 \begin{tabular}{rcl} |
696 \begin{tabular}{rcl} |
665 \bl{$L(\varnothing)$} & \bl{$\dn$} & \bl{$\varnothing$}\\ |
697 \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ |
666 \bl{$L(\epsilon)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ |
698 \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ |
667 \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ |
699 \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ |
668 \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ |
700 \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ |
669 \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$\{ s_1 \,@\, s_2 \;|\; s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$}\\ |
701 \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$\{ s_1 \,@\, s_2 \;|\; s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$}\\ |
670 \bl{$L(r^*)$} & \bl{$\dn$} & \onslide<4->{\bl{$\bigcup_{n \ge 0} L(r)^n$}}\\ |
702 \bl{$L(r^*)$} & \bl{$\dn$} & \onslide<4->{\bl{$\bigcup_{0 \le n} L(r)^n$}}\\ |
671 \end{tabular}\bigskip |
703 \end{tabular}\bigskip |
672 |
704 |
673 \onslide<2->{ |
705 \onslide<2->{ |
674 \hspace{5mm}\bl{$L(r)^0 \;\dn\; \{[]\}$}\\ |
706 \hspace{5mm}\bl{$L(r)^0 \;\dn\; \{[]\}$}\\ |
675 \bl{$L(r)^{n+1} \;\dn\; L(r) \,@\, L(r)^n$}\hspace{9mm}\onslide<3->{\small\textcolor{gray}{(append on sets)}\\ |
707 \bl{$L(r)^{n+1} \;\dn\; L(r) \,@\, L(r)^n$}\hspace{9mm}\onslide<3->{\small\textcolor{gray}{(append on sets)}\\ |
725 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
757 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
726 \begin{frame}[t] |
758 \begin{frame}[t] |
727 \frametitle{Coursework} |
759 \frametitle{Coursework} |
728 |
760 |
729 \begin{itemize} |
761 \begin{itemize} |
730 \item Accounts for 25\%. Two strands. Choose \alert{\bf one}!\bigskip |
762 \item Accounts for 20\%. Two strands. Choose \alert{\bf one}!\bigskip |
731 \end{itemize} |
763 \end{itemize} |
732 |
764 |
733 \begin{columns}[t] |
765 \begin{columns}[t] |
734 \begin{column}{.5\textwidth} |
766 \begin{column}{.5\textwidth} |
735 \underline{\bf Strand 1}\medskip |
767 \underline{\bf Strand 1}\medskip |
736 \begin{itemize} |
768 \begin{itemize} |
737 \item four programming subtasks: |
769 \item four programming tasks: |
738 \begin{itemize} |
770 \begin{itemize} |
739 \item matcher (5\%, 16.10.) |
771 \item matcher (4\%, 20.10.) |
740 \item lexer (5\%, 06.11.) |
772 \item lexer (5\%, 03.11.) |
741 \item parser (5\%, 27.11.) |
773 \item parser (5\%, 24.11.) |
742 \item compiler (10\%, 11.12.) |
774 \item compiler (6\%, 13.12.) |
743 \end{itemize} |
775 \end{itemize} |
744 \end{itemize} |
776 \end{itemize} |
745 \end{column} |
777 \end{column} |
746 |
778 |
747 \hspace{-45pt}\vrule{}\hspace{10pt} |
779 \hspace{-45pt}\vrule{}\hspace{10pt} |
748 \begin{column}{.5\textwidth} |
780 \begin{column}{.5\textwidth} |
749 \underline{\bf Strand 2}\smallskip\begin{itemize} |
781 \underline{\bf Strand 2}\smallskip\begin{itemize} |
750 \item one task: prove the correctness of a regular expression matcher in |
782 \item one task: prove the correctness of a regular expression matcher in |
751 the Isabelle theorem prover |
783 the Isabelle theorem prover |
752 \item 25\%, submission 11.12. |
784 \item 20\%, submission 13.12. |
753 \end{itemize} |
785 \end{itemize} |
754 \end{column} |
786 \end{column} |
755 \end{columns}\medskip |
787 \end{columns}\medskip |
756 |
788 |
757 \small |
789 \small |