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

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

Dr. Tamás Fleiner, 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 emeritus, 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

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

The objective of the subject is the acquisition of some basic mathematical knowledge necessary for software engineering studies and belonging to basic engineering education, and the development of their approach. Within this, the course provides an introduction to some areas of linear algebra and elementary number theory.

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;

• (K2) proving certain theorems and the correctness of 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.

Synopsis

1-2. The basic notions of number theory: divisibility, prime numbers, the fundamental theorem of arithmetic, the cardinality of primes, the prime number theorem. The notion of congruence, operations on congruences.

3-4. Linear congruences, solution of simultaneous congruence systems. Euler-Fermat theorem, Fermat's little theorem. The notion of polynomial algorithm, the efficiency of number-theoretic algorithms.

5-6. Arithmetic algorithms: basic operations, exponentiation modulo m, Euclidean algorithm for computing the greatest common divisor and for solving linear congruences, primality testing. Public key cryptography, the RSA algorithm.

7-8. Coordinate geometry in the space: vectors in the space, coordinate system, scalar product. The equation of a plane. The (parametric and canonical) system of equations of a line. The notion of Rⁿ, operations on column vectors.

9-10. The notion of a subspace of Rⁿ, 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.

11-12. Relation between the sizes of linearly independent systems and generating systems in subspaces. The notions of basis and dimension, the clarity of the dimension. The clarity of representing a vector relative to a basis, the notion of the coordinate vector.

13-14. 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.

15-16. 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.

17-18. The (Laplace) expansion theorem for determinants.. The cross product of 3-dimensional vectors, its relation to the determinant. Operations on matrices, identity matrix, transposed matrix. The determinant of the product matrix.

19-20. Expressing systems of linear equations in the Ax=b form. Connection between the linear independence of the rows and the columns of square matrices and the determinant. The notion of the inverse matrix, necessary and sufficient condition on its existence. Computing the inverse. The notion of the rank of a matrix, the calculation of the rank.

21-22. Equality of the three types of rank notions. The notion of a linear map, necessary and sufficient condition on the linearity of a map. Composition of linear maps, addition formulas for the sine and cosine functions.

23-24. The kernel and the image of linear maps, the dimension theorem. Basis transformation, the matrix of a linear transformation with respect to a basis, its calculation.

25-26. The notions of the eigenvalue and the eigenvector of a square matrix, computing the eigenvalues, characteristic polynomial.

27-28. Repetition, summary, systematic review of the material studied. Description of the current list of exam questions for the oral exam and the detailed expectations related to each exam question.

Detailed topics of the exercises/labs

Same as the theme of the lectures from week to week. 

Method of instruction

4 hours of lecture per week followed by 2 hours of practice per week.

At the lectures, the new theoretical material is presented, and the concepts, theorems, proofs and algorithms learned are illustrated through examples and exercises.

In the practices the students can practice the material and apply it in the exercises.

The practices are always closely related to the material of the corresponding lecture, therefore students are expected to know the material learned in those lectures. The knowledge discussed in the lectures is deepened in the practices, the work that takes place here (including solving homework) is a fundamental part of the learning process. In most cases, the lectures are closely based on the material of the previous weeks, without knowledge of these the new material cannot usually be followed.

In the study period

During the semester the students will write two midterms. The condition for obtaining the signature (that is, for the admission to the exam) is to obtain at least 24 points out of the 60 points that can be obtained in each of the midterms. Students who have a valid signature from a previous semester can attempt to rewrite the midterms to improve on the results of their previous midterms. In this case the following conditions apply:

If they manage to fulfill the conditions necessary for the signature again, the result obtained in this way will count towards their exam mark (even if it is lower than before).

If they fail to fulfill the conditions necessary for the signature again, the signature will not be 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 of the midterms in the current semester, it is considered that the person has made an attempt to fulfill the conditions of the signature again (and the above conditions apply to him/her). Otherwise, the performance of the last semester in which the student attempted to fulfill the conditions of the signature will be taken into account.

In the examination period

Students with a valid signature can apply for the exam.

The exam is oral.

The final mark is formed from the results of the midterm tests and the oral performance in the exam in such a way that the average of the midterms counts up to 40 percent, and the oral exam up to 60 percent. If the oral exam is insufficient , then the final mark is a fail (regardless of the result of the midterms). In the case of a repeat exam, the results obtained from the midterms are still valid.

In more detail: the score determining the final mark is calculated using the following formula, where mt1 and mt2 are the points obtained in the first and second midterms, respectively, and e is the score obtained in the oral exam (the maximum value of which is 60).

final_score = 0,4 × min(50,mt1) + 0,4 × min(50,mt2) + 1,2 × min(50,e).

We provide one make-up opportunity for both midterms (during the study period or in the retake week). These can be used to replace the corresponding midterm or to improve its result. In the latter case, the new score will be valid, even if it is worse than the original. There is one exception to this: the already obtained signature and the minimum score for obtaining it in the given midterms cannot be lost by an unsuccessful retake attempt. If someone shows up at a retake midterm (and receives the test), we consider that person to have attempted to write the midterm (and thus the above conditions apply to him/her).

In addition, we also provide a retake opportunity with a fee (in the retake week or the first week of the exam period), which can be used to replace one (but not both) of the two midterms. Only those students who have not yet obtained a signature based on the results of the two midterms and the two retake midterms and who do not have a valid signature from a previous semester can participate in the retake with a fee. Thus, the retake with a fee cannot be used to improve the result of a midterm previously successfully completed.

We offer consultations before the exams.

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