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 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
De complexiteit van een algoritme kunnen bepalen (maatgevende operatie, worst/best case, ...);
Methoden om een ondergrens op de complexiteit te bepalen kunnen toepassen;
Recurrente betrekkingen kunnen opstellen en oplossen voor bepaalde recursieve algoritmen;
Van een aantal selectie- en sorteeralgoritmen weten en kunnen uitleggen hoe ze werken en wat hun complexiteit is;
Begrijpen wat het betekent dat een probleem in P/NP/NPC zit en voorbeelden van bekende NP-problemen kennen;
Kunnen aantonen dat een probleem in NP zit en met behulp van reducties kunnen bewijzen dat een probleem NP-volledig is;
Rooster
In MyTimetable 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, nadat je bent ingelogd.
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 MyTimetables samen te voegen om een volledig rooster te zien. Deze video legt 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
Als student ben je zelf verantwoordelijk voor het tijdig inschrijven via MyStudyMap.
In deze korte video zie je stap voor stap hoe je je kunt inschrijven voor cursussen in MyStudyMap.
Uitgebreide informatie over de werking van MyStudyMap vind je hier.
Er zijn twee inschrijfperiodes per jaar:
de inschrijving voor het najaar opent in juli
de inschrijving voor het voorjaar opent in december
Zie deze pagina voor meer informatie over deadlines en inschrijven voor vakken en tentamens.
Let op:
Het is verplicht om je in te schrijven voor alle activiteiten die je gaat volgen van een vak.
Je inschrijving is pas voltooid wanneer je je cursusplanning indient in het tabblad ‘Klaar voor inschrijving’ door op ‘indienen’ te klikken.
Niet ingeschreven zijn voor een (her)tentamen betekent dat je niet mag deelnemen aan het (her)tentamen.
Contact
Docent: dr. J.M. de Graaf
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 en belangrijke mededelingen.
Brightspace
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.
Software
Vanaf collegejaar 2024/2025 werkt de faculteit Wiskunde en Natuurwetenschappen met het software distributieplatform Academic Software. Via het platform kun je toegang krijgen tot de software die je nodig hebt voor bepaalde vakken in je studie. Voor sommige software moet je laptop aan bepaalde systeemeisen voldoen. Dit staat aangegeven bij de software. Belangrijk is dat je de software installeert voor de start van het vak. Meer informatie over het laptopprofiel vind je op de studentenwebsite.