IT-Universitetet i København
  Tilbage Kursusoversigt
Kursusnavn (dansk):Grundlæggende strukturer for beregninger - Diskret Matematik 
Kursusnavn (engelsk):Foundations of Computing - Discrete Mathematics 
Semester:Efterår 2010 
Udbydes, softwareudvikling og -teknologi (sdt) 
Omfang i ECTS:7,50 
Min. antal deltagere:12 
Forventet antal deltagere:20 
Maks. antal deltagere:80 
Formelle forudsætninger:Basic ability to program in some imperative programming language (Java, Python, C/C++/C#, etc.), using conditions, loops, arrays, methods/procedures/functions, and simple recursion. This may be obtained by following Object Oriented Programming - Introduction, or Introductory Programming or similar courses.  
Læringsmål:After the course the student should be able to:

* Recognize if a concept is described by a formal definition, and recognize if a simple formal proof is correct, including those that use recursion and induction

* Express simple concepts in the language of mathematics

* Bound the growth rate of functions using asympotic analysis

* Solve recurrence relations, including divide-and-conquer relations

* Enumerate combinatorial structures, assess probabilities of events,
and compute expectations of random variables

* Model phenomena using discrete structures such as relations, graphs, logic, or finite-state machines
Fagligt indhold:The course is a standard introduction to discrete mathematics, but
with focus on applications in the information technologies. In
particular, the course develops the necessary terminology and
conceptual tools needed for later courses such as Advanced Models and Programs, Algorithm Design, Database Tuning, Mobile and Distributed Systems and Efficient AI Programming). This includes,

* the analysis of algorithms, including basic randomised algorithms,

* models of computation, such as logic and automata

* databases, such as relations and functions

* models of networks (technological as well as social), such as graphs

The course emphasises the applicability of these by describing their applications, including a research article. Applications are expected to vary, but can include Google's PageRank algorithm, natural language processing, Bayesian spam filters, models for social networks, or data mining.

Central terms and concepts: Logic, sets and sequences, functions, sums, induction and recursion, permutations and combinations, discrete probability, recurrence relations, relations, graphs, trees, boolean Algebra, finite state machines, grammars.  
Læringsaktiviteter:14 ugers undervisning bestående af forelæsninger og øvelser

14 weeks of teaching consisting of lectures and exercises
Around 14 lectures with exercise classes. Twice a week for the first 5 weeks. A larger project corresponding to half the course. All material will be made available on the Web.

Study structure
This course is mandatory for students who are enrolled on the Development Technology track on SDT. See the track described here:
Development Technology.

I intro-ugen (uge 5) er der ændrede kursustidspunkter:
Link til skemaoplysninger

In the intro week (week 5) the course time table is changed:
Link to the time table


NB!! Course restriction I!!
Please note that there is a course restriction between this course and the SDT course Modelling and Design.
If you have already taken Modeling and Design you need to register for the course Foundations of Computing - Algorithms and Data Structures.  

Eksamensform og -beskrivelse:X. experimental examination form (7-scale; external exam), 7-trins-skala, Ekstern censur

Students need to hand in 3 mandatory assignments before December 3 2010 in order to be eligible for the exam.  

Litteratur udover forskningsartikler:Kenneth Rosen, Discrete Mathematics and Its Applications, 6/e, McGraw Hill, ISBN: 007288008  
Afholdelse (tid og sted)
Kurset afholdes på følgende tid og sted:
Tirsdag 08.30-10.30 Forelæsning ITU 4A16
Tirsdag 10.45-12.45 Øvelser ITU 4A16
Torsdag 08.30-10.30 Forelæsning ITU 2A14
Torsdag 10.45-12.45 Øvelser ITU 2A14

Eksamen afholdes på følgende tid og sted:
2011-01-04 09:00-11:30 (sammen med Algor. & DS. til 13:30) Skriftlig eksamen ITU 4A14 og 4A16
2011-03-09 Re-eksamen Skriftlig eksamen ITU 4A30 - MUNDTLIG EKSAMEN
2011-03-09 Re-eksamen - Kontakt kursusansvarlig for tidspunkt Skriftlig eksamen ITU Eksamensform kan blive ændret / Examination form may be altered