1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
|
\documentclass{beamer}
\usecolortheme{seagull}
\usefonttheme{structurebold}
\usepackage[utf8]{inputenc}
\usepackage[swedish]{babel}
\usepackage{minted} % code with syntax highlighting
\usepackage[normalem]{ulem} % strikethrought
\usepackage{url}
\title{Seminarium 02}
\subtitle{Experimentering}
\date{14 september 2021}
\setlength{\parskip}{1em}
\renewcommand{\baselinestretch}{1.2}
\AtBeginSection[] % Do nothing for \section*
{
\begin{frame}<beamer>
\frametitle{Planering}
\tableofcontents[currentsection]
\end{frame}
}
\begin{document}
\frame{\titlepage}
\section*{Introduktion}
\begin{frame}
\frametitle{Seminarieformen}
Mer fokus på eget kodskrivande än ''Ett steg i taget'', men mer konkret än
''Diskussion och analys''.
Fritt fram att byta spår under terminen.
Innan seminariet: läs förberedelsematerialet och försök er på uppgifterna.
Skicka in lösningar så vi kan diskutera i helklass:
\texttt{seminarium.sörnäs.se}. Anonymt, sålänge du inte skriver ditt namn i
koden :)
\end{frame}
\begin{frame}
\frametitle{Dagens seminarium}
\begin{itemize}
\item Uppgift: iteration
\item \sout{Fysisk iteration}
\item Analys: tupler och rekursion
\item Uppgift: palindrom
\item Analys: dictionaries
\item Diskussion
\end{itemize}
\end{frame}
\begin{frame}[fragile]
\frametitle{Uppgift: \texttt{find\_uncut}}
Om \texttt{True} är en klippt ruta och \texttt{False} är en oklippt ruta,
returnera en lista över alla oklippta rutors koordinater.
\begin{minted}{python}
>>> find_uncut([
... [True, False, True, False],
... [False, False, True, True],
... [True, False, False, True],
... [False, True, True, True]
... ])
...
[(1, 0), (3, 0), (0, 1), (1, 1), (2, 1), (2, 2), (0, 3)]
\end{minted}
\texttt{seminarium.sörnäs.se}
\end{frame}
\begin{frame}[fragile]
\frametitle{\texttt{min\_max}}
\begin{columns}
\begin{column}{0.48\textwidth}
\begin{minted}[fontsize=\scriptsize,linenos]{python}
def min_max(seq):
if not seq:
return (None, None)
if len(seq) == 1:
return (seq[0], seq[0])
(l_min, l_max) = min_max(seq[1:])
if seq[0] < l_min:
l_min = seq[0]
if seq[0] > l_max:
l_max = seq[0]
print("min: ", l_min)
print("max: ", l_max)
return (l_min, l_max)
\end{minted}
% Basfall 1: tom lista => (None, None)
% Basfall 2: [elem] => (elem, elem)
% (l_min, l_max) på tail
% Jämför med head.
% Om head < l_min, l_min = head.
% Om head > l_max, l_max = head.
% => (l_min, l_max)
%
% Tänk på steget innan basfallet, alltså när det finns två element i
% listan. Ta [1,2,3] som exempel. Rekursivt anrop från näst sista steget
% (när vi har [2,3]) ger l_min = l_max = 3. Vi jämför med head och får
% 2 < 3 men not 2 > 3, så nya värden är l_min=2 och l_max=3.
% Rekursionen bakåt ger sedan l_min=1 och l_max=3.
\end{column}%
\begin{column}{0.48\textwidth}
\begin{enumerate}
\item Funktionen körs med \\ \texttt{[1, 2, 3]} som indata. Vad skrivs ut? Vad returneras?
\item Fungerar \texttt{[1, 2, 'abc']} som indata?
\item Fungerar \texttt{(1, 2, 3)} som indata?
\end{enumerate}
\end{column}
\end{columns}
\end{frame}
\begin{frame}
\frametitle{Hur en rekursiv funktion kan analyseras}
(Ingen specifik ordning)
\begin{itemize}
\item Vad är basfallen?
\item Hur delas problemet upp i samma problem i mindre delar?
\item Hur sätts de mindre delarna ihop till grundproblemet?
\end{itemize}
\end{frame}
\begin{frame}[fragile]
\frametitle{Exempel på analys av rekursiv funktion: \texttt{min\_max}}
\begin{columns}
\begin{column}{0.48\textwidth}
\begin{minted}[fontsize=\scriptsize,linenos]{python}
def min_max(seq):
if not seq:
return (None, None)
if len(seq) == 1:
return (seq[0], seq[0])
(l_min, l_max) = min_max(seq[1:])
if seq[0] < l_min:
l_min = seq[0]
if seq[0] > l_max:
l_max = seq[0]
print("min: ", l_min)
print("max: ", l_max)
return (l_min, l_max)
\end{minted}
\end{column}%
\begin{column}{0.48\textwidth}
\only<1> {Vad är basfallen?}%
\only<2> {Hur delas problemet upp i samma problem i mindre delar?}%
\only<3> {Hur sätts de mindre delarna ihop till grundproblemet?}%
\end{column}
\end{columns}
\end{frame}
\begin{frame}[fragile]
\frametitle{Uppgift: palindrom}
Skriv två funktioner (en iterativ och en rekursiv) som tar en sträng och
returnerar huruvida strängen är ett palindrom eller inte.
Ett palindrom är ett ord som skrivs likadant framlänges som baklänges.
Exempel: ABBA, kajak.
\end{frame}
\begin{frame}
\frametitle{Hur en rekursiv funktion kan designas}
\begin{itemize}
\item Vad är basfallen?
\item Hur kan problemet delas upp i samma problem i mindre delar?
\item Hur sätts de mindre delarna ihop till grundproblemet?
\end{itemize}
\end{frame}
\begin{frame}[fragile]
\frametitle{Exempel på en rekursiv funktion: \texttt{palin\_rec}}
\begin{minted}{python}
def palin_rec(s):
\end{minted}
\vspace{-1.5em}
\pause{}
\begin{minted}{python}
if len(s) <= 1:
return True
\end{minted}
\vspace{-1.5em}
\pause{}
\begin{minted}{python}
return s[0] == s[-1] \
\end{minted}
\vspace{-1.5em}
\pause{}
\begin{minted}{python}
and palin_rec(s[1:-1])
\end{minted}
\end{frame}
\begin{frame}[fragile]
\frametitle{\texttt{dict\_func}}
Vad gör den här funktionen?
\begin{minted}[linenos]{python}
def dict_func(d):
result = {}
for key in d:
if d[key] in result:
result[d[key]].append(key)
else:
result[d[key]] = [key]
return result
\end{minted}
\end{frame}
\end{document}
|
