Kategorie: Studium

Restklassenringe

Im ersten Semester lernt man im Informatikstudium Restklassenringe kennen. Diese bilden die mathematische Basis für diverse Kryptographie (beispielsweise RSA), aber auch anderes Zeug wie CRC. Gestern hatte ich im Forum mal ne oberflächliche Einführung in das Thema gegeben. Und damit das nicht verloren geht, will ich das hier nochmal posten. Wer also kein Informatik studiert, aber aus welchen Gründen auch immer wissen will, was modulare Arithmetik ist und wie man in Restklassenringen rechnet, hier eine knappe Einführung. weiter lesen »

Summerschool “Agile Software Development”

Der FIT hat in diesem Jahr neben den schon mehrmals angebotenen — und im übrigen ebenfalls empfehlenswerten — Firmenexkursionen auch eine Veranstaltung zum Thema Agile Softwareentwicklung angeboten: Summerschool “Agile Software Development”.

Als ich die Ankündigung gelesen hatte, wusste ich sofort, dass ich da mitmachen wollte. Mit agiler Softwareentwicklung wollte ich mich sowieso mal beschäftigen. Außerdem sollte das Ganze auch sehr praxisnah sein. (Wenn man auf ner Uni studiert, sind wirklich praxisnahe Lehrveranstaltungen eher selten.) Und zum Dritten bot sich so mal wieder die Gelegenheit, mit ein paar Firmen in Kontakt zu kommen. weiter lesen »

checkLectures

Wenn man studiert, hat man üblicherweise Lehrveranstaltungen. Und zumindest in der Informatik ist es auch üblich, da wirklich hinzugehen [1]. Und es ist üblich, dass es die Folien zum Download gibt. Dann kann man sich die ausdrucken und während der Vorlesung Notizen drauf machen.

Normalerweise gibt es also zu jeder Vorlesung eine Webseite mit den ganzen Materialen (Vorlesungsfoien, Übungsblätter) und ein paar News. Da man natürlich wissen will, wann es neue Folien gibt oder neue Übungsblätter oder wenn, sagen wir mal, der Raum verlegt wird, ist es wichtig, dass man ständig die Vorlesungsseite besucht. Das Ganze macht man mindestens einmal täglich, wenn nicht öfter.

Wie schön wäre es da, wenn alle Vorlesungsseiten einfach einen Newsfeed anbieten würden. Dann würde der Feedreader die ganze Arbeit machen und man müsste nicht ständig selber gucken, sondern nur, wenns wirklich was Neues gibt. Leider ist das die große Ausnahme. Nur ein Bruchteil der Vorlesungsseiten hat einen Feed. Schade.

Gestern hatte ich dann mal wieder so einen Warum-ist-mir-das-nicht-schon-früher-eingefallen-Erlebnis. Ich könnte mir doch schnell ein kleines Skript zusammenbasteln, das mir die Arbeit abnimmt. Für was bin ich denn eigentlich Informatiker, wenn ich schon so Kleinkram nicht automatisiere! Warum muss mir sowas eigentlich erst im 9. Semester einfallen?

Ich hab mich also kurz mal hingesetzt und ein kleines Ruby-Skript geschrieben. Es ist nicht furchtbar schön, aber es tut seinen Zweck:

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
#!/usr/bin/ruby

require 'pathname'

# configuration
$path = File.dirname(Pathname.new(__FILE__).realpath)
$lecturesFile = $path + '/lectures.list'
$browser = 'opera'

def checkLecturesInFile(lecturesFile)
        items = File.open(lecturesFile).readlines
        File.open lecturesFile, 'w' do | file |
                items.each do | item |
                        data = item.split ';'
                        name = data[0].strip
                        url = data[1].strip
                        hash = data[2].strip

                        newHash = `wget "#{url}" -qO - | md5sum | cut -d " " -f 1`
                        newHash.strip!
                        if hash == newHash
                                puts "#{name}: OK"
                        else
                                puts "#{name}: new"
                               `#{$browser} "#{url}"`
                        end
                        file.puts "#{name} ; #{url} ; #{newHash}"
                end
        end
end

# main
checkLecturesInFile $lecturesFile

[2]

In der Datei lectures.list ist dann ne URL-Liste in folgendem Format:

1
<Name> ; <URL> ; <md5Hash>

also z.B.

1
CRDE ; http://www.christian-rehn.de ; b1306d712bc39ecfb95fa8d29c8d23a4

Das Skript geht die Datei Zeile für Zeile durch, ruft die Webseite ab, berechnet einen Hash-Wert und vergleicht ihn mit dem gespeicherten Hash. Hat sich die Seite geändert wird sie automatisch im Browser geladen. Der neue Hash wird dann wieder in die Datei gespeichert. Die Idee ist einfach und funktioniert in den meisten Fällen. Leider eben nicht in allen:

  • Manche Vorlesungsseiten sind passwortgeschützt. HTTP Auth ist per wget kein Problem, aber wenn wenn handgestrickte Lösungen ins Spiel kommen, müsste man das genau auf die jeweilige Seite anpassen. Einfach nen Cookie zu übergeben klappt i.d.R. nicht, da wohl weitere Header überprüft werden (um Session Hijacking zu vermeiden). Das also jeweils anzupassen ist mehr Arbeit, die sich nicht unbedingt lohnt.
  • Manche Vorlesungsseiten generieren Session IDs oder ähnliche Tokens und bauen sie in die Links mit ein. Das ändert natürlich den Hash, womit der Ansatz nicht mehr klappt. Ich hab auch schon überlegt nen HEAD-Request mit If-Modified-Since zu senden, aber die meisten dynamischen Seiten machen sich hier keine große Mühe und geben immer Modified zurück, womit der Ansatz schon generell ausscheidet.

Nicht perfekt, aber das muss es auch nicht. Auf jeden Fall besser als alles immer händisch prüfen.

[1] Das lohnt sich auch, denn die Vorlesungen sind meistens gut.
[2] Der Code ist trivial und darf von jedem ohne Einschränkung verwendet werden.


Update(30.08.11): kleiner Bugfix

Tradable Quality Hypothesis

In der Vorlesung Projektmanagement hört man folgendes: Die Produktivität eines Softwareentwicklungsteams ist konstant. Will man mehr leisten, in kürzerer Zeit leisten, zu geringeren Kosten leisten oder in höherer Qualität leisten, leiden die jeweils anderen Aspekte. Es ist unmöglich alle diese Punkte gleichermaßen zu verbessern.

Der Zusammenhang lässt sich mit dem so genannten Teufelsquadrat nach Sneed visualisieren. Der blaue Bereich in der Mitte der Grafik ist die Produktivität des Teams. Zieht man nun an einer oder mehreren Ecken, so drückt man gleichzeitig die anderen Ecken ein. Die Fläche in der Mitte – die Produktivität – bleibt immer konstant.

Das Teufelsquadrat nach Sneed

Das ist sehr anschaulich und auch intuitiv verständlich. Aber ist es auch richtig? Gerade letztens habe ich bei Martin Fowler etwas Interessantes dazu gelesen. weiter lesen »

SE1: Terminierungsbeweise

Terminierungsbeweise sind generell unmöglich. Im speziellen sind sie aber meist recht trivial und unter anderem müssen das alle SE1-Studenten mal machen. Das Schema hatte ich schon an die Tafel geschrieben und Jenny und Jonas haben es auch mal in digitaler Form verfügbar gemacht: http://sci-nexus.de/project_detail.php?c=1

Hier noch ein paar Hinweise: weiter lesen »

SE1: FizzBuzz

Wöchentlich stelle ich “meinen” SE1-Studenten ein paar kleine meist sehr einfache Aufgaben. Letztens hab ich ihnen versprochen, die Aufgabe zu “Java” wird ein Kinderspiel. Und genau das war sie auch:

Das Spiel geht folgendermaßen: Es geht reihum und dabei muss gezählt werden. Jeder sagt die Zahl, die um eins höher ist, als die vorherige. Es wird bei 1 angefangen und der, der einen Fehler macht, scheidet aus dem Spiel aus. Damit das nicht so einfach ist, werden alle Vielfache von 3 durch “Fizz” und alle Vielfache von 5 durch “Buzz” ersetzt. Vielfache von 3 und 5 werden durch “Fizzbuzz” ersetzt. Damit ergibt sich folgende Folge:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
...

Ich hätte jetzt gerne eine Prozedur, die einen int-Parameter entgegen nimmt und das Ganze bis zu dieser Grenze durchexerziert. Also fizzbuzz(16) gibt genau die obige Ausgabe auf der Konsole aus.

Die Aufgabe selbst ist nicht weiter spannend, eigentlich sogar ziemlich langweilig. Etwas weniger langweilig ist aber, wo ich die Idee her hab. weiter lesen »

SE1: Aufgaben zur Parameterinduktion

Ich hatte ja noch versprochen die Aufgaben zur Parameterinduktion online zu stellen. Hier sind sie:

1
2
add x 0 = x
add x y = 1 + add x (y-1)

Behauptung: add x y = x + y

1
2
3
ack 0 m = m + 1
ack n 0 = ack (n-1) 1
ack n m = ack (n-1) (ack n (m-1))

Behauptung1: ack 1 m = m + 2
Behauptung2: ack 2 m = 2m + 3
Behauptung3: ack 3 m = 8 \cdot 2^m -3

Für die Behauptungen 2 und 3 können die vorherigen Behauptungen als gegeben angenommen werden.

Die Idee, die Ackermannfunktion als Aufgabe zu stellen, stammt übrigens nicht von mir, sondern von Jennifer. Das Schöne an dieser Aufgabe ist, dass sie zwar kompliziert aussieht, letztendlich aber gar nicht so schwer ist. Bietet also wunderbar die Möglichkeit die Angst vor der Parameterinduktion zu verlieren (sollte man sie denn haben).

SE1: Sortieralgorithmen

Das Sortieren ist ein typisches Problem der Informatik. So typisch, dass es mittlerweile dermaßen gut erforscht ist, dass es schon seit mindestens zwei halben Ewigkeiten eine Reihe von Sortieralgorithmen gibt, die quasi jeder Informatiker kennt. Und das obwohl kaum jemand heute noch in der Praxis Sortieralgorithmen schreibt. In der Regel wird ein Problem wie das Sortieren einmal gelöst (d.h. einmal der Algorithmus implementiert) um dann nur noch die bereits bestehende Implementierung zu nutzen. Jede Standardbibliothek für eine x-beliebige Programmiersprache bringt normalerweise einen implementierten Sortieralgorithmus (oft QuickSort) mit, den man dann einfach nur noch benutzt.

Dennoch ist es sehr sinnvoll, die grundlegenden Sortieralgorithmen zu kennen, da diese sehr schön prinzipielle Herangehensweisen an typische Probleme, verdeutlichen. Also auch, wenn man das Sortieren wohl kaum selbst implementieren wird, so wird man ähnliche Algorithmen implementieren, die bestimmte Ideen nutzen, die sich auch in den Sortieralgorithmen finden.

Zu diesen grundlegenden Sortieralgorithmen gehören SelectionSort, InsertionSort, BubbleSort, MergeSort, QuickSort und HeapSort. Diese haben alle gewisse Vor- und Nachteile und zeigen bestimmte Herangehensweisen an algorithmische Probleme.
weiter lesen »

SE1: Rekursion mit Haskell

Rekursion ist für manche noch ein ungewohntes Konzept. Viele einfache Aufgaben lassen sich aber direkt nach “Schema F” lösen. Der generelle Ansatz ist eigentlich immer gleich. Deshalb hier ein paar kleine Daumenregeln, die vielleicht helfen, Rekursionsaufgaben systematischer zu lösen:

Analogie: Vollständige Induktion

Rekursion funktioniert so ähnlich wie vollständige Induktion. Bei letzterer gibt es einen Induktionsanfang, eine Induktionsvoraussetzung und einen Induktionsschritt. Ganz ähnlich ist es mit der Rekursion: Ein Rekursionsanfang definiert die Funktion für den einfachsten Fall (beispielsweise die leere Liste). Dann kann angenommen werden, dass die Funktion bereits funktioniert (der rekursive Aufruf nutzt das). Schließlich ist analog zum Induktionsschritt ein Rekursionsschritt nötig. Dabei wird quasi nur noch das implementiert, was getan werden muss, wenn die Liste um ein Element länger ist.

Die Datenstruktur bestimmt die Rekursion

Die meisten Rekursionsaufgaben orientieren sich an bestimmten rekursiven Datenstrukturen. Das sind in den meisten Fällen entweder Listen oder Bäume. Die Lösung der Aufgabe wird demnach stark an die Definition der Datenstruktur angelehnt sein.
weiter lesen »

SE1: Zusatzaufgaben

Auf Wunsch einiger “meiner” Studenten habe ich mal ein paar Übungsaufgaben zu kontextfreien Grammatiken und Rekursion in Haskell zusammen gestellt. Eigentlich hatte ich ja gar nicht vor so viel zu schreiben, aber wenn man mal anfängt…

Ich hoffe, die Aufgaben helfen.

weiter lesen »

powered by WordPress | QuickLaTeX | WordPress Themes