Fundamentele Informatica 1 2018/2019

Het eerstejaarsvak Fundamentele Informatica 1 wordt in het najaar van 2018 verzorgd door Jeannette de Graaf. De assistentie, wordt verleend door Danielle Gramsbergen, Hermes Spaink, Elze de Vink en Larissa Wolters. Het vak is verplicht voor alle studenten Informatica, Informatica&Economie en Informatica&Biologie en levert 6 EC op. Het vak bestaat uit hoorcolleges en werkcolleges. Verder is er halverwege een toets en uiteraard een afsluitend tentamen.
Studenten die deel gaan nemen aan Fundamentele Informatica 1 wordt verzocht zich via uSis aan te melden voor het tentamen. Je kunt dit het beste doen via het nummer van de studieactiviteit. Ga hiertoe naar de studentenwebsite, daar kiezen voor Inschrijven voor vakken en tentamens en dan kiezen voor het tabblad Wiskunde en Natuurwetenschappen.

De colleges vinden meestal (maar niet altijd) plaats op dinsdagen van 13:30 uur tot 15:15 uur, in wisselende zalen. Er is inmiddels een apart overzicht beschikbaar van wanneer en in welke zaal de colleges precies zijn. Op de laatste collegeslide/sheet van elk college zal eveneens worden aangegeven in welke zaal en op welke tijd/dag de week erna het (werk)college zal zijn. Dus zie het collegeschema (Programma) verderop op deze site. Zie ook het Informaticarooster, het I&Erooster en het Bio-informaticarooster op internet. In deze roosters kan mogelijk hier of daar nog een kleine verandering optreden. De zalenroosters op dezelfde pagina geven aan in welke zalen een en ander plaatsvindt, maar ze zijn mogelijk niet altijd even betrouwbaar. Dus gebruik voor FI1 de door de docent tijdens college aangeleverde locatie-informatie.

Inhoud van het vak

Het vak is bedoeld als een kennismaking met discrete wiskundige structuren die van belang zijn voor de informatica. Verder wordt geleerd om te gaan met formalisaties, abstracties en bewijstechnieken. Een globaal overzicht van de behandelde onderwerpen: verzamelingenleer, relaties en functies, equivalentierelaties, partiële ordeningen, recursieve definities, volledige en structurele inductie, grafen, bomen en expressies, strings en talen, eindige automaten.

Literatuur

Schaum's Outline of Discrete Mathematics, door Seymour Lipschutz, Marc Lipson.

Net als vorig jaar gebruiken we het boek van Schaum, derde editie, ISBN 9780071615860, zie bv. amazon.de.

Niet alle hoofdstukken worden behandeld tijdens dit college, zie de specificatie van de collegestof, en het collegeschema verderop op deze pagina.

Overig materiaal

Naast het boek en het college en het werkcollege is er nog meer materiaal om je verder te helpen.

Collegedictaat Bestaat uit aanvullingen op het gebruikte boek. Hoofdstuk 2 staat inmiddels hieronder, de andere twee hoofdstukken komen nog.

Opgaven Het boek bevat een groot aantal opgaven. Een selectie (aangevuld met eigen bedenksels) vormt de oefenstof [=opgaven] voor de werkcolleges. Er is ook een groot aantal opgaven uitgewerkt.

Slides De laatste versie van de door de docent gemaakte slides komen per college als pdf op deze site in het collegeschema te staan. Er wordt naar gestreefd de sheets met te behandelen stof uiterlijk de ochtend voor het college op deze site te plaatsten; deze versie is dus onder voorbehoud. De definitieve versie, met de uiteindelijk echt behandelde hoeveelheid stof, wordt zo snel mogelijk na het college gepubliceerd. Uitleg van de kleurcoderingen in de sheets:  Rood  is uit het college,  groen  geeft extra toelichting/uitleg of extra weetjes.

Nieuws / updates

25-01-2019 - 18 uur: het tentamen is nagekeken. Ik zal vanavond mijn best doen om alle cijfers op Blackboard te krijgen. Ik stuur via Blackboard een mail als dat gelukt is. Er komt volgende week een uitwerking van het tentamen op deze site.

04-01-2019 - Vandaag en gisteren zijn twee aanvullingen bij de oude tentamens gezet, zoals een ontbrekend antwoord. Ook is de beloofde uitwerking van de extra opgave bij het werkcollege over formele talen toegevoegd.

21-12-2018 - Het tentamen zal plaatsvinden in het Snellius, zalen B01, B02, B03, 412, 312, 408. Studenten die recht hebben op extra tijd gaan naar zaal B01.

21-12-2018 - Het vragenuur van vrijdag 4 januari vindt plaats in zaal 312 van het Snellius. Aanvang: 14 uur.

14-12-2018 - Dinsdag zijn we net niet toegekomen aan onderdeel b en c van opgave 7 van het tentamen van maart 2018. Daarom van deze onderdelen nog een uitwerking.

11-12-2018 - De vrijdag voor het tentamen is er een vragenuur. Dit zal dus zijn op vrijdag 4 januari. Aanvang: 14 uur; plaats: Snellius. De precieze zaal wordt t.z.t. bekendgemaakt via deze website.

11-12-2018 - Vandaag is het college in de De Sitterzaal in het Huygens. Volgende week is er geen college meer.

04-12-2018 - Vandaag zijn bij het werkcollege de opgaven 72 en 74 over aftelbaarheid niet aan bod gekomen. We zullen hierop terugkomen bij het college van aanstaande dinsdag en zeker ook bij de werkgroep van volgende week. Vrijdag 14/12 zullen dus opgaven over (over)aftelbaarheid en eindige automaten behandeld worden.

29-11-2018 - Op dinsdag 4/12 is het college in de De Sitterzaal in het Huygens.

29-11-2018 - Er zijn nog drie werkcolleges te gaan; morgen (30/11; formele talen), vrijdag 7/12 (aftelbaarheid, modulo-rekenen) en vrijdag 14/11 (eindige automaten). Als het goed is is aanstaande dinsdag 4/12 het laatste reguliere college (eindige automaten). Op dinsdag 11/12 zal ik (een deel van) het hertentamen van het afgelopen studiejaar voormaken; het college van 18/12 zal dan vervallen. Dat is in elk geval de planning, maar daar kan verandering in komen als daar een goede reden voor is.

26-11-2018 - Deze week is er weer gewoon op dinsdag (27 november) college, en wel in het van Steenisgebouw, zaal E004. Ik zal de nagekeken toetsen daarheen meenemen, zodat iedereen die zijn/haar nagekeken nog niet terug heeft, dat morgen alsnog kan meenemen.

19-11-2018 - Let op: deze week is er op dinsdag (20 november) geen college, maar op vrijdag (23 november) wel. Er is dan college in plaats van werkcollege. Dus: vrijdag 23 november, 9.15 - 11.00 uur, college in zaal 407-409 van het Snellius.

19-11-2018 - De toets is inmiddels wel nagekeken, en de cijfers staan sinds zaterdagavond op Blackboard. Ook is inmiddels een vrij uitgebreide, handgeschreven uitwerking van de toets beschikbaar; zie verderop op deze site. Pagina 3 staat helaas ondersteboven, maar daar komen jullie wel uit. Het is overigens verstandig om je nagekeken werk terug te halen. Dit kan sowieso bij het college van aanstaande vrijdag, 23 november. Ik zal alle nagekeken werken naar dat college meenemen.

16-11-2018 - Ik ben nu bijna klaar met de (tweede) correctie van de toets. De bedoeling is om dat morgen af te maken en dan de cijfers op Blackboard te zetten. Het zou kunnen dat dat vanuit huis niet gaat; in dat geval wordt het pas maandag. Met excuses dat het zo lang duurt.

12-11-2018 - Morgen, dinsdag 13 november, is het college in het van Steenisgebouw. Om precies te zijn in zaal E004 aldaar. Tijd: 13.30 - 15.15 uur.

09-11-2018 - Naar verwachting zal de tussentoets in de loop van volgende week helemaal nagekeken zijn. De cijfers zullen op Blackboard worden gezet, en de nagekeken werken krijgen jullie terug om te zien wat er fout/goed is gegaan. Een uitwerking zal op deze site worden gezet. Volgende week dus.

09-11-2018 - Een uitwerking van opgave 50 (uit het tentamen van maart 2004) is toegevoegd. Kijk hiervoor bij de oude tentamens.

06-11-2018 - Een uitwerking van de extra opgaven over combinatoriek en inductie/recursie van het werkcollege van 2 november zijn nu ook beschikbaar.

05-11-2018 - Let op: In week 47 is er op dinsdag (20 november) geen college, maar op vrijdag (23 november) doen we college in plaats van werkcollege. Dus: vrijdag 23 november, 9.15 - 11.00 uur, college in zaal 407-409 van het Snellius.

19-10-2018 - De tussentoets zal op donderdag 25 oktober van 9 uur tot 11 uur plaatsvinden in het Snellius, in de zalen B01, 312, 407-409 en 412. Zorg dat je op tijd bent als je de volle 2 uur wilt benutten. In twee van de drie zalen begint namelijk om 11 uur een college, dus dan moeten wij eruit. Studenten met extra tijd graag naar zaal B01; de anderen mogen zelf kiezen waar ze gaan zitten.

19-10-2018 - Zoals hieronder al werd gemeld zal de tussentoets van 25 oktober gaan over de stof van college 1 t/m 7 en de bijbehorende werkcolleges. Ruwweg: verzamelingen, relaties, functies en ongerichte en gerichte grafen. Voor een preciezer overzicht kun je in het collegeschema kijken: de stof van de slides en de daarbij genoemde paragrafen uit het boek van Schaum. Merk op dat er in het boek nog (veel) meer opgaven staan om te oefenen.

19-10-2018 - Uit een kleine enquete gehouden onder studenten bij college blijkt dat er twee redenen zijn voor het matige werkcollegebezoek: het vroege tijdstip (kan ik niets aan doen, helaas) en te weinig klassikale uitwerking van opgaven. Over dat laatste is overlegd met de assistenten, en er zal bij werkcolleges in het vervolg wat meer op het bord voorgedaan worden.

09-10-2018 - Ik zag dat ik vergeten was de sheets voor het college op de site te zetten. Nu staan die slides er wel. We zijn gekomen tot de definities van soorten paden. Volgende week maken we het onderwerp (on)gerichte grafen af. De toets van 25 oktober zal gaan over de stof van college 1 t/m 7, dus tot en met wat we volgende week nog behandelen.

01-10-2018 - Ter herinnering: morgen, 2 oktober, is het college van 13.30 uur tot 16.15 uur in zaal C1 (Gorlaeus).

25-09-2018 - Er is nu ook een uitwerking van de nieuwe onderdelen van opgave 3 beschikbaar. Die zitten in hetzelfde document als de opgave zelf. Dus zie het betreffende werkcollege in het (werk)collegeschema.

18-09-2018 - Volgende week (25 september) is er geen college; de week erna (2 oktober) is het college daarom 3 uur in plaats van 2 uur. Dus van 13.30 uur tot 16.15 uur. Dat college zal plaatsvinden in zaal C1 (Gorlaeus).

18-09-2018 - Het college is vandaag in zaal E004 van het van Steenis gebouw, van 13.30 tot 15.15 uur.

13-09-2018 - Het eerste werkcollege is vrijdag 14 september van 9.00 tot 10.45 uur in Snelliuszalen 401, 402, 405 en 408. De aldaar te maken opgaven komen in principe allemaal uit de opgavenbundel; soms is er een extra opgave, die dan in het collegeschema komt te staan. Alle extra opgaven zullen uiteindelijk bij elkaar in 1 document komen. Er is een indeling gemaakt voor de werkgroepen, gebaseerd op de achternaam, zodanig dat in elke zaal ongeveer evenveel studenten zitten. Zie daartoe de laatste slide van college 3, relaties1.

11-09-2018 - Volgende week (18 september) is het college in zaal E004 van het van Steenis gebouw, van 13.30 tot 15.15 uur. We gaan dan door met het onderwerp relaties.

11-09-2018 - Er is sinds vandaag een overzicht beschikbaar van wanneer de colleges zijn en waar. In de sheets van de introductie stond nog een klein foutje: daar stond voor 40 als begintijd 13.00 uur; dit moet natuurlijk 13.30 zijn (zie het overzicht). De docent zal dit binnenkort verbeteren.

07-09-2018 - De slides die corresponderen met het college van vanochtend staan nu op de website. Het college van volgende week zal verder gaan met de algebraische eigenschappen/rekenregels voor verzamelingsoperaties. Het college is komende week op dinsdag (11/09) van 15.30 tot 17.15 in Gorlaeus zaal C1. Aansluitend is de eerstejaarsbarbecue in het Snellius.

04-09-2018 - Graag ook inschrijven voor dit vak op Blackboard. Hier zullen t.z.t. de resultaten van de toets gepubliceerd worden. Het eindcijfer komt uiteindelijk in uSis terecht. Zie de sheets van de introductie (college 1) voor de bepaling van het eindcijfer.

04-09-2018 - De sheets van het eerste college (introductie+begin verzamelingen) staan inmiddels op de website. Een paar kleine foutjes zijn verbeterd. De bedoeling is de slides van elk college vanaf college 2 op de website te zetten ruim voordat het college begint. Voor college 2 zet ik ze donderdagmiddag online.

30-08-2018 - Het eerste college is op dinsdag 4 september van 9:00 tot 10:45 uur in collegezaal C1 van het Gorlaeus (het ronde collegegebouw).

Programma

Hieronder wordt het programma voor het hoorcollege/werkcollege van het najaar 2018 bijgehouden. Voor elke week staat daarin vermeld welke onderwerpen aan de orde zijn gekomen met de bijbehorende hoofdstukken/paragrafen uit het boek, de gebruikte slides en de opgaven die bij het werkcollege behandeld zijn. In principe worden de sheets de ochtend of de dag voor het college op de site gezet; direct na het college komt de definitieve versie hieronder te staan.


Weeknummer Onderwerp Schaum Slides Werkcollege: opgaven
36 Intro, verzamelingen I, verzamelingen II 1.1-4, 1.6 intro, verzamelingen1, verzamelingen2 geen werkcollege
37 Verzamelingen III, Relaties I 1.5, 1.7, 2.1-2 verzamelingen3, relaties1 3, 2, 4, 7acd, 9ab, 10, 11
38 Relaties II 2.3-6 relaties2 geen werkcollege
39 geen college --- --- rest (10, 11), 5, 13, 8, 15, 16
40 Relaties III, Functies I 2.6-9, 3.1-3 relaties3, functies1 extra, 17 (niet b), 18, 19half, 20, 22, 21
41 Functies II, Grafen I 3.5, 8.2-3 functies2, grafen1 23ac, extra, 26, 24, 25, 27, 28
42 Grafen II 8.4-7,9.1-3,9.5(#),9.9 grafen2 29, 30, 31, 32, 33, 34, 36, extra
43 TOETS op donderdag --- --- ---
44 Combinatoriek, Inductie/recursie I 5.1-5, 3.6 combinatoriek, recursie1 1 t/m 5, 1 t/m 3, 37
45 Inductie/recursie II, Bomen I 1.8, 11.3, 8.8, 9.4 recursie2, bomen1 38, 39c, 40, 46, 50, 5, 6, 7
46 Bomen II 8.8, 9.4, 10.1-3, 10.5, 10.9 bomen2 52, 53, 54, 55, 56, 47bc, extra(, 57a)
47 Formele talen 12.1-4 talen college op vrijdag
48 Aftelbaarheid, modulo rekenen 2.8, 3.7, 3.4, 11.8 equivalentierelaties 58, 59, 60bcde, 61abc, 63, 64, extra
49 Eindige automaten 12.5 eindige automaten 66, 68, 69, 71, 72, 74
50 Oud Tentamen ... Tentamen van maart 2018 72b, 74b, 75, 76

(#) alleen de adjacency matrix representatie


Tentamen

Halverwege het semester is er een schriftelijke toets, die vooral bedoeld is als een soort test voor jezelf. De toets kan ook een kleine bonus opleveren. Indien het cijfer van zowel tentamen als toets >= 5,0 is geldt: eindcijfer = tentamencijfer + (toetscijfer/10); anders eindcijfer = tentamencijfer.

De tussentoets is op donderdag 25 oktober 2018 van 9:00 tot 11:00 uur. Locatie: Snellius.
Het tentamen is op maandag 7 januari 2019 van 14:00 tot 17:00 uur. Op vrijdag 4 januari is er een vragenuur. Aanvang: 14.00 uur. Plaats: in het Snellius. De zaal wordt t.z.t. bekendgemaakt via deze webpagina.
Op dinsdag 12 maart 2019 is de herkansing (van 14:00 tot 17:00 uur).

Er zijn enige oude tentamens en tussentoetsen Fundamentele Informatica 1 beschikbaar om mee te oefenen. Deze zijn hieronder te vinden, inclusief uitwerkingen.



Vragen en/of opmerkingen kunnen worden gestuurd naar: j.m.de.graaf@liacs.leidenuniv.nl.

Laatste wijziging 8 januari 2019 liacs.leidenuniv.nl/~graafjmde/FI1/