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ó    

    Advanced Mathematics for Informaticians C

    A tantárgy neve magyarul / Name of the subject in Hungarian: Felsőbb matematika informatikusoknak C

    Last updated: 2012. november 24.

    Budapest University of Technology and Economics
    Faculty of Electrical Engineering and Informatics
    Course ID Semester Assessment Credit Tantárgyfélév
    TE90MX42 1 4/0/0/v 4 1/1
    3. Course coordinator and department Dr. Rónyai Lajos,
    6. Pre-requisites
    Kötelező:
    NEM ( TárgyEredmény( "BMETE90MX57" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMETE90MX57", "FELVETEL", AktualisFelev()) > 0)

    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.

    8. Synopsis

    Mathematical Logics: Formal languages. The language of first order logic. Meta- and object languages. Formalizing sentences. Logical semantics building on set theory. Structures, truth. Consequences. Applications in the Artificial Intelligence. Proof theory. Axiomatizing models. Deduction and refutation systems. Analytic trees, resolution. Consistency and decidability of theories. Proving independency. The elements of logic programming. Mechanical proofs. On the connection of semantics and proof theory, completeness of first order
    logic. Model method. Incompleteness theorems, on the limits of Logic. On the connection of Logic and Algebra. Non-standard analysis. Introductions of the concept of infinitisemal. Complexity theory, logical characterizations.

    Applied Algebra: Linear space, subspace, dimension, basis. Linear map, kernel, image, rank, operations with them. Matrices. Determinants, Eigenvalues and eigenvectors. Diagonalization, spectral decomposition. Euclidean spaces, symmetric, self adjoint, unitary, normal, projector operators and their matrices. Jordan
    normal form. Nonnegative matrices, Frobenius-Perron theorems. Inequalities for the spectral radius. Stochastic matrices. Singular value decomposition, existence, uniqueness, computation, Eckart-Young theorem, applications (least squares method, pseudoinverses, solving homogeneous linear systems). QR-decomposition. Some notable computational applications of linear algebra (indexing with vector spaces,
    error correcting codes, secret sharing, ranking pages in the internet).Existence proofs and randomness: Erdõs' method through examples (2-coloring of hypergarphs, Ramsey numbers) with algorithmic aspects. Turán's theorem. Derandomization. Lovász's local lemma and applications. Analysis of randomized algorithms (expected time of quicksort, Rabin- Miller primality test, Schwartz-Zippel lemma and applications,
    pattern matching, treaps, minimum spanning trees, computing planar autopartitions and convex hulls). Random walks and algorithms, ranking pages in the internet. Randomness and complexity classes (RP, Las Vegas, interactive protocols, IP, BPP, RL with examples, IP=PSPACE). Zero knowledge proofs. Random graphs (Erdõs-Rényi model, Albert-Barabási model). Properties of large networks.

    14. Required learning hours and assignment
    Kontakt óra
    Félévközi készülés órákra
    Felkészülés zárthelyire
    Házi feladat elkészítése
    Kijelölt írásos tananyag elsajátítása
    Vizsgafelkészülés
    Összesen