Shall we start please?
So excuse me, today's lecture is going to be in English, okay?
I hope it's okay for all of us.
If at any point you have questions, either on what we are doing or about some English
word you don't understand or I said wrong or whatever, please just interrupt me and
ask me.
If you don't want to ask me in English, try in German slowly, I might understand.
And if I don't, I'm sure a couple of you will be able to translate it for me, so everything
should be fine.
First thing in the agenda, of course, will be the registration for the exercises we had
yesterday and the day before.
It was, of course, a mess for all of us, so the first thing I'd like to do is apologize
for that, if we had known that Studon was going to behave the way he did, of course,
he would have tried some other thing.
This situation with the system, which was unresponsive most of the time, turned out
to generate three kinds of problems, which I will now enumerate and we will try to solve
somehow.
So there were three kinds of problems.
First, some of you, by the time you were able to access the system, find out that there
were no more slots, no more vacancies, and that was because we couldn't even enter to
change and increase the number of vacancies in time, so I know that some of you couldn't
register to any UBUM whatsoever, so just to have an idea, how many of you are in that
situation?
Could you raise your hand?
Okay, good.
There was a second problem, which was as follows.
We realized about half an hour before the registration period started that there were
some inconsistencies between what said in Studon and what was in Unibiz and in our homepage.
What was wrong was what was in Studon, okay?
We tried to fix it before the registration period started, but we couldn't, and we tried
to do it short after it started because we said, okay, maybe a couple of people did it
wrong so then we can fix it, and we couldn't as well.
We could only fix it yesterday in the afternoon.
So it may be the case, this is the second problem, that many of you registered to one
group believing that you were registering to one group and you were actually registering
to another one.
The groups with these problems were, well, there was one announced for Tuesdays at 2
p.m.
Even slightly outdoors, and of course we discussed that this slot was not available, so here
it was meant to mean Thursdays.
So if you registered in this one, well, maybe you thought it was going to be the one at
10 in the morning.
Well, no, it was going to be this one.
And then there were two more, the one that said Tuesday 4.15 and Thursday 4.15.
One said here Litak and the other one said Gorin.
So these were interchanged.
So if you registered to this one expecting to get here, it was wrong and the other way
around.
This case is not so problematic because we just essentially swapped those who misregistered.
So we put a warning message in the webpage of the course, but I don't know if you were
Presenters
Zugänglich über
Offener Zugang
Dauer
01:29:50 Min
Aufnahmedatum
2013-04-19
Hochgeladen am
2019-04-22 18:59:02
Sprache
de-DE
- Mathematische Hilfsmittel der Algorithmenanalyse: Abschätzung des asymptotischen Wachstums von Funktionen, Summationen, Anzahlen, divide-and-conquer-Rekursionen, etc.
-
Grundbegriffe der quantitativen Algorithmenanalyse: worst-case- und average-case-Analsyse, obere und untere Schranken, Algorithmen- und Problemkomplexität
-
Exemplarische Analysen von Sortieralgorithmen
-
Sortierkomplexität und Entropie
-
Quellcodierung und Datenkompression
-
Komplexität von arithmetischen Operationen und Problemen (Multiplikation, Primtest, Faktorisierung)
-
modulare Arithmetik und schnelle Fouriertransformation
-
Kryptographie und Komplexität
Lernziele und Kompetenzen:
Die Studierenden
-
erwerben fundierte Kenntnisse über die Grundbegriffe der quantitativen Algorithmenanalyse (Laufzeit) und die benötigten mathematischen Methoden
-
verstehen die Komplexität (Laufzeitverhalten) von Standardalgorithmen (z.B. Sortieren, arithmetische Algorithmen) und können deren praktische Bedeutung erklären
-
sind in der Lage, an einfachen, exemplarischen Algorithmen Analysen des worst-case-Verhaltens und des average-case-Verhaltens durchzuführen
-
können exemplarisch Algorithmenkomplexität und Problemkomplexität in Bezug setzen
-
können die Beziehungen zwischen Sortier- und Suchkomplexität und dem Entropiebegriff darstellen
-
erwerben Grundkenntnisse über algebraische Strukturen der Arithmetik und die Komplexität arithmetischer Operationen
-
können die Rolle von Komplexitätsaussagen für die Beurteilung der Sicherheit einfacher kryptografischer Protokoll darstellen
Literatur:
Graham, Knuth, Patashnik, Concrete Mathematics, Addison-Wesley, 1994.
Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, MIT-Press, 2001.
Heun, Grundlegende Algorithmen, Vieweg, 2001.