Toegangseisen
Voorkennis: de volgende vakken uit het eerste jaar van de bachelor Informatica: Calculus 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 via My Studymap. Zonder geldige voorinschrijving in My Studymap kun je niet deelnemen aan het tentamen.
Uitgebreide informatie over de werking van MyStudymap vind je hier.
Contact
Docenten: dr. J.M. de Graaf en
L.J. Edixhoven MSc
Coördinator: 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.