Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással
    vissza a tantárgylistához   nyomtatható verzió    

    Advanced Mathematics for Informatics - System Optimisation

    A tantárgy neve magyarul / Name of the subject in Hungarian: Felsőbb matematika informatikusoknak - Rendszeroptimalizálás

    Last updated: 2016. január 14.

    Budapest University of Technology and Economics
    Faculty of Electrical Engineering and Informatics     		MSc degree program in Software Engineering
    Course ID Semester Assessment Credit Tantárgyfélév
    VISZMA02 1 4/0/0/v 4  
    3. Course coordinator and department Dr. Szeszlér Dávid,
    Web page of the course http://cs.bme.hu/rendszeropt
    4. Instructors

    Dr. András Recski, professor, Department of Computer Science and Information Theory

    Dr. Dávid Szeszlér, associate professor, Department of Computer Science and Information Theory 

    Dr. Gábor Wiener, associate professor, Department of Computer Science and Information Theory 

    6. Pre-requisites
    Kötelező:
    NEM ( TárgyEredmény( "BMEVISZM117" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZM117", "FELVETEL", AktualisFelev()) > 0
    VAGY
    TárgyEredmény( "BMEVISZMA10" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZMA10", "FELVETEL", AktualisFelev()) > 0)

    A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

    A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

    7. Objectives, learning outcomes and obtained knowledge

    The subject introduces some areas of operations research and combinatorial optimization. Besides covering the most relevant algorithms and methods and their limits, it also aims at giving a glimpse into some of their engineering applications. Thus the subject also covers some general algorithmic approaches like linear and integer programming and matroid theory. Furthermore, the course aims at extending and deepening the knowledge formerly provided by the Introduction to the Theory of Computing 1 and 2 and the Theory of Algorithms subjects of the BSc degree program in Software Engineering.

    8. Synopsis Linear programming. Methods of solution, Farkas' lemma,
    duality, integer programming, branch and bound, totally unimodular
    matrices.
    Matroid theory. Basic notions, greedy algorithm, duality, minors,
    direct sum, algorithms, Tutte's and Seymour's theorems, rank function,
    matroid matching.
    Approximation algorithms. Additive and relative error, examples.
    Scheduling algorithms. Types, algorithms of Hu, Coffman and Graham.
    Reliable network design. Local edge connectivity, edge connectivity
    number, algorithms of Nagamochi and Ibaraki, Karger, Khuller and
    Vishkin, Cheriyan and Thurimella, Plesnik.
    Applications in electrical networks and statics. Kichhoff's theorems,
    rigidity of frameworks.
    9. Method of instruction 4 hours of lecture per week
    10. Assessment

    Signature:

    1 midterm during the semester the result of which has to be at least 40%.

    Final:

    Oral exam.

    11. Recaps 2 occasions for retaking the midterm will be provided (the second one in the week preceding the exam period).
    12. Consultations Subject to individual arrangements.
    13. References, textbooks and resources Foulds, L. R. (2012). Combinatorial optimization for undergraduates. Springer Science & Business Media.
    14. Required learning hours and assignment
    In class56
    Preparation for classes 12
    Preparation for midterms 12
    Homework 
    Reading assignment 
    Preparation for final 40
    Total 120
    15. Syllabus prepared by Dr. Dávid Szeszlér, associate professor, Department of Computer Science and Information Theory