Syllabus:

**Swedish name: **Diskret modellering

**This syllabus is valid: **2020-08-17
and until further notice

**Course code: **5MA174

**Credit points: **7.5

**Education level: **Second cycle

**Main Field of Study and progress level: **
Mathematics: Second cycle, has second-cycle course/s as entry requirements

**Grading scale: **TH teknisk betygsskala

**Responsible department: **Department of Mathematics and Mathematical Statistics

**Revised by: **Faculty Board of Science and Technology, 2020-03-26

Module 1 (4.5 ECTS): Theory of discrete modelling.

This part of the course treats theory for discrete modelling, from problem formulation and choice of model, via specific model formulation and implementation, to evaluation of appropriateness and effectiveness of the model.

This part of the course starts with general theory for formulating an integer program from a given problem description, and general theory for SAT formulations of optimization and decision problems. In connection to this, complexity theory and the general theory of polynomial reduction from one problem to another.

Integer formulations and SAT formulations are then connected to different classes of graph models, in particular matchings, the travelling salesman problem. In addition to this, Hamilton cycles, Euler cycles, assignment problems and stable matchings are studied.

Both exact and heuristic models are studied with regard to effectiveness. Artificial intelligence is treated by means of an introduction to genetic algorithms, especially for the travelling salesman problem.

Following this, concrete large scale examples of applied discrete modelling are studied, and an introduction to literature search in the area of discrete modelling is given. The theory is concluded with an introduction to simulation using randomized scenarios.

Module 2 (3 ECTS): Lab assignment.

This part of the course treats implementation of discrete models, and comparisons between different formulations as regards computational efficiency. To handle problems where solution to optimality is not feasible, simulation methods for discrete models are implemented. Finally, methods from the broadly construed area of artificial intelligence are treated, such as genetic algorithms and simulated annealing.

- thoroughly account for the theory of discrete modelling
- thoroughly account for SAT formulations and their connection to complexity theory and problem reduction

- independently formulate integer-, graph- and model and SAT-models for given problem situations
- independently perform reductions from one problem type to another
- account for the modelling of a concrete problem orally and in written form
- generate scenarios for testing models

- assess appropriateness and efficiency for different model formulations
- assess the possibility of exact solutions and approximations of solutions for different instances of the types of problems treated in the course
- independently find literature and assess its relevance and usefulness

Deviations from the syllabus examination form can be made for a student who has a decision on pedagogical support due to disability. Individual adaptation of the examination form shall be considered based on the student's needs. The examination form is adapted within the framework of the expected learning outcomes of the course syllabus. At the request of the student, the course coordinator, in consultation with the examiner, must promptly decide on the adapted examination form. The decision shall then be communicated to the student.

A student who has not received a passing grade after participating in two tests has the right to be assigned another examiner, unless there are certain circumstances prohibiting this (see the Higher Education Ordinance, chapter 6, 22§). A request to be assigned another examiner should be adressed to the head of department for the department of mathematics and mathematical statistics. The possibility of being examined based on the current version of the syllabus is guaranteed for two years following the student's first participation in the course.

All students have the right to have their previous education or equivalent, and their working life experience evaluated for possible consideration in the corresponding education at Umeå university. Application forms should be adressed to Student services/Degree evaluation office. More information regarding credit transfer can be found on the student web pages of Umeå university, http://www.student.umu.se, and in the Higher Education Ordinance (chapter 6). If denied, the application can be appealed (as per the Higher Education Ordinance, chapter 12) to Överklagandenämnden för högskolan. This includes partially denied applications.

**Annat material (tillhandahålles av inst.)**

Matematik och Matematisk statistik :