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ó    

    Theory of Algorithms

    A tantárgy neve magyarul / Name of the subject in Hungarian: Algoritmuselmélet

    Last updated: 2012. november 23.

    Budapest University of Technology and Economics
    Faculty of Electrical Engineering and Informatics
    Course ID Semester Assessment Credit Tantárgyfélév
    VISZA213 4. 2/2/0/v 5 1/1
    3. Course coordinator and department Dr. Friedl Katalin,
    6. Pre-requisites
    Kötelező:
    (TárgyEredmény( "BMEVISZA110" , "aláírás" , _ ) = -1
    VAGY TárgyEredmény( "BMEVISZA031" , "jegy" , _ ) >= 2
    VAGY TárgyEredmény( ahol a TárgyKód = "BMEVIMA1236", ahol a Típus = "VIZSGA", ahol a Ciklus = tetszőleges, ahol a KépzésKód = tetszőleges) >=2
    VAGY Aláírás( ahol a TárgyKód = "BMEVIMA2603", ahol a Ciklus = tetszőleges)
    VAGY TárgyEredmény( "BMEVISZA071" , "jegy" , _ ) >= 2 )
    VAGY KépzésLétezik( ahol a KépzésKód = "9N-MM09")

    ÉS
    NEM ( TárgyEredmény( "BMEVISZAB01" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZAB01", "FELVETEL", AktualisFelev()) > 0)

    ÉS Training.Code=("5N-A8")

    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 objective is to provide the students with the fundamental methods and skills to design and analyze algorithms.

     

    Obtained skills and expertise:

     

    Design and analysis of algorithms.

     
    8. Synopsis Algorithms. Sequential and binary search. Search with some basic data structures, like search tree, AVL tree, B-tree, hash table. Sorting by insertion, merge sort, heap sort, quicksort, bin sort, radix sort and the analysis of these methods. The complexity of sorting. Basic graph theoretical algorithms: BFS, DFS and their applications to determine (strongly) connected components. Algorithms for acyclic graphs. Finding maximal matching in bipartite graphs. Determining shortest paths by methods of Bellman-Ford, Dijkstra, and Ford. Minimal spanning tree algorithms and the union-find data structure. General algorithmic methods: branch and bound, divide and conquer, dynamic programming. Efficient approximation algorithms. Algorithmically hard problems, the notion of NP and NP-completeness.

     
    13. References, textbooks and resources T. Corman, C. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms, Second Edition, MIT Press, 2001.
    14. Required learning hours and assignment
    Kontakt óra
    Félévközi készülés órákra
    Felkészülés zárthelyire
    Házi feladat elkészítése
    Kijelölt írásos tananyag elsajátítása
    Vizsgafelkészülés
    Összesen