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 D

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

    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
    TE90MX43 1 4/0/0/v 4 1/1
    3. Course coordinator and department Dr. Tóth Bálint,
    6. Pre-requisites
    Kötelező:
    NEM ( TárgyEredmény( "BMETE90MX58" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMETE90MX58", "FELVETEL", AktualisFelev()) > 0)

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

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

    8. Synopsis Stochastics 1: 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. Stochastics 2: Review of basic probability theory: random variables, distribution, expectation, covariance matrix, important types of distributions. Types of convergence: stochastic, L^p, almost sure. Borel-Cantelli lemmas. Laws of large numbers, weak convergence of distributions, limit theorems. Generating and characteristic functions and their applications: limit theorems and large deviations (Bernstein inequality, Chernoff bound, Kramer's theorem). Basics of stochastic processes: Markov chains and Markov processes. Markov chains with finite state space: irreducibility, periodicity, linear algebraic tools, stationary measures, ergodicity, reversibility, MCMC. Chains with countable state space: transience, recurrence. Application to birth and death processes and random walks. Basics of continuous time Markov chains: Poisson process, semigroups. Additional topics: percolation, random graphs, phase transition.
    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