Uniwersytet Warszawski University of Warsaw
Menu
Wyszukiwarka
 W bieżącym katalogu

The scope of the entrance examination into the PhD study in computer science

Each candidate should have a broad knowledge on the level of Master's programs in computer science in the following topics:

  1. Cardinality of sets. Partially ordered sets, fixed points. Well-founded sets, proofs by induction.
  2. Homomorphisms and congruence relations. Defining classes of algebras by equations.
  3. Syntax and sematics of the propositional logic and the first-order predicate calculus. The notion of formal proof. The completeness theorem.
  4. Convergence of sequences and series of functions. Lebesgue integration and its relations to Riemann integral.
  5. Linear dependence relation. The rank of a linear transformation. Linear matrices and its relation to linear transformations.
  6. Floating point arithmetics: scope and error estimation. Example of an analysis of errors induced by rounding. Quadratures: rank, convergence. Linear equation systems: solvability, numerical methods, determinants, matrix reversibility. Conditioning.
  7. Formal grammars, automata and their classification. Decidable and undecidable decision problems. Classes of complexity, NP-completeness.
  8. Semantic correctness of algorithms. Pessimistic, average and amortized costs.
  9. Sorting and selection algorithms.
  10. Abstract data structures (dictionary, priority queue, stack), their implementations and applications.
  11. Formal sematics of programming languages. Floyd-Hoare method - proving correctness of programs.
  12. Imperative and declarative programming. Object-oriented programming.
  13. Lexical, syntactic and semantic analysis of programs. Code generation and optimization algorithms. Runtime environment.
  14. Synchronization and communication of processes in centralized and distributed systems. Examples of formalisms.
  15. Concurrent programming: correctness, examples of correctness violation, classical problems.
  16. Operating systems: tasks, typical implementation problems and solutions.
  17. Distributed systems: hardware and software aspects, methods of distributed communication, file systems, distributed shared memory, examples of distributed algorithms.