704
+ − 1 % !TEX program = xelatex
744
+ − 2 \documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
315
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 3 \usepackage{../slides}
215
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 4 \usepackage{../langs}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 5 \usepackage{../data}
871
+ − 6 \usepackage{../graphicss}
315
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 7 \usepackage{soul}
86
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 8
223
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 9 \tikzset{onslide/.code args={<#1>#2}{%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 10 \only<#1>{\pgfkeysalso{#2}} % \pgfkeysalso doesn't change the path
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 11 }}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 12
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 13 \makeatletter
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 14 \newenvironment<>{btHighlight}[1][]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 15 {\begin{onlyenv}#2\begingroup\tikzset{bt@Highlight@par/.style={#1}}\begin{lrbox}{\@tempboxa}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 16 {\end{lrbox}\bt@HL@box[bt@Highlight@par]{\@tempboxa}\endgroup\end{onlyenv}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 17
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 18 \newcommand<>\btHL[1][]{%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 19 \only#2{\begin{btHighlight}[#1]\bgroup\aftergroup\bt@HL@endenv}%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 20 }
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 21 \def\bt@HL@endenv{%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 22 \end{btHighlight}%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 23 \egroup
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 24 }
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 25 \newcommand{\bt@HL@box}[2][]{%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 26 \tikz[#1]{%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 27 \pgfpathrectangle{\pgfpoint{1pt}{0pt}}{\pgfpoint{\wd #2}{\ht #2}}%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 28 \pgfusepath{use as bounding box}%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 29 \node[anchor=base west, fill=orange!30,outer sep=0pt,inner xsep=1pt, inner ysep=0pt, rounded corners=3pt, minimum height=\ht\strutbox+1pt,#1]{\raisebox{1pt}{\strut}\strut\usebox{#2}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 30 }%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 31 }
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 32 \makeatother
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 33
86
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 34
315
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 35 % beamer stuff
459
+ − 36 \renewcommand{\slidecaption}{CFL 10, King's College London}
86
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 37 \newcommand{\bl}[1]{\textcolor{blue}{#1}}
315
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 38
86
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 39
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 40 \begin{document}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 41
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 42 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
315
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 43 \begin{frame}[t]
86
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 44 \frametitle{%
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 45 \begin{tabular}{@ {}c@ {}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 46 \\[-3mm]
459
+ − 47 \LARGE Compilers and \\[-2mm]
904
+ − 48 \LARGE Formal Languages\\[-3mm]
86
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 49 \end{tabular}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 50
904
+ − 51 \normalsize
86
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 52 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 53 \begin{tabular}{ll}
940
+ − 54 Email: & christian.urban at kcl.ac.uk\\
+ − 55 Office Hour: & Thurdays 15 -- 16\\
904
+ − 56 Location: & N7.07 (North Wing, Bush House)\\
+ − 57 Slides \& Progs: & KEATS\\
+ − 58 Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\
86
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 59 \end{tabular}
904
+ − 60 \end{center}
86
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 61
744
+ − 62 \begin{center}
+ − 63 \begin{tikzpicture}
+ − 64 \node[drop shadow,fill=white,inner sep=0pt]
+ − 65 {\footnotesize\rowcolors{1}{capri!10}{white}
+ − 66 \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline
+ − 67 1 Introduction, Languages & 6 While-Language \\
+ − 68 2 Regular Expressions, Derivatives & 7 Compilation, JVM \\
+ − 69 3 Automata, Regular Languages & 8 Compiling Functional Languages \\
+ − 70 4 Lexing, Tokenising & 9 Optimisations \\
+ − 71 5 Grammars, Parsing & \cellcolor{blue!50}10 LLVM \\ \hline
+ − 72 \end{tabular}%
+ − 73 };
+ − 74 \end{tikzpicture}
+ − 75 \end{center}
315
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 76 \end{frame}
864
+ − 77 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 78
+ − 79 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 80 \tikzstyle{sensor}=[draw, fill=blue!20, text width=3.8em, line width=1mm,
+ − 81 text centered, minimum height=2em,drop shadow]
+ − 82 \tikzstyle{ann} = [above, text width=4em, text centered]
+ − 83 \tikzstyle{sc} = [sensor, text width=7em, fill=red!20,
+ − 84 minimum height=6em, rounded corners, drop shadow,line width=1mm]
+ − 85
+ − 86 \begin{frame}[fragile,c]
+ − 87 \frametitle{LLVM: Overview}
+ − 88
+ − 89 \begin{tikzpicture}
+ − 90 % Validation Layer is the same except that there are a set of nodes and links which are added
+ − 91
+ − 92 \path (0,0) node (IR) [sc] {\textbf{LLVM-IR}\\ Optimisations};
+ − 93 \path (IR.west)+(-2.2,1.7) node (sou1) [sensor] {C++};
+ − 94 \path (IR.west)+(-2.2,0.5) node (sou2)[sensor] {C};
+ − 95 \path (IR.west)+(-2.2,-1.0) node (dots)[ann] {$\vdots$};
+ − 96 \path (IR.west)+(-2.2,-1.8) node (sou3)[sensor] {Haskell};
+ − 97
+ − 98 \path [draw,->,line width=1mm] (sou1.east) -- node [above] {} (IR.160);
+ − 99 \path [draw,->,line width=1mm] (sou2.east) -- node [above] {} (IR.180);
+ − 100 \path [draw,->,line width=1mm] (sou3.east) -- node [above] {} (IR.200);
+ − 101
+ − 102 \path (IR.east)+(2.2,2.0) node (tar1)[sensor] {x86};
+ − 103 \path (IR.east)+(2.2,0.8) node (tar2)[sensor] {ARM};
+ − 104 \path (IR.east)+(2.2,-0.4) node (tar3)[sensor] {MIPS};
+ − 105 \path (IR.east)+(2.2,-1.6) node (tar4)[sensor] {RISC};
+ − 106 \path (IR.east)+(2.2,-2.8) node (tar5)[sensor] {Power PC};
+ − 107 \path (IR.east)+(2.2,-4.2) node (dots2)[ann] {$\vdots$};
+ − 108
+ − 109 \path [draw,<-,line width=1mm] (tar1.west) -- node [above] {} (IR.10);
+ − 110 \path [draw,<-,line width=1mm] (tar2.west) -- node [above] {} (IR.5);
+ − 111 \path [draw,<-,line width=1mm] (tar3.west) -- node [above] {} (IR.0);
+ − 112 \path [draw,<-,line width=1mm] (tar4.west) -- node [above] {} (IR.-5);
+ − 113 \path [draw,<-,line width=1mm] (tar5.west) -- node [above] {} (IR.-10);
+ − 114
+ − 115 \end{tikzpicture}
+ − 116 \end{frame}
+ − 117 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 118
86
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 119
704
+ − 120 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 121 \begin{frame}[c,fragile]
818
+ − 122 \frametitle{Static Single-Assignment}
+ − 123
+ − 124 \bl{$(1 + a) + (3 + (b * 5))$}\bigskip\bigskip
+ − 125
+ − 126 \begin{lstlisting}[language=LLVMIR,numbers=left]
+ − 127 let tmp0 = add 1 a in
+ − 128 let tmp1 = mul b 5 in
+ − 129 let tmp2 = add 3 tmp1 in
+ − 130 let tmp3 = add tmp0 tmp2
+ − 131 in tmp3
+ − 132 \end{lstlisting}
+ − 133
+ − 134
+ − 135 \end{frame}
+ − 136 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 137
+ − 138 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 139 \begin{frame}[c,fragile]
+ − 140 \small
+ − 141
+ − 142 \mbox{}\bigskip\bigskip\bigskip
+ − 143
864
+ − 144 \begin{lstlisting}[language=llvm,numbers=left]
818
+ − 145 define i32 @fact (i32 %n) {
+ − 146 %tmp_20 = icmp eq i32 %n, 0
+ − 147 br i1 %tmp_20, label %if_branch_24, label %else_branch_25
+ − 148 if_branch_24:
+ − 149 ret i32 1
+ − 150 else_branch_25:
+ − 151 %tmp_22 = sub i32 %n, 1
+ − 152 %tmp_23 = call i32 @fact (i32 %tmp_22)
+ − 153 %tmp_21 = mul i32 %n, %tmp_23
+ − 154 ret i32 %tmp_21
+ − 155 }
+ − 156 \end{lstlisting}
+ − 157
+ − 158 \begin{lstlisting}[language={},numbers=none]
+ − 159 def fact(n) = if n == 0 then 1 else n * fact(n - 1)
+ − 160 \end{lstlisting}
+ − 161 \end{frame}
+ − 162 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 163
864
+ − 164 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 165 \begin{frame}[fragile,c]
+ − 166 \frametitle{LLVM Types}
+ − 167
+ − 168 \tt
+ − 169 \begin{center}
+ − 170 \begin{tabular}{ll}
+ − 171 boolean & i1 \\
+ − 172 byte & i8 \\
+ − 173 short & i16\\
+ − 174 char & i16\\
+ − 175 integer & i32\\
+ − 176 long & i64\\
+ − 177 float & float\\
+ − 178 double & double\\
+ − 179 *\_ & pointer to \\
+ − 180 **\_ & pointer to a pointer to\\
+ − 181 \mbox{}[\_] & arrays of\\
+ − 182 \end{tabular}
+ − 183 \end{center}
+ − 184
+ − 185 \end{frame}
+ − 186 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 187
+ − 188
818
+ − 189 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 190 \begin{frame}[c,fragile]
+ − 191
+ − 192
+ − 193 \begin{lstlisting}[language=LLVM,numbers=none]
+ − 194 br i1 %var, label %if_br, label %else_br
+ − 195
+ − 196 icmp eq i32 %x, %y ; for equal
+ − 197 icmp sle i32 %x, %y ; signed less or equal
+ − 198 icmp slt i32 %x, %y ; signed less than
+ − 199 icmp ult i32 %x, %y ; unsigned less than
+ − 200
+ − 201 %var = call i32 @foo(...args...)
+ − 202 \end{lstlisting}
+ − 203
+ − 204 \end{frame}
+ − 205 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 206
864
+ − 207 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 208 \begin{frame}[fragile,c]
+ − 209 \frametitle{Abstract Syntax Trees}
+ − 210 \footnotesize
+ − 211
+ − 212 \begin{lstlisting}[language=Scala,numbers=none,xleftmargin=-3mm]
+ − 213 // Fun language (expressions)
+ − 214 abstract class Exp
+ − 215 abstract class BExp
+ − 216
+ − 217 case class Call(name: String, args: List[Exp]) extends Exp
+ − 218 case class If(a: BExp, e1: Exp, e2: Exp) extends Exp
+ − 219 case class Write(e: Exp) extends Exp
+ − 220 case class Var(s: String) extends Exp
+ − 221 case class Num(i: Int) extends Exp
+ − 222 case class Aop(o: String, a1: Exp, a2: Exp) extends Exp
+ − 223 case class Sequence(e1: Exp, e2: Exp) extends Exp
+ − 224 case class Bop(o: String, a1: Exp, a2: Exp) extends BExp
+ − 225 \end{lstlisting}
+ − 226
+ − 227 \end{frame}
+ − 228 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 229
+ − 230 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 231 \begin{frame}[fragile,c]
+ − 232 \frametitle{K-(Intermediate)Language}
+ − 233 \footnotesize
+ − 234
+ − 235 \begin{lstlisting}[language=Scala,numbers=none,xleftmargin=-3mm]
+ − 236 abstract class KExp
+ − 237 abstract class KVal
+ − 238
+ − 239 // K-Values
+ − 240 case class KVar(s: String) extends KVal
+ − 241 case class KNum(i: Int) extends KVal
+ − 242 case class Kop(o: String, v1: KVal, v2: KVal) extends KVal
+ − 243 case class KCall(o: String, vrs: List[KVal]) extends KVal
+ − 244 case class KWrite(v: KVal) extends KVal
+ − 245
+ − 246 // K-Expressions
+ − 247 case class KIf(x1: String, e1: KExp, e2: KExp) extends KExp
+ − 248 case class KLet(x: String, v: KVal, e: KExp) extends KExp
+ − 249 case class KReturn(v: KVal) extends KExp
+ − 250 \end{lstlisting}
+ − 251
+ − 252 \end{frame}
+ − 253 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 254
+ − 255 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 256 \begin{frame}[fragile,c]
+ − 257 \frametitle{KLet}
+ − 258
+ − 259 \begin{lstlisting}[language=LLVM]
+ − 260 tmp0 = add 1 a
+ − 261 tmp1 = mul b 5
+ − 262 tmp2 = add 3 tmp1
+ − 263 tmp3 = add tmp0 tmp2
+ − 264 \end{lstlisting}
+ − 265
+ − 266 \begin{lstlisting}[language=LLVMIR]
+ − 267 KLet tmp0 , add 1 a in
+ − 268 KLet tmp1 , mul b 5 in
+ − 269 KLet tmp2 , add 3 tmp1 in
+ − 270 KLet tmp3 , add tmp0 tmp2 in
+ − 271 ...
+ − 272 \end{lstlisting}
+ − 273
+ − 274 \begin{lstlisting}[language=Scala,numbers=none]
+ − 275 case class KLet(x: String, e1: KVal, e2: KExp)
+ − 276 \end{lstlisting}
+ − 277
+ − 278 \end{frame}
+ − 279 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 280
+ − 281 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 282 \begin{frame}[fragile,c]
+ − 283 \frametitle{KLet}
+ − 284
+ − 285 \begin{lstlisting}[language=LLVM]
+ − 286 tmp0 = add 1 a
+ − 287 tmp1 = mul b 5
+ − 288 tmp2 = add 3 tmp1
+ − 289 tmp3 = add tmp0 tmp2
+ − 290 \end{lstlisting}
+ − 291
+ − 292 \begin{lstlisting}[language=LLVMIR]
+ − 293 let tmp0 = add 1 a in
+ − 294 let tmp1 = mul b 5 in
+ − 295 let tmp2 = add 3 tmp1 in
+ − 296 let tmp3 = add tmp0 tmp2 in
+ − 297 ...
+ − 298 \end{lstlisting}
+ − 299
+ − 300 \begin{lstlisting}[language=Scala,numbers=none]
+ − 301 case class KLet(x: String, e1: KVal, e2: KExp)
+ − 302 \end{lstlisting}
+ − 303
+ − 304 \end{frame}
+ − 305 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 306
+ − 307
+ − 308 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 309 \begin{frame}[fragile,c]
+ − 310 \frametitle{CPS-Translation}
+ − 311 \small
+ − 312
+ − 313 \begin{lstlisting}[language=Scala,numbers=none]
+ − 314 def CPS(e: Exp)(k: KVal => KExp) : KExp =
+ − 315 e match { ... }
+ − 316 \end{lstlisting}
+ − 317 \bigskip\bigskip
+ − 318
+ − 319 the continuation \texttt{k} can be thought of:\medskip
+ − 320
+ − 321 \small
+ − 322 \begin{lstlisting}[language=LLVMIR,numbers=none,xleftmargin=30mm,escapeinside={(*@}{@*)}]
+ − 323 let tmp0 = add 1 a in
+ − 324 let tmp1 = mul (*@$\Box$@*) 5 in
+ − 325 let tmp2 = add 3 tmp1 in
+ − 326 let tmp3 = add tmp0 tmp2 in
+ − 327 KReturn tmp3
+ − 328 \end{lstlisting}
+ − 329
+ − 330 \end{frame}
+ − 331 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 332
+ − 333
+ − 334
818
+ − 335 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 336 \begin{frame}[c,fragile]
704
+ − 337
+ − 338
+ − 339 \begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-6mm]
+ − 340 def fact(n: Int) : Int = {
+ − 341 if (n == 0) 1 else n * fact(n - 1)
+ − 342 }
+ − 343
+ − 344
+ − 345 def factC(n: Int, ret: Int => Int) : Int = {
+ − 346 if (n == 0) ret(1)
+ − 347 else factC(n - 1, x => ret(n * x))
+ − 348 }
+ − 349
+ − 350 fact(10)
+ − 351 factC(10, identity)
+ − 352 \end{lstlisting}
+ − 353 \end{frame}
+ − 354 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 355
+ − 356 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 357 \begin{frame}[c,fragile]
+ − 358
+ − 359
+ − 360 \begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-6mm]
+ − 361 def fibC(n: Int, ret: Int => Int) : Int = {
+ − 362 if (n == 0 || n == 1) ret(1) else
+ − 363 fibC(n - 1,
+ − 364 r1 => fibC(n - 2,
+ − 365 r2 => ret(r1 + r2)))
+ − 366 }
+ − 367
+ − 368 fibC(10, identity)
+ − 369 \end{lstlisting}
+ − 370 \end{frame}
+ − 371 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 372
904
+ − 373 \begin{frame}<1-15>[c]
704
+ − 374
904
+ − 375 \end{frame}
704
+ − 376
+ − 377
543
+ − 378
+ − 379 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 380 \begin{frame}[c]
+ − 381
704
+ − 382 \Large\bf Are there more strings in \\ \hfill\bl{$L(a^*)$} or
617
+ − 383 \bl{$L((a + b)^*)$}?
543
+ − 384
+ − 385 \end{frame}
+ − 386 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 387
+ − 388 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 389 \begin{frame}[c]
704
+ − 390 \frametitle{Can you remember this HW?}
+ − 391
+ − 392 \begin{itemize}
+ − 393 \item (1) How many basic regular expressions are there to match
+ − 394 the string \bl{$abcd$}?
+ − 395 \item (2) How many if they cannot include
+ − 396 \bl{$\ONE$} and \bl{$\ZERO$}?
+ − 397 \item (3) How many if they are also not
+ − 398 allowed to contain stars?
+ − 399 \item (4) How many if they are also
+ − 400 not allowed to contain \bl{$\_ + \_$}?
+ − 401 \end{itemize}
+ − 402
+ − 403 \end{frame}
+ − 404 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 405
+ − 406
+ − 407 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 408 \begin{frame}[c]
543
+ − 409
+ − 410 \Large\bf There are more problems, than there are
+ − 411 programs.\bigskip\bigskip\pause\\
+ − 412
+ − 413 There must be a problem for which there is no program.
+ − 414 \end{frame}
+ − 415 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 416
+ − 417 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 418 \begin{frame}[c]
+ − 419 \frametitle{Subsets}
+ − 420
+ − 421 \Large
+ − 422 If \bl{$A \subseteq B$} then \bl{$A$} has fewer or equal elements
+ − 423 than \bl{$B$}\bigskip\bigskip
+ − 424
+ − 425 \Large
+ − 426 \bl{$A \subseteq B$} and \bl{$B \subseteq A$}\bigskip
+ − 427
+ − 428 then \bl{$A = B$}
+ − 429 \end{frame}
+ − 430 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 431
+ − 432
+ − 433 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 434 \begin{frame}[c]
+ − 435
+ − 436 \begin{center}
+ − 437 \begin{tikzpicture}
+ − 438
+ − 439 \draw (-4,2.5) node [scale=2.5] (X)
+ − 440 {\begin{tabular}{l}
+ − 441 $\{$
+ − 442 \!\includegraphics[scale=0.02]{../pics/o1.jpg},
+ − 443 \includegraphics[scale=0.02]{../pics/o2.jpg},
+ − 444 \!\includegraphics[scale=0.02]{../pics/o3.jpg},
+ − 445 \includegraphics[scale=0.02]{../pics/o4.jpg},
+ − 446 \!\includegraphics[scale=0.027]{../pics/o5.jpg}
+ − 447 $\}$
+ − 448 \end{tabular}};
+ − 449
+ − 450 \draw (-5.6,-2.5) node [scale=2.5] (Y)
+ − 451 {\begin{tabular}{l}
+ − 452 $\{$
+ − 453 \!\includegraphics[scale=0.059]{../pics/a1.jpg},
+ − 454 \includegraphics[scale=0.048]{../pics/a2.jpg},
+ − 455 \includegraphics[scale=0.02]{../pics/a3.jpg}
+ − 456 $\}$
+ − 457 \end{tabular}};
+ − 458
+ − 459 \draw (0,1.5) node (X1) {5 elements};
+ − 460 \draw (0,-3.5) node (y1) {3 elements};
+ − 461 \end{tikzpicture}
+ − 462 \end{center}
+ − 463
+ − 464 \end{frame}
+ − 465 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 466
+ − 467 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 468 \begin{frame}[c]
+ − 469 \frametitle{Newton vs Feynman}
+ − 470
+ − 471 \begin{center}
+ − 472 \begin{tabular}{cc}
+ − 473 \includegraphics[scale=0.2]{../pics/newton.jpg} &
+ − 474 \includegraphics[scale=0.2]{../pics/feynman.jpg}\\
+ − 475 classical physics & quantum physics
+ − 476 \end{tabular}
+ − 477 \end{center}
+ − 478 \end{frame}
+ − 479 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 480
+ − 481 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 482 \begin{frame}[c]
+ − 483 \frametitle{The Goal of the Talk}
+ − 484 \large
+ − 485 \begin{itemize}
+ − 486 \item show you that something very unintuitive happens with very large sets
+ − 487 \bigskip\bigskip
+ − 488
+ − 489 \item convince you that there are more {\bf problems} than {\bf programs}
+ − 490 \end{itemize}
+ − 491 \end{frame}
+ − 492 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 493
+ − 494 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 495 \begin{frame}[t]
+ − 496 %
+ − 497 \begin{center}
+ − 498 \begin{tikzpicture}
+ − 499
+ − 500 \draw (-5,2.5) node [scale=2.3] (X)
+ − 501 {\begin{tabular}{@ {\hspace{-3mm}}l}
+ − 502 \bl{$B$ $=$ $\{$
+ − 503 \!\includegraphics[scale=0.02]{../pics/o1.jpg},
+ − 504 \includegraphics[scale=0.02]{../pics/o2.jpg},
+ − 505 \!\includegraphics[scale=0.02]{../pics/o3.jpg},
+ − 506 \includegraphics[scale=0.02]{../pics/o4.jpg},
+ − 507 \!\includegraphics[scale=0.027]{../pics/o5.jpg}
+ − 508 $\}$}
+ − 509 \end{tabular}};
+ − 510
+ − 511 \draw (-6.6,-0.5) node [scale=2.3] (Y)
+ − 512 {\begin{tabular}{@ {\hspace{-3mm}}l}
+ − 513 \bl{$A$ $=$ $\{$
+ − 514 \!\includegraphics[scale=0.059]{../pics/a1.jpg},
+ − 515 \includegraphics[scale=0.048]{../pics/a2.jpg},
+ − 516 \includegraphics[scale=0.02]{../pics/a3.jpg}
+ − 517 $\}$}
+ − 518 \end{tabular}};
+ − 519
+ − 520 \only<1>{\draw (-5, -3) node[scale=2]
+ − 521 {\bl{$|A|$ $=$ $5$}, \bl{$|B|$ $=$ $3$}};}
+ − 522 \only<2>{
+ − 523 \draw [->, line width=1mm, red] (-7.4, 0.2) -- (-6.1, 2.1);
+ − 524 \draw [->, line width=1mm, red] (-5.8, 0.2) -- (-3.1, 2.1);
+ − 525 \draw [->, line width=1mm, red] (-4.5, 0.2) -- (-7.6, 2.1);
+ − 526 \draw (-5, -3) node[scale=2] {then \bl{$|A|$ $\le$ $|B|$}};
+ − 527 }
+ − 528 \only<3>{
+ − 529 \draw [<-, line width=1mm, red] (-7.5, 0.2) -- (-6.1, 2.1);
+ − 530 \draw [<-, line width=1mm, red] (-7.3, 0.2) -- (-3.1, 2.1);
+ − 531 \draw [<-, line width=1mm, red] (-6, 0.2) -- (-7.5, 2.1);
+ − 532 \draw [<-, line width=1mm, red] (-4.5, 0.2) -- (-4.5, 2.1);
+ − 533 \draw [<-, line width=1mm, red] (-4.3, 0.2) -- (-1.3, 2.1);
+ − 534
+ − 535 \draw (-5, -3) node[scale=1.5] {\small{}for \bl{$=$}
+ − 536 has to be a {\bf one-to-one} mapping};
+ − 537 }
+ − 538
+ − 539
+ − 540 \end{tikzpicture}
+ − 541 \end{center}
+ − 542
+ − 543 \end{frame}
+ − 544 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 545
+ − 546 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 547 \begin{frame}[c]
+ − 548 \frametitle{Cardinality}
+ − 549
+ − 550 \Large
+ − 551 \bl{$|A|$} $\dn$ ``how many elements''\bigskip\\
+ − 552
+ − 553 \bl{$A \subseteq B \Rightarrow |A| \leq |B|$}\bigskip\\\pause
+ − 554
+ − 555 if there is an injective function \bl{$f: A \rightarrow B$} then \bl{$|A| \leq |B|$}\
+ − 556
+ − 557 \begin{center}
+ − 558 \bl{\large$\forall x y.\; f(x) = f(y) \Rightarrow x = y$}
+ − 559 \end{center}
+ − 560 \end{frame}
+ − 561 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 562
+ − 563 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 564 \begin{frame}[t]
+ − 565
+ − 566 \begin{center}
+ − 567 \begin{tikzpicture}
+ − 568
+ − 569 \draw (-6.6,2.5) node [scale=2.3] (X)
+ − 570 {\begin{tabular}{@ {\hspace{-3mm}}l}
+ − 571 $A$ $=$ $\{$
+ − 572 \!\includegraphics[scale=0.02]{../pics/o1.jpg},
+ − 573 \includegraphics[scale=0.02]{../pics/o2.jpg},
+ − 574 \!\includegraphics[scale=0.02]{../pics/o3.jpg}
+ − 575 $\}$
+ − 576 \end{tabular}};
+ − 577
+ − 578 \draw (-6.6,-0.5) node [scale=2.3] (Y)
+ − 579 {\begin{tabular}{@ {\hspace{-3mm}}l}
+ − 580 $B$ $=$ $\{$
+ − 581 \!\includegraphics[scale=0.059]{../pics/a1.jpg},
+ − 582 \includegraphics[scale=0.048]{../pics/a2.jpg},
+ − 583 \includegraphics[scale=0.02]{../pics/a3.jpg}
+ − 584 $\}$
+ − 585 \end{tabular}};
+ − 586 \onslide<3->{\draw (-7, -3) node[scale=1.5]
+ − 587 {then \bl{$|A|$ \alert{$=$} $|B|$}};}
+ − 588 \only<1>{
+ − 589 \draw [->, line width=1mm, red] (-7.4, 0.2) -- (-6.1, 2.1);
+ − 590 \draw [->, line width=1mm, red] (-5.8, 0.2) -- (-4.3, 2.1);
+ − 591 \draw [->, line width=1mm, red] (-4.5, 0.2) -- (-7.6, 2.1);
+ − 592 }
+ − 593 \only<2->{
+ − 594 \draw [<-, line width=1mm, blue] (-7.5, 0.2) -- (-7.5, 2.1);
+ − 595 \draw [<-, line width=1mm, blue] (-5.8, 0.2) -- (-4.3, 2.1);
+ − 596 \draw [<-, line width=1mm, blue] (-4.5, 0.2) -- (-6.1, 2.1);
+ − 597 }
+ − 598
+ − 599
+ − 600 \end{tikzpicture}
+ − 601 \end{center}
+ − 602
+ − 603 \end{frame}
+ − 604 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
315
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 605
86
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 606
543
+ − 607 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 608 \begin{frame}[c]
+ − 609 \frametitle{Natural Numbers}
+ − 610
+ − 611 \Large
+ − 612 \bl{$\mathbb{N}$} \bl{$\dn$} \bl{$\{0, 1, 2, 3, .......\}$}\bigskip\pause
+ − 613
+ − 614 \bl{$A$} is \alert{countable} iff \bl{$|A| \leq |\mathbb{N}|$}
+ − 615
+ − 616 \end{frame}
+ − 617 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 618
+ − 619 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 620 \begin{frame}[c]
+ − 621 \frametitle{First Question}
+ − 622
+ − 623 \Large
+ − 624 \bl{$|\mathbb{N} - \{0\}| \;\;\;\alert{?}\;\;\; |\mathbb{N}| $}\bigskip\bigskip
+ − 625
+ − 626 \large
+ − 627 \bl{$\geq$} or \bl{$\leq$} or \bl{$=$} ?
+ − 628 \bigskip\bigskip\bigskip\pause
+ − 629
+ − 630 \bl{$x$ $\mapsto$ $x + 1$},\\ \bl{$|\mathbb{N} - \{0\}|$ $=$
+ − 631 $|\mathbb{N}|$}
+ − 632 \end{frame}
+ − 633 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 634
+ − 635 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 636 \mode<presentation>{
+ − 637 \begin{frame}[c]
+ − 638
+ − 639 \Large
+ − 640 \bl{$|\mathbb{N} - \{0, 1\}| \;\;\;\alert{?}\;\;\; |\mathbb{N}| $}\bigskip\pause
+ − 641
+ − 642 \bl{$|\mathbb{N} - \mathbb{O}| \;\;\;\alert{?}\;\;\; |\mathbb{N}| $}\bigskip\bigskip
+ − 643
+ − 644 \normalsize
+ − 645 \bl{$\mathbb{O}$} $\dn$ odd numbers\quad \bl{$\{1,3,5......\}$}\\ \pause
+ − 646 \bl{$\mathbb{E}$} $\dn$ even numbers\quad \bl{$\{0,2,4......\}$}\\
+ − 647 \end{frame}}
+ − 648 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 649
+ − 650 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 651 \mode<presentation>{
+ − 652 \begin{frame}[c]
+ − 653
+ − 654 \Large
+ − 655 \bl{$|\mathbb{N} \cup \mathbb{-N}| \;\;\;\alert{?}\;\;\; |\mathbb{N}| $}\bigskip\bigskip
+ − 656
+ − 657
+ − 658 \normalsize
+ − 659 \bl{$\mathbb{\phantom{-}N}$} $\dn$ positive numbers\quad \bl{$\{0,1,2,3,......\}$}\\
+ − 660 \bl{$\mathbb{-N}$} $\dn$ negative numbers\quad \bl{$\{0,-1,-2,-3,......\}$}\\
+ − 661 \end{frame}}
+ − 662 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 663
+ − 664 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 665 \mode<presentation>{
+ − 666 \begin{frame}[c]
+ − 667
+ − 668 \Large
+ − 669 \bl{$A$} is \alert{countable} if there exists an injective \bl{$f : A \rightarrow \mathbb{N}$}\bigskip
+ − 670
+ − 671 \bl{$A$} is \alert{uncountable} if there does not exist an injective \bl{$f : A \rightarrow \mathbb{N}$}\bigskip\bigskip
+ − 672
+ − 673
+ − 674 countable: \bl{$|A| \leq |\mathbb{N}|$}\\
+ − 675 uncountable: \bl{$|A| > |\mathbb{N}|$}\pause\bigskip
+ − 676
+ − 677
+ − 678 Does there exist such an \bl{$A$} ?
+ − 679
+ − 680 \end{frame}}
+ − 681 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 682
+ − 683 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 684 \mode<presentation>{
+ − 685 \begin{frame}[c]
+ − 686 \frametitle{Hilbert's Hotel}
+ − 687
+ − 688 \begin{center}
+ − 689 \includegraphics[scale=0.8]{../pics/hilberts_hotel.jpg}
+ − 690 \end{center}
+ − 691
+ − 692 \begin{itemize}
+ − 693 \item \ldots has as many rooms as there are natural numbers
+ − 694 \end{itemize}
+ − 695
+ − 696 \end{frame}}
+ − 697 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 698
+ − 699
+ − 700 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 701 \begin{frame}[t]
+ − 702 \frametitle{\begin{tabular}{c}Real Numbers between\\[-2mm] 0 and 1\end{tabular}}
+ − 703
+ − 704 \begin{center}
+ − 705 \begin{tikzpicture}
+ − 706 \draw [fill, color=black!50] (1,4) rectangle (2, 3);
+ − 707 \draw [fill, color=black!50] (2,3) rectangle (3, 2);
+ − 708 \draw [fill, color=black!50] (3,2) rectangle (4, 1);
+ − 709 \draw [fill, color=black!50] (4,1) rectangle (5, 0);
+ − 710 \draw (0, 0) grid (8, 5);
+ − 711 \draw [line width = 1.mm] (1,0) -- (1, 5);
+ − 712 \draw [line width = 1.mm] (0, 4) -- (8, 4);
+ − 713 \draw (0.5,3.5) node {$1$};
+ − 714 \draw (0.5,2.5) node {$2$};
+ − 715 \draw (0.5,1.5) node {$3$};
+ − 716 \draw (0.5,0.5) node {$4$};
+ − 717
+ − 718 \draw (1.5,3.5) node {\only<1>{$3$}\only<2->{$4$}};
+ − 719 \draw (2.5,3.5) node {$3$};
+ − 720 \draw (3.5,3.5) node {$3$};
+ − 721 \draw (4.5,3.5) node {$3$};
+ − 722 \draw (5.5,3.5) node {$3$};
+ − 723 \draw (6.5,3.5) node {$3$};
+ − 724 \draw (7.5,3.5) node {$\ldots$};
+ − 725
+ − 726 \draw (1.5,2.5) node {$1$};
+ − 727 \draw (2.5,2.5) node {\only<1-2>{$2$}\only<3->{$3$}};
+ − 728 \draw (3.5,2.5) node {$3$};
+ − 729 \draw (4.5,2.5) node {$4$};
+ − 730 \draw (5.5,2.5) node {$5$};
+ − 731 \draw (6.5,2.5) node {$6$};
+ − 732 \draw (7.5,2.5) node {$7$};
+ − 733
+ − 734 \draw (1.5,1.5) node {$0$};
+ − 735 \draw (2.5,1.5) node {$1$};
+ − 736 \draw (3.5,1.5) node {\only<1-3>{$0$}\only<4->{$1$}};
+ − 737 \draw (4.5,1.5) node {$1$};
+ − 738 \draw (5.5,1.5) node {$0$};
+ − 739 \draw (6.5,1.5) node {$\ldots$};
+ − 740
+ − 741 \draw (1.5,0.5) node {$7$};
+ − 742 \draw (2.5,0.5) node {$8$};
+ − 743 \draw (3.5,0.5) node {$5$};
+ − 744 \draw (4.5,0.5) node {\only<1-4>{$3$}\only<5->{$4$}};
+ − 745 \draw (5.5,0.5) node {$9$};
+ − 746 \draw (6.5,0.5) node {$\ldots$};
+ − 747
+ − 748 \draw (1.5,-0.5) node {$\ldots$};
+ − 749 \draw (8.5,3.5) node {$\ldots$};
+ − 750 \end{tikzpicture}
+ − 751 \end{center}
+ − 752 \mbox{}\\[-20mm]\mbox{}
+ − 753
+ − 754 \onslide<6->{
+ − 755 \begin{center}
+ − 756 \Large\bl{$|\mathbb{N}| < |R|$}
+ − 757 \end{center}
+ − 758 }
+ − 759
+ − 760 \end{frame}
+ − 761 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 762
+ − 763
+ − 764 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 765 \mode<presentation>{
+ − 766 \begin{frame}[t]
+ − 767 \frametitle{The Set of Problems}
+ − 768
+ − 769 $\aleph_0$
+ − 770
+ − 771 \begin{center}
+ − 772 \begin{tikzpicture}
+ − 773 \draw [fill, color=black!50] (1,4) rectangle (2, 3);
+ − 774 \draw [fill, color=black!50] (2,3) rectangle (3, 2);
+ − 775 \draw [fill, color=black!50] (3,2) rectangle (4, 1);
+ − 776 \draw [fill, color=black!50] (4,1) rectangle (5, 0);
+ − 777 \draw (0, 0) grid (8, 5);
+ − 778 \draw [line width = 1.mm] (1,0) -- (1, 5);
+ − 779 \draw [line width = 1.mm] (0, 4) -- (8, 4);
+ − 780 \draw (0.5,3.5) node {$1$};
+ − 781 \draw (0.5,2.5) node {$2$};
+ − 782 \draw (0.5,1.5) node {$3$};
+ − 783 \draw (0.5,0.5) node {$4$};
+ − 784
+ − 785 \draw (1.5,4.5) node {$0$};
+ − 786 \draw (2.5,4.5) node {$1$};
+ − 787 \draw (3.5,4.5) node {$2$};
+ − 788 \draw (4.5,4.5) node {$3$};
+ − 789 \draw (5.5,4.5) node {$4$};
+ − 790 \draw (6.5,4.5) node {$5$};
+ − 791 \draw (7.5,4.5) node {$\ldots$};
+ − 792
+ − 793 \draw (1.5,3.5) node {$0$};
+ − 794 \draw (2.5,3.5) node {$1$};
+ − 795 \draw (3.5,3.5) node {$0$};
+ − 796 \draw (4.5,3.5) node {$1$};
+ − 797 \draw (5.5,3.5) node {$0$};
+ − 798 \draw (6.5,3.5) node {$1$};
+ − 799 \draw (7.5,3.5) node {$\ldots$};
+ − 800
+ − 801 \draw (1.5,2.5) node {$0$};
+ − 802 \draw (2.5,2.5) node {$0$};
+ − 803 \draw (3.5,2.5) node {$0$};
+ − 804 \draw (4.5,2.5) node {$1$};
+ − 805 \draw (5.5,2.5) node {$1$};
+ − 806 \draw (6.5,2.5) node {$0$};
+ − 807 \draw (7.5,2.5) node {$0$};
+ − 808
+ − 809 \draw (1.5,1.5) node {$0$};
+ − 810 \draw (2.5,1.5) node {$0$};
+ − 811 \draw (3.5,1.5) node {$0$};
+ − 812 \draw (4.5,1.5) node {$0$};
+ − 813 \draw (5.5,1.5) node {$0$};
+ − 814 \draw (6.5,1.5) node {$\ldots$};
+ − 815
+ − 816 \draw (1.5,0.5) node {$1$};
+ − 817 \draw (2.5,0.5) node {$1$};
+ − 818 \draw (3.5,0.5) node {$0$};
+ − 819 \draw (4.5,0.5) node {$1$};
+ − 820 \draw (5.5,0.5) node {$1$};
+ − 821 \draw (6.5,0.5) node {$\ldots$};
+ − 822
+ − 823 \draw (1.5,-0.5) node {$\ldots$};
+ − 824 \draw (8.5,3.5) node {$\ldots$};
+ − 825
+ − 826 \end{tikzpicture}
+ − 827 \end{center}
+ − 828
+ − 829
+ − 830 \onslide<2>{
+ − 831 \begin{center}
+ − 832 \large \bl{|Progs| $=$ $|\mathbb{N}|$ $<$ |Probs|}
+ − 833 \end{center}
+ − 834 }
+ − 835
+ − 836
+ − 837 \end{frame}}
+ − 838 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 839
+ − 840
+ − 841 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 842 \mode<presentation>{
+ − 843 \begin{frame}[c]
+ − 844 \frametitle{Halting Problem}
+ − 845
+ − 846 \large
+ − 847 Assume a program \bl{$H$} that decides for all programs \bl{$A$} and all
+ − 848 input data \bl{$D$} whether\bigskip
+ − 849
+ − 850 \begin{itemize}
+ − 851 \item \bl{$H(A, D) \dn 1$} iff \bl{$A(D)$} terminates
+ − 852 \item \bl{$H(A, D) \dn 0$} otherwise
+ − 853 \end{itemize}
+ − 854
+ − 855 \end{frame}}
+ − 856 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 857
+ − 858 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 859 \mode<presentation>{
+ − 860 \begin{frame}[c]
+ − 861 \frametitle{Halting Problem (2)}
+ − 862
+ − 863 \large
+ − 864 Given such a program \bl{$H$} define the following program \bl{$C$}:
+ − 865 for all programs \bl{$A$}\bigskip
+ − 866
+ − 867 \begin{itemize}
+ − 868 \item \bl{$C(A) \dn 0$} iff \bl{$H(A, A) = 0$}
+ − 869 \item \bl{$C(A) \dn$ loops} otherwise
+ − 870 \end{itemize}
+ − 871
+ − 872 \end{frame}}
+ − 873 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 874
+ − 875 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 876 \mode<presentation>{
+ − 877 \begin{frame}[c]
+ − 878 \frametitle{Contradiction}
+ − 879
+ − 880
+ − 881 \bl{$H(C, C)$} is either \bl{$0$} or \bl{$1$}.
+ − 882
+ − 883 \begin{itemize}
+ − 884 \item \bl{$H(C, C) = 1$} $\stackrel{\text{def}\,H}{\Rightarrow}$ \bl{$C(C)\downarrow$} $\stackrel{\text{def}\,C}{\Rightarrow}$ \bl{$H(C, C)=0$}
+ − 885 \item \bl{$H(C, C) = 0$} $\stackrel{\text{def}\,H}{\Rightarrow}$ \bl{$C(C)$} loops $\stackrel{\text{def}\,C}{\Rightarrow}$\\
+ − 886 \hspace{7cm}\bl{$H(C, C)=1$}
+ − 887 \end{itemize}
+ − 888
+ − 889 Contradiction in both cases. So \bl{$H$} cannot exist.
+ − 890
+ − 891 \end{frame}}
+ − 892 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 893
+ − 894 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 895 \mode<presentation>{
+ − 896 \begin{frame}[c]
+ − 897 \frametitle{Take Home Points}
+ − 898 \large
+ − 899
+ − 900 \begin{itemize}
+ − 901 \item there are sets that are more infinite than others\bigskip
+ − 902 \item even with the most powerful computer we can imagine, there
+ − 903 are problems that cannot be solved by any program\bigskip\bigskip
+ − 904
+ − 905 \item in CS we actually hit quite often such problems (halting problem)
+ − 906 \end{itemize}
+ − 907
+ − 908 \end{frame}}
+ − 909 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
864
+ − 910
+ − 911 \begin{frame}<1-20>[c]
+ − 912 \end{frame}
+ − 913
+ − 914
959
+ − 915 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 916 \begin{frame}[c]
+ − 917 \frametitle{Big Thank You!}
+ − 918 \large
+ − 919
+ − 920 \only<1>{%
+ − 921 \begin{itemize}
+ − 922 \item<-1> It is always fun to learn new things in CFL
+ − 923 \item<-1> I want to add Higher-Order Functions and Algebraic Datatypes
+ − 924 to Fun
+ − 925 \end{itemize}}
+ − 926
+ − 927 \only<2->{%
+ − 928 \begin{itemize}
+ − 929 \item<2-> Thanks for ALL the EoY feedback:\medskip\bigskip
+ − 930
+ − 931 \begin{minipage}{13cm}
+ − 932 \begin{quote}\it
+ − 933 ``If all modules were as good as this one I would start recommending KCL over basically every single university instead of suggesting people look somewhere else.''
+ − 934 \end{quote}
+ − 935 \end{minipage}
+ − 936 \end{itemize}}
+ − 937
+ − 938 \hfill\includegraphics[scale=0.12]{thanks.png}
+ − 939
+ − 940 \end{frame}
+ − 941 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 942
+ − 943
86
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 944 \end{document}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 945
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 946 %%% Local Variables:
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 947 %%% mode: latex
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 948 %%% TeX-master: t
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 949 %%% End:
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
+ − 950