Hinweise zum Grundlagenfragebogen

Hier sind die Aufgaben aus dem Fragebogen; die Auswertung im Kontext von A&DS ist hier.

Der Grundlagenfragebogen diente hauptsächlich mir als Dozent dazu, eure Vorkenntnisse besser einzuschätzen zu können; nicht alles, was dort abgefragt wurde, ist in allen Studiengänge tatsächlich Pflichtprogramm, und nicht alles wird für A&DS benötigt.

Aber: Ein großer Teil der Fähigkeiten sind schon wichtig für A&DS, und gerade die Matheteile sind zu einem großen Teil Schulstoff, auf den wir innerhalb der Vorlesung nicht im Detail eingehen können. Wer hier Lücken hat, sollte also selbst aktiv werden.

Nachfolgend sind einige Links gesammelt, die dabei helfen können; sie beziehen sich jeweils auf Aufgaben aus dem Grundlagenfragebogen.

Rechenregeln

• Potenzgesetze: youtube
• Logarithmengesetze: youtube

• Umformungsregeln für Summen: youtube

• Zählen von Teilmengen: wikipedia
• »Kleiner Gauß«: wikipedia
  (Wer sich die Formel nicht merken kann, kennt vermutlich nur die richtige Erklärung nicht, siehe dieses Video.)

Grenzwerte

Grenzwerte spielen eine zentrale Rolle bei der asymptotischen Analyse von Algorithmen, und kommen in typischen Klausuraufgaben (als Teilprobleme) vor. Wer nie eine formale Definition von Grenzwerten (Stichwort »epsilon-delta Kriterium«) gesehen hat, sollte das unbedingt nachholen.

Wir brauchen i.d.R. nur die Fähigkeit, Grenzwerte von Termen auszurechnen. Dazu reichen meist einige einfache Regeln:

• Die gängigsten Tricks werden hübsch erklärt in diesem Video Teil 1 und Teil 2.
  
• Es fehlt dort l’Hopitals rule,
• und einige Grenzwerte, die nicht leicht herzuleiten sind, und die man daher besser einfach (er)kennt. Eine sinnvolle Liste (mit Beweisen) findet ihr hier, leider ist die etwas unübersichtlich. Wikipedia hat auch eine laaange Liste, die man aber nicht alle kennen muss/kann.
  
• Der wichtigste davon ist $\lim_{n\to\infty} (1+\frac1n)^n = e$.
  Diesen klassischen Grenzwert muss man kennen; er wird oft sogar als Definition von e verwendet. Er hat einen anschaulichen Zusammenhang mit Zinseszins. Hier ist der Beweis der Konvergenz.

Mit diesen Zutaten sind die Aufgaben aus dem Grundlagenfragebogen recht schnell zu lösen; und ich empfehle, das zu üben. Man kann aber auch computer algebra nutzen, insbesondere wolfram alpha ist hier stark.

Vollständige Induktion

Induktionsbeweise sind ein wichtiges Hilfsmittel um die Korrektheit von Algorithmen zu begründen.

Eine sehr gut aufbereitete und detaillierte Einführung findet ihr in Video Teil 1 und Teil 2, (mit fast genau dem Beispiel aus dem Grundlagenfragebogen).

Auswertung

Hier sind Kuchendiagramme mit der Häufigkeit der Antworten. Das abgesetzte Kuchenstück repräsentiert die korrekte Antwort.