Belépés címtáras azonosítással
magyar nyelvű adatlap
angol nyelvű adatlap
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: 2015. november 29.
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
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.
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. Determinant expansion by minors.
6) 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. Expressing systems of linear equations on the Ax=b
form. Connections between the linear independence of the rows and the columns
7) The notion of the inverse matrix,
necessary and sufficient condition on its existence. Computing the inverse. The
notion of the rank of a matrix, equality of the three types of rank notions.
Computing the rank of a matrix.
8) The notion of a linear map,
necessary and sufficient condition on the linearity of a map. 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.
9) 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.
10) 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.
11) 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.
12) 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.
13) Cardinality of infinite
sets: the notions of equal and less than or equal cardinalities. The notions of
sets of countably infinite and continuum cardinalities. The cardinality of the
sets N, Z, Q and R.
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 grade: 40% midterms, 60% oral exam.