Скачать 238.92 Kb.

M7. PROBABILITY AND STATISTICS
Students will learn basic probability models with applications. Laws of large numbers, central limit and large deviation theorems will be introduced together with the notion of conditional expectation that plays a crucial role in statistics. While probability theory describes random phenomena, mathematical statistics teaches us how to behave in the face of uncertainties, according to the famous mathematician Abraham Wald. Roughly speaking, we will learn strategies of treating randomness in everyday life.
The first part of the course gives an introduction to probability models and basic notion of conditional distributions, while the second part to the theory of estimation and hypothesis testing. The main concept is that our inference is based on a randomly selected sample from a large population, and hence, our observations are treated as random variables. Through the course we intensively use laws of large numbers and the Central Limit Theorem. On this basis, applications are also discussed, mainly on a theoretical basis, but we make the students capable of solving numerical exercises.
Students will be able to identify probability models, further to find the best possible estimator for a given parameter by investigating the bias, efficiency, sufficiency, and consistency of an estimator on the basis of theorems and theoretical facts. Students will gain familiarity with basic methods of estimation and will be able to construct statistical tests for simple and composite hypotheses. They will become familiar with applications to realworld data and will be able to choose the most convenient method for given reallife problems.
Literature: S. Ross, A First Course in Probability. Fifth Edition, PrenticeHall, 1998. A. Rényi, Probability Theory, Acad. Press, 1978. W. Feller, An Introduction to Probability. Theory and Its Applications, Wiley, 1966. C.R. Rao, Linear statistical inference and its applications. Wiley, New York, 1973. R. A. Johnson, G. K. Bhattacharyya, Statistics. Principles and methods. Wiley, New York, 1992. M.G. Kendall, A. Stuart, The Theory of Advanced Statistics IIII. Griffin, London, 1966. Handouts: tables of notable distributions and percentile values of basic test distributions. MATRIX COMPUTATIONS WITH APPLICATIONS
1. Introduction to Matlab. Matrix manipulations and matlab notations. 2. Matrix multiplication problems 3. Matrix analysis 4. Linear systems 5. Orthogonalization and least squares 6. Eigenvalue problems, Lanczos methods 7. Iterative methods for linear systems 8. Krylov subspaces, matrix functions 9. Applications (using matlab): numerical solution of partial differential equations, nonnegativity preservation, matrix exponential, numerical solution of Maxwell equations, model reduction. COMPUTATIONS IN ALGEBRA
Different computational methods are discussed with an eye for applications. Diversity is a primary aim.
One of the main goals of the course is to introduce the main algorithms and their implementation. The computer algebra package GAP is used and its features are made familiar.
The students will learn the GAP system and attain fluency in it. They will get acquainted with some important algorithms and their implementations. They will be able to approach various problems with this arsenal.
1. A complexity analysis of the basic algorithms with polynomials 2. Discrete Fourier transform and fast Fourier transform of polynomials; fast multiplication of polynomials 3. Factorization of univariate and bivariate polynomials over finite fields; 4. Berlekamp and Cantor–Zassenhaus algorithms compared 5. applications to coding theory (decoding ReedSolomon codes) 6. Lattice basis reduction; the LLL algorithms; 7. applications to cryptography (breaking knapsack cryptosystems) 8. Factorization of polynomials with integer coefficients 9. Computational problems with multivariate polynomials; Groebner bases 10. Applications of Groebner bases (solving a system of algebraic equations) 11. Applications of Groebner bases (automatic geometric theorem proving; coding theory) 12. Various applications based on some computer algebra software Optional topics: Categorical approach: products, coproducts, pullback, pushout, functor categories, natural transformations, Yoneda lemma, adjoint functors. Books: 1. J von zur Gathen and J Gerhard, Modern Computer Algebra, Cambridge University Press, 1999. 2. Th Becker and V Weispfenning, Gröbner Bases: A Computational Approach to Commutative Algebra, Graduate Texts in Mathematics, Springer, 1998. CRYPTOLOGY
1. Computational difficulty, computational indistinguishability 2. Pseudorandom function, pseudorandom permutation 3. Probabilistic machines, BPP 4. Hard problems 5. Public key cryptography 6. Protocols, ZK protocols, simulation 7. Unconditional Security, multiparty protocols 8. Broadcast and pairwise channels 9. Secret Sharing Schemes, Verifiable SSS 10. Multiparty Computation DIFFERENTIAL GEOMETRY
1. Curves in R2. 2. Hypersurfaces in R2. Theorema Egregium. Special surfaces. 3. Differentiable manifolds, tangent budle, tensor bundles; Lie algebra of vector fields, distributions and Frobenius' theorem; Covariant derivation, the LeviCivita connection of a Riemannian manifold, parallel transport, holonomy groups; Curvature tensor, symmetries of the curvature tensor, decomposition of the curvature tensor; Geodesic curves, the exponential map, Gauss Lemma, Jacobi fields, the GaussBonnet theorem; Differential forms, de Rham cohomology, integration on manifolds, Stokes' theorem. INTRODUCTION TO DISCRETE MATHEMATICS
Fundamental concepts and results of combinatorics and graph theory. Main topics: counting, recurrences, generating functions, sieve formula, pigeonhole principle, Ramsey theory, graphs, flows, trees, colorings.
The main goal is to study the basic methods of discrete mathematics via a lot of problems, to learn combinatorial approach of problems. Problem solving is more important than in other courses!
Knowledge of combinatorial techniques that can be applied not just in discrete mathematics but in many other areas of mathematics. Skills in solving combinatorial type problems.
Week 1. Basic counting problems, permutations, combinations, sum rule, product rule Week 2. Occupancy problems, partitions of integers Week 3. Solving recurrences, Fibonacci numbers Week 4. Generating functions, applications to recurrences Week 5. Exponential generating functions, Stirling numbers, derangements Week 6. Advanced applications of generating functions (Catalan numbers, odd partitions) Week 7. Principle of inclusion and exclusion (sieve formula), Euler function Application of sieve formula to Stirling numbers, derangements, and other involved problems Week 8. Pigeonhole principle, Ramsey theory, Erdos Szekeres theorem Week 9. Basic definitions of graph theory, trees Week 10. Special properties of trees, Cayley’s theorem on the number of labeled trees Week 11. Flows in networks, connectivity Week 12. Graph colorings, Brooks theorem, colorings of planar graphs References: 1. Fred. S. Roberts, Applied Combinatorics, Prentice Hall, 1984 2. Fred. S. Roberts, Barry Tesman, Applied Combinatorics, Prentice Hall, 2004 3. Bela Bollobas, Modern Graph Theory, Springer, 1998 GRAPH THEORY AND APPLICATIONS
1. Basics: Graphs, degrees, components, paths and cycles, independent sets, cliques, isomorphism, subgraphs, complement of a graph, trees, Euler tours, other notions of graphs 2. Hamilton cycles: Sufficient conditions for Hamiltonicity, theorems of Dirac, Ore 3. Coloring: The concept of chromatic number, its relation to the clique number, theorems on chromatic number 4. Coloring edges and matchings: Vizing's theorem, matchings in bipartite graphs, KõnigHallFrobenius theorem, theorems of Gallai, Tutte's theorem 5. Network flows and connectivity: Networks, FordFulkerson theorem, connectivity numbers, Menger's theorems 6. Planarity: Euler's lemma, Kuratowski's theorem, coloring of planar graphs 7. Turán and Ramseytype questions: Turán's theorem and related results, the role of the chromatic number in extremal graph theory, graph Ramsey theorems 8. Probabilistic approach: Some important results showing the power of the probabilistic method in graph theory will be discussed 9. Graph Algorithms: Shortest paths (Dikstra, BellmanFord, Floyd), depth first and width first search, mincost spanning trees (Prim, Kruskal), matching in bipartite graphs (Hungarian method) 10. Various applications NONSTANDARD ANALYSIS
1. Tools from mathematical logic: compactness theorem, higherorder logic 2. Enlargement 3. Elementary Analysis: differentiation, integration, convergence 4. Topological Spaces: compactness, Tichonov's theorem, Uhrysson's theorem on metrizable spaces 5. Theorems of Montel and Kakeya on lacunary polynomials 6. Complex Functions: the Picard's theorem, Julia direction DIFFERENCE EQUATIONS AND APPLICATIONS
1. The difference calculus 2. Firstorder difference equations 3. Linear difference equations 4. Linear partial difference equations 5. Nonlinear difference equations 6. Various applications EVOLUTION EQUATIONS AND APPLICATIONS
1. Preliminaries of linear and nonlinear functional analysis 2. Existence and regularity of solutions to evolution equations in Hilbert spaces 3. Boundedness of solutions on the positive half axis 4. Stability of solutions. Strong and weak convergence results. 5. Periodic forcing. The asymptotic dosing problem 6. Applications to delay equations, parabolic and hyperbolic boundary value problems. Specific examples. 