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ó    

    Introduction to the Theory of Computing 1

    A tantárgy neve magyarul / Name of the subject in Hungarian: Bevezetés a számításelméletbe 1

    Last updated: 2018. december 18.

    Budapest University of Technology and Economics
    Faculty of Electrical Engineering and Informatics
    Course ID Semester Assessment Credit Tantárgyfélév
    VISZAA03   2/2/0/v 5  
    3. Course coordinator and department Dr. Szeszlér Dávid,
    Web page of the course http://cs.bme.hu/bsz1-english
    4. Instructors

    Dr. Rita Csákány, associate professor, Department of Computer Science and Information Theory

    Dr. Tamás Fleiner, associate professor, Department of Computer Science and Information Theory

    Dr. Péter Pál Pach, associate professor, Department of Computer Science and Information Theory

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

    Dr. Gábor Simonyi, 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("BMEVISZA103", "jegy", _) >= 2
    VAGY
    TárgyEredmény("BMEVISZA103", "felvétel", AktualisFelev()) > 0
    VAGY
    TárgyEredmény("BMEVISZAA00", "jegy", _) >= 2
    VAGY
    TárgyEredmény("BMEVISZAA00", "felvétel", AktualisFelev()) > 0
    VAGY
    TárgyEredmény( "BMEVISZAA00" , "aláírás" , _ ) = -1)

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

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

    A kötelező előtanulmányi rendek grafikus formában itt láthatók.

    7. Objectives, learning outcomes and obtained knowledge

    The goal of the subject is to acquire the fundamental mathematical knowledge (in the area of linear algebra and number theory) necessary for software engineering studies. 

    Students successfully completing the course will be able to:

    • (K3) understand and apply the notions and the knowledge covered by the course;
    • (K3) individually solve practical problems related to the material of the course;
    • (K2) apply the algorithms covered by the course;
    • (K3) during their further studies, identify situations where fields of knowledge covered by the course are applicable and apply them successfully.
    8. Synopsis

    1) Coordinate geometry in the space: vectors in the space, coordinate system, scalar product. The equation of a plane. The (parametric and canonic) system of equations of a line. The notion of Rn, operations on column vectors.

    2) The notion of a subspace of Rn, the property of being closed under operations. The notions of linear combination, generating system, spanned subspace. The notion of linear independence, the equivalence of the two definitions.

    3) Relation between the sizes of linearly independent systems and generating systems in subspaces. The notions of basis and dimension, the unicity of the dimension. The unicity of representing a vector with respect to a basis.

    4) Solving systems of linear equations with the Gaussian elimination. The notions of row reduction, echelon form and reduced echelon form. Relation between the number of equations and the number of variables of uniquely solvable systems.

    5) The definition of the determinant. The number of inversions in permutations. Basic properties of the determinant. Computing the determinant with the Gaussian elimination. Characterizing the unique solvability of (n x n) systems of linear equations with the determinant.

    6) Determinant expansion by minors. The cross product and the mixed product of 3-dimensional vectors. The relation of the mixed product to the determinant. Operations on matrices, identity matrix, transposed matrix. The determinant of the product matrix.

    7) Expressing systems of linear equations on the Ax=b form. Connections between the linear independence of the rows and the columns. The notion of the inverse matrix, necessary and sufficient condition on its existence. Computing the inverse. The notion of the rank of a matrix.

    8) Equality of the three types of rank notions. Computing the rank of a matrix. The notion of a linear map, necessary and sufficient condition on the linearity of a map.

    9) The composition of linear maps, addition formulas for the sin and cos functions. The kernel and the image of linear maps, the rank-nullity theorem.

    10) Basis transformation, the matrix of a linear transformation with respect to a basis, computing this matrix. The notions of the eigenvalue and the eigenvector of a square matrix, computing the eigenvalues, characteristic polynomial.

    11) The basic notions of number theory: divisibility, prime numbers, the fundamental theorem of arithmetics, the cardinality of primes, the gap between adjacent primes, the prime number theorem. The notion of congruence, operations on congruences. Solvability of linear congruence equations.

    12) Euclidean algorithm for computing the greatest common divisor and for solving linear congruence equations. Linear diophantine equations on two variables, simultaneous linear congruences. Euler's totient theorem, Fermat's little theorem.

    13)  Arithmetic algorithms: relation between the size of the input and the logartihm of the input data, basic operations, exponentiation modulo m, primality testing. Public key cryptography, the RSA code.

    9. Method of instruction

    2 hours of lecture and 2 hours of problem solving each week.

    The lecture introduces new theory and the role of practice classes is to deepen the acquired knowledge by applying it on problems. Since practice classes closely follow the material of corresponding lectures, a thorough knowledge of the material covered by the lectures is expected from the students. The common work done on practice classes (including homeworks) is an inherent part of the learning process. Lectures in most cases build on the material of previous weeks, it is typically impossible to follow the new material without the preliminary knowledge provided by them.

    10. Assessment

    Signature:

    There are two midterms during the semester, each containing 6 questions worth 10 points each.
    To obtain a signature you have to achieve at least 30% (i.e. at least 18  points) on each of the two midterm tests (or the repeat midterm), and the average result of the two midterms should be at least 40% (i.e. the total points from the two midterms should be at least 48).

    There are two repeat midterms, one during the semester, and one in the repeat week. At each you can repeat any one of the two midterms.
    On the first repeat test you can repeat a midterm to improve your grade as well. In this case the points obtained on the repeat are considered, regardless whether it is better or worse than the original midterm. The only exception is that a signature obtained cannot be lost by writing a bad repeat midterm. 

    Final:

    Oral exam.

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

    There will be 2 retake occasions. In both cases, either one of the two midterms can be retaken (but not both).

    13. References, textbooks and resources

    Linear Algebra:

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

    Primality testing:  https://en.wikipedia.org/wiki/Fermat_primality_test

    Public key cryptosystems: https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29

    14. Required learning hours and assignment
    In class56
    Preparation for lectures
    6
    Preparation for practice classes 15
    Preparation for midterms
    30
    Preparation for the final
    43
      
    Total150
    15. Syllabus prepared by Dr. Dávid Szeszlér, associate professor, Department of Computer Science and Information Theory