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ó    

    Foundation of Computer Science

    A tantárgy neve magyarul / Name of the subject in Hungarian: A számítástudomány alapjai

    Last updated: 2015. november 23.

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

    Electrical Engineering

    BSc

    Course ID Semester Assessment Credit Tantárgyfélév
    VISZAA02 1 2/2/0/v 4  
    3. Course coordinator and department Dr. Katona Gyula,
    Web page of the course www.cs.bme.hu/sza
    4. Instructors Dr. András Recski, professor, Department of Computer Science and Information Theory
    6. Pre-requisites
    Kötelező:
    (Training.Code=("5N-A7") VAGY Training.Code=("5N-A7H")) ÉS

    NEM ( TárgyEredmény( "BMEVISZA105", "jegy" , _ ) >= 2
    VAGY TárgyEredmény("BMEVISZA105", "FELVETEL", AktualisFelev()) > 0
    VAGY TárgyEredmény( "BMEVISZAA05", "jegy" , _ ) >= 2
    VAGY TárgyEredmény("BMEVISZAA05", "FELVETEL", AktualisFelev()) > 0
    VAGY TárgyEredmény( "BMEVISZAA05" , "aláírás" , _ ) = -1)

    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 required theoretical background in combinatorics, algorithmics, elementary cryptography, and graph theory for further studies in electrical engineering.

    Obtained skills and expertise:

     

    Theoretical knowledge and problem solving skills in the treated fields of mathematics.

    8. Synopsis

    Week 1: Basic concepts of combinatorics: permutations, variations, combinations, binomial coefficient, nimonial theorem

    Week 2: Basic concepts of graph theory (vertex, edge, degree, isomorphism). Path, circuit, connectivity, trees.

    Week 3: Shortest path, BFS, Dijkstra, Ford, Floyd algorithms, widest paths in directed and undirected graphs

    Week 4: DFS, directed cycles, fundamental system of cycles and cuts, PERT

    Week 5:  Euler- and Hamiltonian circuits, sufficient and necessary conditions for the existence. Dirac, Ore theorems,

    Week 6: Graph coloring problems (vertex, edge and map coloring). Bipartite graphs. Flows, Ford-Fulkerson theorem, algorithm to find a maximal flow. Integral maximum flow lemma.

    Week 7:  Multiple source flows, vertex capacities, undirected flows.

    Week 8: Bipartite graphs, matchings, Hall's theorem, algorithm to find a maximal matching. Independent and covering vertex and edge sets, König's and Gallai's theorems. 

    Week 9: Planar graphs, duality. Euler's Theorem, Kuratowski's theorem, four color theorem.

    Week 10: Basic concepts of algorithms and complexity. Polynomially solvable and NP-complete problems, coNP.

    Week 11: Karp-reduction, Cook-Levin theorem, famous NP-complete problems: SAT, HAM, 3-COLOR, k-COLOR, MAXSTABLE, MAXCLIQUE, HAMPATH.

    Week 12:  Basic concepts in number theory: divisibility, primes,  fundamental theorem of number theory, number of divisors, distribution of primes

    Week 13: Congruences, diophantine equations, Euler-Fermat theorem,

    Week 14: Algorithms in number theory: prime tests, public key cryptography, RSA. 

    9. Method of instruction 2 hours lecture, 2 hours problem solving
    10. Assessment

    Signature:

    2 midterms during the semester. Both must be at least 30% and at least 40% in average. 2 occasions for retake, each time either one of the test can be retaken.

    Final:

    Oral exam.

    Final grade: 40% midterms, 60% oral exam. 

    13. References, textbooks and resources M. O. Albertson, J. P. Hutchinson: Discrete Mathematics with Algorithms, Wiley, 1988 
    14. Required learning hours and assignment
    In class56
    Preparation for classes14
    Preparation for midterms10
    Homework
    Reading assignment
    Preparation for final40
    Total120
    15. Syllabus prepared by

    Dr. Tamás Fleiner, associate professor

    Department of Computer Science and Information Theory 


    Dr. Gyula Katona, associate professor

    Department of Computer Science and Information Theory

     

    Dr. András Recski, professor

    Department of Computer Science and Information Theory