311.265 (17S) Selectied Topics in Discrete Mathematics
Overview
- Lecturer
- Course title german Ausgewählte Kapitel der Diskreten Mathematik (Algebraic Methods in Discrete Optimization)
- Type Lecture - Practical class (continuous assessment course )
- Hours per Week 3.0
- ECTS credits 5.0
- Registrations 12 (25 max.)
- Organisational unit
- Language of instruction English
- Course begins on 01.03.2017
- eLearning Go to Moodle course
-
Remarks (english)
- Please forgive the professor her poor German!
- Students should bring their laptops to each class meeting, as coding demonstrations can happen at any time.
- Students are encouraged to work with classmates and others in learning the material.
- Phones and other distracting devices should be off during class.
- If you know you are going to be absent on a particular day, it is common courtesy to notify the instructor in advance, preferably by email.
- Information in this Course Policy Statement is subject to minor modications.
- Collaborations with the professor are welcome!
Time and place
Course Information
Intended learning outcomes
By the end of this course students will be able to:
(1) Model discrete combinatorial problems as systems of polynomial equations, and then solve via a wide range of algorithms.
(2) Construct a small library of computer algebra programs that will aid them in their future research.
Teaching methodology including the use of eLearning tools
Lecture, and coding demostrations.
Course content
Course Topics:
1. Background in ideals, varieties and algorithms
2. Grobner bases
3. Buchberger's critieron
4. Faugere's F4/F5 algorithm
5. Elimination ideals
6. Hilbert's Nullstellensatz
7. Stengle's Positivstellensatz
8. Border bases
9. Combinatorial problems as systems of polynomial equations
10. Hidden Field Equation cryptosystem and algebraic attacks
Literature
An Introduction to Polynomial and Semi-Algebraic Optimization (Lasserre),
Algebraic and Geometric Ideas in the Theory of Discrete Optimization (De Loera, Hemmecke, Köppe),
Ideals, Varieties, and Algorithms (Cox, Little, O`Shea)
Examination information
Examination methodology
There will be one take-home midterm, and a take-home final
Homework: There will be a six to eight homework sets in this course. Each homework set will include programming problems. You are welcome to work in groups of three or less. Collaboration and discussion are encouraged!
Examination topic(s)
All topics from the lecture.
Assessment criteria / Standards of assessment for examinations
The grades will be based on homework (65%), midterm (15%) and final (20%).
Grading scheme
Grade / Grade grading schemePosition in the curriculum
- Bachelor's degree programme Technical Mathematics
(SKZ: 201, Version: 12W.2)
-
Subject: Diskrete Mathematik
(Compulsory elective)
-
Ausgewählte Kapitel der Diskreten Mathematik (
3.0h VU / 5.0 ECTS)
- 311.265 Selectied Topics in Discrete Mathematics (3.0h VU / 5.0 ECTS)
-
Ausgewählte Kapitel der Diskreten Mathematik (
3.0h VU / 5.0 ECTS)
-
Subject: Diskrete Mathematik
(Compulsory elective)
- Master's degree programme Technical Mathematics
(SKZ: 401, Version: 13W.1)
-
Subject: Diskrete Mathematik
(Compulsory elective)
-
Algebraic Methods in Discrete Optimization (
3.0h VU / 5.0 ECTS)
- 311.265 Selectied Topics in Discrete Mathematics (3.0h VU / 5.0 ECTS)
-
Algebraic Methods in Discrete Optimization (
3.0h VU / 5.0 ECTS)
-
Subject: Diskrete Mathematik
(Compulsory elective)