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: 2022. június 10.

    Budapest University of Technology and Economics
    Faculty of Electrical Engineering and Informatics     		Electrical Engineering
    BSc
    Course ID Semester Assessment Credit Tantárgyfélév
    VISZAA07 1 3/2/0/v 5  
    3. Course coordinator and department Dr. Fleiner Tamás,
    Web page of the course www.cs.bme.hu/fcs
    4. Instructors Dr. Attila Sali, associate professor, Department of Computer Science and Information Theory
    7. Objectives, learning outcomes and obtained knowledge
    The objective of the subject is to acquire some basic mathematical knowledge and approach to the study of electrical engineering and the basic engineering literacy. In this context, the subject provides an introduction to certain areas of linear algebra and graph theory.
    Students who successfully complete the course will be able to:
    - understand and apply the concepts and knowledge introduced in the subject;
    - independently solve practical problems related to the material;
    - apply the algorithms covered in the course;
    - recognise situations in which the knowledge acquired in the course is relevant and apply it successfully in later studies.
    8. Synopsis
    1. Basic concepts of graph theory. Degrees of graphs, components, paths, walks, edge series, isomorphism. Trees and forests, their simple properties.
    2. Spanning tree, fundamental circle system, fundamental cut system. Minimum cost spanning tree, Kruskal's algorithm.
    3. Concept of graph entry, classification of edges, BFS. Shortest paths and properties of BFS, shortest path tree. Augmentation on edges, Dijkstra's algorithm.
    4. Ford and Floyd's algorithms. Depth first search, searching directed cycles, characterization of acyclic graphs. PERT problem, algorithm for solution.
    5. Euler's trail and circuit, necessary and sufficient conditions for their existence (for connected graphs). Necessary and sufficient conditions for the existence of a Hamiltonian cycle: Dirac's and Ore's theorems and number of components after vertex deletion.
    6. Graph drawing on the plane and the sphere. Euler's polyhedron theorem and its consequences for simple planar graphs. Kuratowski graphs, series expansion, Kuratowski's theorem. Dual of a planar graph. Truncating edges, series edges, truncation. Properties of dual graph (edge number, vertex number, connectedness, cycle-cut duality, its special cases). Chromatic number of planar graphs, four-colour theorem.
    7. Solving systems of linear equations by Gaussian elimination. Concepts of elementary series equivalent step, stepwise form and reduced stepwise form. Relationship between equations and the number of unknowns and the uniqueness of the solution.
    8. Linear combinations, generated subspace (and its subspace nature), generator system. Linear independence (two definitions and their equivalence). Lemma of the new vector. I-G inequality.
    9. Concepts of base and dimension, uniqueness of dimension. Standard base, dimension of Rn. Concept of coordinate vector and its uniqueness. Existence of base in arbitrary subspace of Rn.
    10. Definition of determinant. Inversion number of permutations. Basic properties of determinant. Calculation of determinant by Gauss elimination. The Laplace Expansion Theorem. 
    11. Operations with matrices (addition, multiplication by scalar, multiplication, transposition), their properties. The determinant of the transposed matrix. Multiplication theorem of determinants (without proof). Linear mappings.
    12. Inverse of a matrix, necessary and sufficient conditions for its existence, calculation of inverse. Rank of matrices, equality of rank concepts, definition of rank. Characterization of the unique solvability of systems of linear equations n × n using the determinant. Relationship between systems of linear equations, the question of membership of a generated subspace in Rn and matrix equations based on matrix multiplication. Relationship between determinants of quadratic matrices and linear independence of rows and columns. 
     
    This topic was developed in consultation with the Institute of Mathematics.


    9. Method of instruction
    The course consists of 3 hours of lectures per week and 2 hours of small group practice session per week.
    The lectures introduce the new theory and the exercises provide practice and application of the theory in exercises. The exercises are always closely related to the material of the corresponding lecture and therefore students are expected to be familiar with the material taught in the lecture. The concepts and knowledge covered in the lectures are practised and deepened in the exercises, and the work done here (including homework) is an essential part of the learning process. In most cases, the lectures are closely based on the material of the previous weeks, without which the new material cannot usually be followed.

    10. Assessment Signature: During the semester the students will write two midterms. To obtain the signature, you must achieve at least 40% in each of the midterms.
    Students who have a valid signature from a previous semester may attempt to re-write their midterms to improve on the results of their previous midterms. In this case, the following conditions apply:
    If you manage to meet the conditions for the signature again, the result obtained will count towards your exam mark (see below) (even if it is lower).
    If you fail to meet the signature requirements again, the signature is not lost, but only the minimum score required to obtain the signature will be counted towards the mark.
    If a student with a valid signature appears in at least one final exam in the current semester, he/she will be considered to have attempted to re-sign (and will be subject to the above conditions). Otherwise, the last semester performance in which the student attempted to re-sign will be taken into account.
     
    Exam:  You can apply for the exam if you have a valid signature. The exam  is oral. 
    The final mark is the weighted average of the results of the two midterms and the oral performance in the exam, with the midterm weighted 2 and the oral exam weighted 3. If the oral exam is unsatisfactory, the final mark is also unsatisfactory (regardless of the result of the midterms). In the case of a repeat examination, the results of the midterms are valid.
    The final mark  is calculated using the following formula (mt1 and mt2 are the marks obtained in the first and second midterm and e is the mark obtained in the oral examination).
    final_point = 0,4*(min(50,mt1) + min(50,mt2)) + 1,2*min(50,e). 
    The final grade is based on the final score: 0-39: unsatisfactory, 40-54: fair, 55-69: average, 70-84: good, 85-100: excellent.
    The examination topics for varies from semester to semester, the list of topics for the current semester can be downloaded from the subject's departmental website from the last week of the semester.
    No preliminary examinations are held.


    11. Recaps
    For each of the two midterms, you will be given one make-up opportunity (during the term or in the make-up week). These can be used to make up the corresponding midterms or to improve your score. In the latter case, the new score will be valid, even if it is lower than the original. There is one exception to this rule: the signature already obtained and the minimum score required to obtain it in a given midterm cannot be lost by a failed attempt to correct it. If a person appears in a make-up midterm (and takes the paper), they are considered to have made an attempt to write the paper (and are therefore subject to the above conditions). 

    A person who has not obtained a signature and has not obtained a signature at a make-up session, but who has obtained a signature by successfully completing one paper, is entitled to attend the make-up session for which a fee is charged. This must be registered at the Neptune and is subject to a special procedure fee. A make-up, for which a fee is charged, is an examination from the corresponding final written under the same conditions as the final.
    12. Consultations By appointment.
    13. References, textbooks and resources

    M. O. Albertson, J. P. Hutchinson: Discrete Mathematics with Algorithms, Wiley, 1988

    Peter Selinger: Matrix Theory and Linear Algebra (https://www.mathstat.dal.ca/~selinger/linear-algebra/downloads/LinearAlgebra.pdf)

    14. Required learning hours and assignment
    Kontakt óra70
    Félévközi készülés órákra28
    Felkészülés zárthelyire14
    Házi feladat elkészítése6
    Kijelölt írásos tananyag elsajátítása
    Vizsgafelkészülés32
    Összesen150
    15. Syllabus prepared by Dr. Tamás Fleiner, associate professor, Department of Computer Science and Information Theory