311.265 (17S) Selectied Topics in Discrete Mathematics

Sommersemester 2017

Registration deadline has expired.

First course session
01.03.2017 16:00 - 17:30 N.2.01 On Campus
... no further dates known

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 modi cations.
  • Collaborations with the professor are welcome!

Time and place

List of events is loading...

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

Im Fall von online durchgeführten Prüfungen sind die Standards zu beachten, die die technischen Geräte der Studierenden erfüllen müssen, um an diesen Prüfungen teilnehmen zu können.

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 fi nal (20%).

Grading scheme

Grade / Grade grading scheme

Position 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)
  • 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)

Equivalent courses for counting the examination attempts

This course is not assigned to a sequence of equivalent courses