Studiegids

nl en

Complexity

Vak
2022-2023

Toegangseisen

Voorkennis: De volgende vakken uit het eerste jaar van de bachelor Informatica: Continue Wiskunde en Programmeermethoden / Algoritmiek.

Beschrijving

In dit college bestuderen we de complexiteit (computational complexity) van algoritmen. Dit is de benodigde rekentijd, of algemener, het aantal elementaire stappen dat het bekeken algoritme nodig heeft om een bepaald probleem op te lossen. Ook kijken we naar technieken om de optimaliteit van een algoritme te bewijzen.
Behandelde onderwerpen zullen zijn: O-notatie, worst case, best case en and average case complexiteit, algoritmen voor selectie en sorteren (en hun complexiteit), polynoomevaluatie/matrixvermenigvuldiging, een enkel graafalgoritme, beslissingsbomen en adversary argumenten. In het tweede deel van het college houden we ons bezig met complexiteitsklassen: klassen die problemen groeperen op basis van hun moeilijkheid (hardness). We concentreren ons daarbij op de klassen P (problemen die oplosbaar zijn in polynomiale tijd) en NP, en het begrip NP-volledigheid. De klasse van NP-volledige problemen bevat onder andere het bekende Handelsreizigersprobleem en heeft enkele interessante eigenschappen. Een belangrijk begrip daarbij zijn reducties.

Leerdoelen

Kennis en ervaring opdoen met de analyse van algoritmen, zoals het bepalen van de worst case complexiteit. Verder leert men een aantal technieken om daarmee de optimaliteit van bepaalde algoritmen te bepalen. Verder wordt bestudeerd wat het betekent als een probleem NP-volledig is, en geleerd hoe men NP-volledigheid kan bewijzen met behulp van reducties.

Rooster

In MyTimetable (login) kun je alle vak- en opleidingsroosters vinden, waarmee jij je persoonlijke rooster kunt samenstellen. Onderwijsactiviteiten waarvoor je je via MyStudymap hebt ingeschreven, worden automatisch in je rooster getoond. Daarnaast kun je My Timetable gemakkelijk koppelen aan een agenda-app op je telefoon en worden roosterwijzigingen automatisch in je agenda doorgevoerd; bovendien ontvang je desgewenst per e-mail een notificatie van de wijziging. Je kunt notificaties aanzetten bij Instellingen, na login.

Vragen? Bekijk de video, lees de instructie of neem contact op met de ISSC helpdesk. Let op: Joint Degree studenten Leiden/Delft dienen de informatie uit de Leidse en Delftse MyTimetable's samen te voegen om een volledig rooster te zien. Deze video leg uit hoe dat werkt.

Onderwijsvorm

  • Colleges

  • Werkcolleges

Toetsing en weging

  • (Maximaal) vier huiswerkopdrachten

  • Schriftelijk tentamen

Het gemiddeld huiswerkcijfer telt mee als bonus indien het tentamencijfer >= 5,0 is.

Het eindcijfer wordt dan als volgt berekend:
als (tentamencijfer >= 5,0): eindcijfer = tentamencijfer + (gemiddeld huiswerkcijfer ) / 10;
als (tentamencijfer < 5,0): eindcijfer = tentamencijfer

Literatuurlijst

  • Dictaat (reader) waarin ook opgaven zijn opgenomen

  • Links naar eventuele interessante extra literatuur zullen worden gedeeld via college / website

Inschrijven

Met ingang van het collegejaar 2022-2023 ben je als student zelf verantwoordelijk om je tijdig, dat wil zeggen 14 of 28 dagen voor aanvang van het vak, in te schrijven. Dat kan via Mystudymap. Dit doe je twee keer per jaar: één keer voor de vakken die je wilt volgen in semester 1 en één keer voor de vakken die je wilt volgen in semester 2.

Inschrijven voor vakken in het eerste semester is mogelijk vanaf juli; inschrijven voor vakken in het tweede semester is mogelijk vanaf december. Zie voor meer informatie deze pagina (tab Wiskunde en Natuurwetenschappen)

Daarnaast is het voor alle studenten, inclusief eerstejaars bachelorstudenten, verplicht om zich in te schrijven voor tentamens én de inschrijving voor elk tentamen in My Studymap te bevestigen. Dit kan tot en met uiterlijk 10 kalenderdagen voorafgaand aan het tentamen. Zonder geldige voorinschrijving én bevestiging in My Studymap kun je niet deelnemen aan het tentamen.

Uitgebreide informatie over de werking van MyStudyMap vind je hier.

Contact

Lecturer: dr. J.M. de Graaf
Coordinator: Onderwijscoördinator LIACS bachelors

Website

https://liacs.leidenuniv.nl/~graafjmde/COMP

Opmerkingen

Veel informatie over het vak, zoals de collegeslides, het dictaat met opgaven en enkele oude tentamens, staat op de website van het vak. Brightspace wordt voornamelijk gebruikt voor het publiceren van de huiswerkcijfers.

Voor meer informatie over Brightspace kun je op deze link klikken om de handleidingen van de universiteit te bekijken. Bij overige vragen of problemen kan contact opgenomen worden met de helpdesk van de universiteit Leiden.