D1
Algorithms & Complexity

Ideen und Konzepte der Informatik

Veranstaltung für Studierende anderer Fakultäten, 2+2

Übungsblattabgabe

Zu Ihrer und unserer Entlastung lassen wir ab Übungsblatt 5 Gruppenabgaben zu.

Dabei gelten folgende Bedingungen, an die Sie sich bitte genau halten:

  • Sie dürfen die Übungsblätter ab Blatt 5 in Teams mit bis zu drei Mitgliedern abgeben. Einzelabgaben sind weiterhin zulässig, und in der Klausur wird weiterhin erwartet, dass Sie persönlich den gesamten Stoff können.

  • Teams müssen sich bei Ann-Sophie registrieren und einen eindeutigen Teamnamen angeben (nutzen Sie Ihre Fantasie, um zu verhindern, dass es zu Namenskollisionen kommt – bei Namenskollisionen muss die Gruppe, die sich später registriert hat, neu überlegen). An die Stelle der Matrikelnummer im PDF-Namen und im Email-Betreff tritt der Teamname; im abgegebenen PDF müssen sowohl der Teamname als auch die Matrikelnummern und Namen aller Teammitglieder angegeben sein.

  • Die Teams sollen grundsätzlich fest sein (mit allem anderen tun Sie weder sich noch uns einen Gefallen). Zwingend erforderliche Änderungen in der Teamzusammensetzung müssen Sie vor Abgabe des ersten von der Änderung betroffenen Übungsblatts an Ann-Sophie übermitteln.

Außerdem werden ab Blatt 5 Abgaben über 5 MB zwar korrigiert, aber nicht korrigiert an Sie zurückgegeben. Verkleinern Sie Ihre Abgaben auf maximal 5 MB.

Ziele und Inhalte

Wir verfolgen drei Ziele:

  • Die Hörer sollen mit den Grundbegriffen der Informatik vertraut werden. Was ist ein Algorithmus? Was ist ein Computer? Sind alle Computer gleich?  
  • Sie sollen die Grundlagen wichtiger Informatiksysteme verstehen. Welche wissenschaftlichen Erkenntnisse haben die informatische Revolution möglich gemacht? Wo sind die Grenzen dieser Systeme?
  • Sie sollen genügend Informatikwissen erwerben, damit sie die gesellschaftlichen Konsequenzen von Informatiksystemen fundiert diskutieren können.

Wir behandeln folgende Themen: Algorithmen und Programme, Programmiersprachen, Aufbau von Rechenanlagen, Sortieren, Suchen, Suchmaschinen, Kryptographie und Electronic Banking, Schnellste Wege und Navis, Verteiltes Entscheiden und algorithmische Spieltheorie, Optimierung, Internet, Email und WWW, maschinelles Lernen, Finden versus Verifizieren, Blockchains, Algorithmisches Entscheiden, Sicherheit und Privatsphäre.

Außerdem gehen wir darauf ein, wie die Erkenntnisse der Informatik das wissenschaftliche Weltbild verändert haben. Was ist Intelligenz? Werden soziale Netze eine Experimentierumgebung für die Sozialwissenschaften? Was folgt aus der Möglichkeit, sehr große Datenmengen zu analysieren? Außerdem werfen informatische Systeme neue ethische Fragen auf, etwa in Bereichen der Privatsphäre oder beim autonomen Fahren.

Zeitplan und Unterlagen

Achtung: Die Themen und die bereitgestellten Unterlagen sind erst ab dem Datum der Einheit final, der sie zugeordnet sind.
Bis dahin stellen wir Ihnen die Unterlagen aus dem Vorjahr als Service zur Verfügung. 
Wenn Sie Themen vorarbeiten wollen, tun Sie das auf eigene Gefahr.

Die Aufzeichnungen der Übungen werden hier bereit gestellt. Sie sind passwortgeschützt. Das Passwort wurde Ihnen über die Mailingliste der Vorlesung mitgeteilt.

DatumThemaKernmaterialZusatzmaterialÜbungLösungArtikel der Woche

18.10.21

Einführung,

Sicherheit und Privatheit

Grundlagen der Informatik,

Kapitel 1 und 4

Traits and ...

Erasmus-Lecture

Folien, Einfuehrung

Folien, Sicherheit

Blatt 1

Blatt 1 mit Loesung

 

 
25.10.21Rechner

Grundlagen der Informatik

Kapitel 2

Computer MuseenBlatt 2

Blatt 2 mit Loesung

 

 
08.11.21Algorithmen und Programme

Grundlagen der Informatik,

Kapitel 3

 Blatt 3Blatt 3 mit Loesung 

15.11.21

Suchen und SortierenSuchen und Sortieren, Kapitel 1-3 Blatt 4Blatt 4 mit Loesung 

22.11.21

WebsucheWebsuche Blatt 5Blatt 5 mit Loesung 
29.11.21Schnellste WegeSchnellste Wege Blatt 6Blatt 6 mit Loesung 
06.12.21InternetInternetUS House ReportBlatt 7Blatt 7 mit Loesung 
13.12.21OptimierungOptimierungDantzig, Stigler, Paarungsalgorithmen für die NierentransplantationBlatt 8Blatt 8 mit Loesung 
03.01.21

Algorithmische Spieltheorie, 

Auktionen und verteiltes Entscheiden

Algorithmische Spieltheorie

 

Paarungsalgorithmen für Wohnungszuweisung

Blatt 9Blatt 9 mit Loesung 

10.01.22

Kryptographie; Bitcoins und BlockchainsKryptographieBlockchain DEMO

Blatt 10

Blatt 10 mit Platz

Blatt 10 mit Loesung 
17.01.22Künstliche Intelligenz und Maschinelles Lernen, Teil IKünstliche Intelligenz, Kapitel 1-3 

Blatt 11

Blatt 11 mit Platz

  
24.01.22Künstliche Intelligenz und Maschinelles Lernen, Teil IIKünstliche Intelligenz, Kapitel 4-6    
31.01.22Künstliche Intelligenz und Maschinelles Lernen, Teil IIIKünstliche Intelligenz​​​​​​​, Kapitel 7-8Studie zur Algorithmenregulierung   
07.02.22Quantum ComputingQuantum Computing    
 Probeklausur     
 Fragestunde     
05.03.22Klausur (10h00-12h30)     
       
 Mathematisches Rüstzeug

Grundlagen der Informatik

Kapitel 6

    
 P = NP?P = NP?    

Allgemeine Informationen

Dozenten:

Kurt Mehlhorn und Corinna Coupette

Chefbremser: Ann-Sophie Becker

Zeit und Raum:

Vorlesung und Übungen finden virtuell in Zoom statt. Falls der vorstehende Link nicht funktionieren sollte, benutzen Sie folgende Meeting-ID: 910 7124 6639 und Kenncode: 958976.

Die erste Vorlesung wird am 18. Oktober 2021 über Zoom stattfinden und um 16h15 beginnen.

Die weiteren Vorlesungen werden in Form von Videos angeboten. Die Videos stehen als eine Iversity-Akademie zur Verfügung (Iversity ist eine Tochter von Springer/Nature); alternativ können Sie sich die qualitativ schlechteren Videos des letzten Jahres ansehen. Der Iversity-Kurs ist eine Obermenge der Vorlesung und enthält auch weitere Übungen. Wir werden jeweils angeben, welche Videos Sie studieren sollen.

Der Link auf die Iversity-Akademie darf nur von Mitgliedern (Beschäftigte und Studenten) der Universität des Saarlandes genutzt werden. Wenn Sie ihm zum ersten Mal folgen, müssen Sie sich registrieren. Danach steht Ihnen der Zugang zur Verfügung. Falls Sie sich bereits ohne den Link registriert haben und Sie nicht auf alle Inhalte zugreifen können, schreiben Sie uns eine Email mit der Emailadresse, die Sie für die Registrierung verwendet haben, damit wir Sie manuell zum Kurs hinzufügen können. Prüfen Sie aber vorher, dass Sie tatsächlich keinen Zugriff auf die Kursinhalte haben, und lassen Sie sich nicht davon abschrecken, dass die meisten Kurse nach wie vor mit "Pro" gekennzeichnet sind.

Wir treffen uns ab dem 25. Oktober jeden Montag von 16h00-17h30 im Zoom-Raum,  um das Übungsblatt und Fragen zu den Videos zu besprechen.
Von 17h30-18h00 beantworten wir zusätzlich individuelle Fragen (falls Sie erst für diesen Teil hinzukommen, seien Sie aber pünktlich).

Klausur:

05.03.2022, 10h00-12h30, hybrid (vor Ort in Saarbrücken oder daheim vor Ihrem PC mit laufender Videokamera; Details in den Instruktionen zur Probleklausur)

Anmeldung zur Klausur: bis Sonntag, 27.02.2022, 23.59 CET, per Email an Ann-Sophie Becker, mit Betreff: "Klausuranmeldung <Ihre Matrikelnummer> <Ihr Name> <ob Sie physisch oder remote schreiben wollen>", und ggf. zusätzlich dort, wo es für Ihren Studiengang notwendig und möglich ist (LSF oÄ).

Übungen:

Montag 16h00-17h30, Zoom-Raum

Wir besprechen das Übungsblatt und beantworten Fragen zur Vorlesung.

Bitte beachten Sie bei der Einreichung Ihrer Übungen folgende Vorgaben:
  • Die Abgabe einer Übung hat bis spätestens vor Beginn der jeweils nächsten Veranstaltung (montags, 16 Uhr) per Mail an Ann-Sophie Becker zu erfolgen (der jeweilige Abgabetermin ist auch auf dem Übungsblatt vermerkt); entscheidend für die Rechtzeitigkeit der Abgabe die Timestamp des Eingangs im Postfach der angegebenen Emailadresse.
    Schicken Sie Ihre Abgabe keinesfalls an die Mailingliste der Veranstaltung!
  • Sie müssen Ihre Lösung als eine PDF-Datei im Anhang Ihrer Email abgeben; achten Sie also bitte darauf, ggf. mehrere Seiten zu einer Datei zusammenzufügen. Verkleinern Sie die Datei auf unter 5 MB. Abgaben über 5 MB werden zwar korrigiert, aber nicht korrigiert an Sie zurückgegeben.
  • Die PDF-Datei muss Ihre Matrikelnummer und Ihren Namen enthalten und wie der Dateiname muss wie folgt strukturiert sein: "<Matrikelnummer> Abgabe <Übungsnummer>.pdf" (Beispiel: "0123456 Abgabe 1.pdf").
  • Der Betreff Ihrer Email muss wie folgt strukturiert sein: "[IdI] <Matrikelnummer> Abgabe <Übungsnummer>" (Beispiel: "[IdI] 0123456 Abgabe 1").
  • Sie können Ihre Lösungen digital oder handschriftlich erstellen; für den Scan handschriftlicher Lösungen mit dem Smartphone eignet sich zum Beispiel die App CamScanner.
Bei Fragen oder Problemen (die sich nicht mit einer Web-Suche klären lassen) wenden Sie sich bitte an Ann-Sophie Becker.

Gruppenabgaben sind nicht zulässig. Ihre Übungsabgaben werden korrigiert und per Email an Sie zurückgegeben.

Weitere Informationen zum Übungsbetrieb werden ggf. über die Mailingliste bekannt gegeben.

Zielgruppe:Die Veranstaltung ist für Hörer aller Fakultäten sowie Universitätsfremde offen und erfordert keinerlei Vorkenntnisse. Insbesondere sind keine Programmierkenntnisse nötig. Die Vorlesung wird auf Deutsch abgehalten.
Anmeldung:

Eine Anmeldung zur Vorlesung ist nur nötig, wenn ein Leistungsnachweis erworben werden soll.

Neben einer Anmeldung in den entsprechenden Systemen für Ihren Studiengang (sofern erforderlich) sollten Sie sich auch auf der Mailingliste registrieren (klicken Sie auf den Link und folgen Sie den dortigen Instruktionen; schreiben Sie keine Email an uns oder die Mailingliste), da ein großer Teil der Kommunikation zwischen Ihnen und den Dozenten über die Mailingliste laufen wird.

Credit Points:

5 ECTS

 

Klausur/Credit Points:

Es kann ein Schein über 5LP erworben werden, wenn

  1. die Übungen erfolgreich bearbeitet werden (mindestens 50% der möglichen Übungspunkte), und
  2. die Klausur erfolgreich bestanden wird.

Die Gesamtnote ist die Klausurnote.

Studenten der Informatik können keinen Schein für diese Vorlesung erwerben.

Details zur Klausur in diesem Jahr finden Sie in der entsprechenden Reihe der Tabelle zu "Allgemeine Informationen".

Achtung: Aus vergangenen Iterationen dieser VO wissen wir, dass sich Studenten mancher Studienrichtungen explizit bei Ihren jeweiligen Prüfungsreferaten zur Klausur anmelden müssen, um die Klausur mitschreiben zu können. Es obliegt daher den Studierenden sich rechtzeitig und korrekt anzumelden.

Literatur/Links

  • J. Gallenbacher: Abenteuer Informatik, auch als E-Book.
  • B. Vöcking, H. Alt, M. Dietzfelbinger, R. Reischuk, C. Scheideler, H. Vollmer, D. Wagner: Taschenbuch der Algorithmen (ISBN:9783540763932)
  • Minsky: The Society of Mind
  • Hofstadter: Gödel, Escher, Bach
  • Algorithmus der Woche

Die Bücher finden sich auch im Semesterapparat der Informatikbibliothek.