# Degree Plans

The obligatory and elective courses, as specified below, are the same for the three specializations. The specializations differ in one area of the state final exam and the students are recommended to adjust their choice of elective and optional courses accordingly.

#### Obligatory courses

 Code Subject Credits Winter Summer NMAI054 Mathematical Analysis I 5 2/2 C+Ex — NMAI055 Mathematical Analysis II 5 — 2/2 C+Ex NMAI057 Linear Algebra I 5 2/2 C+Ex — NMAI058 Linear Algebra II 5 — 2/2 C+Ex NMAI062 Algebra I 6 2/2 C+Ex — NDMI002 Discrete Mathematics 5 2/2 C+Ex — NDMI011 Combinatorics and Graph Theory I 5 — 2/2 C+Ex NOPT048 Linear programming and combinatorial optimization 1 6 — 2/2 C+Ex NMAI059 Probability and Statistics 6 2/2 C+Ex — NAIL062 Propositional and Predicate Logic 6 2/2 C+Ex — NTIN071 Automata and Grammars 6 — 2/2 C+Ex NTIN060 Algorithms and Data Structures I 5 — 2/2 C+Ex NTIN061 Algorithms and Data Structures II 6 2/2 C+Ex — NPRG030 Programming I 6 3/2 C — NPRG031 Programming II 2 5 — 2/2 C+Ex NPRG005 Non-procedural Programming 6 — 2/2 C+Ex NSWI120 Principles of Computers 3 3/0 Ex — NSWI141 Introduction to networking 2 1/0 Ex — NSWI095 Introduction to UNIX 5 — 2/2 C+Ex NDBI025 Database Systems 6 — 2/2 C+Ex NPRG045 Individual Software Project 4 — 0/1 C NSZZ031 Bachelor Thesis 6 — 0/4 C

1 The course NOPT048 went under name "Optimization methods" until the academic year 2017/18.

2 In the course NPRG031 the exam can be taken before obtaining the course credit.

#### Set 1

The student needs to obtain at least 6 credits for courses from this set.

 Code Subject Credits Winter Summer NPRG041 Programming in C++ 6 2/2 C+Ex — NPRG013 Java 6 2/2 C+Ex — NPRG035 C# Language and .NET Framework 6 2/2 C+Ex —

#### Set 2

The student needs to obtain at least 34 credits for courses from this set.

 Code Subject Credits Winter Summer NMAI056 Mathematical Analysis III 6 2/2 C+Ex — NDMI012 Combinatorics and Graph Theory II 6 2/2 C+Ex — NMAI063 Algebra II 3 — 2/0 Ex NDMI009 Combinatorial and Computational Geometry I 6 2/2 C+Ex — NDMI084 Introduction to approximation and randomized algorithms 5 2/1 C+Ex — NOPT046 Discrete and Continuous Optimization 6 — 2/2 C+Ex NMAI042 Numerical Mathematics 6 — 2/2 C+Ex NAIL063 Set Theory 3 — 2/0 Ex NPFL054 Introduction to Machine Learning 5 2/2 C+Ex — NPFL063 Introduction to General Linguistics 5 2/1 C+Ex — NPFL012 Introduction to Computer Linguistics 3 2/0 Ex — NPRG051 Advanced C++ Programming 6 — 2/2 C+Ex NPRG021 Advanced programming for Java platform 6 — 2/2 C+Ex NPRG038 Advanced .NET Programming I 6 — 2/2 C+Ex NSWI090 Computer Networks 3 — 2/0 Ex NSWI143 Computer Architecture 3 — 2/0 Ex NSWI004 Operating Systems 5 2/1 C+Ex — NDBI007 Data Organisation and Processing I 4 2/1 C+Ex — NDBI026 Database Applications 4 1/2 MC — NSWI098 Compiler Principles 6 2/2 C+Ex — NPGR003 Introduction to Computer Graphics 5 2/2 C+Ex — NPGR004 Computer Graphics II 5 — 2/1 C+Ex NPGR020 Geometry for Computer Graphics 3 — 2/0 Ex NPGR002 Digital Image Processing 5 3/0 Ex — NPRG036 XML Technologies 6 — 2/2 C+Ex NSWI089 Information Security I 3 2/0 Ex — NSWI015 Unix/Linux Programming in C 5 2/1 C+Ex — NSWI036 Programming for Windows - I 3 2/0 Ex — NSWI106 Unix Administration 6 2/2 C+Ex — NSWI045 TCP/IP Protocol Suite 3 — 2/0 Ex NSWI041 Introduction to Software Engineering 5 — 2/2 C+Ex NPRG003 Programming Methodology and Philosophy of Programming Languages 3 — 2/0 Ex

** The course can be taken in the summer as well as in the winter semester.

#### Recommended course of study

The recommended course of study contains all obligatory courses, some elective courses in required extend and some optional courses. The student needs to choose other courses him/herself. The obligatory courses are printed in boldface, the elective courses are printed upright and the optional courses in italics.

#### First year

 Code Subject Credits Winter Summer NMAI054 Mathematical Analysis I 5 2/2 C+Ex — NMAI057 Linear Algebra I 5 2/2 C+Ex — NDMI002 Discrete Mathematics 5 2/2 C+Ex — NPRG030 Programming I 6 3/2 C — NSWI120 Principles of Computers 3 3/0 Ex — NSWI141 Introduction to networking 2 1/0 Ex — NMAI069 Mathematical skills 1 2 0/2 C — Optional courses 2 NMAI055 Mathematical Analysis II 5 — 2/2 C+Ex NMAI058 Linear Algebra II 5 — 2/2 C+Ex NDMI011 Combinatorics and Graph Theory I 5 — 2/2 C+Ex NPRG031 Programming II * 5 — 2/2 C+Ex NTIN060 Algorithms and Data Structures I 5 — 2/2 C+Ex NSWI095 Introduction to UNIX 5 — 2/2 C+Ex

1The course NMAI069 Mathematical skills is highly recommended to students who want to master basic mathematical skills used in mathematical courses. The use of logical thinking is heavily emphasized.

* In the course NPRG031 the exam can be taken before obtaining the course credit.

#### Second year

 Code Subject Credits Winter Summer NTIN061 Algorithms and Data Structures II 6 2/2 C+Ex — NAIL062 Propositional and Predicate Logic 6 2/2 C+Ex — NMAI059 Probability and Statistics 6 2/2 C+Ex — Elective course from Set 1 6 2/2 C+Ex — NMAI056 Mathematical Analysis III 6 2/2 C+Ex — NOPT048 Linear programming and combinatorial optimization 6 — 2/2 C+Ex NPRG005 Non-procedural Programming 6 — 2/2 C+Ex NTIN071 Automata and Grammars 6 — 2/2 C+Ex NDBI025 Database Systems 6 — 2/2 C+Ex NPRG045 Individual Software Project 4 — 0/1 C Elective courses from Set 2 2

#### Third year

 Code Subject Credits Winter Summer NMAI062 Algebra I 6 2/2 C+Ex — NMAI063 Algebra II 3 — 2/0 Ex NSZZ031 Bachelor Thesis 6 — 0/4 C Elective courses from Set 2 30 Optional courses 15

#### Algorithms and optimization

 Code Subject Credits Winter Summer NOPT046 Discrete and Continuous Optimization 6 — 2/2 C+Ex NDMI009 Combinatorial and Computational Geometry I 6 2/2 C+Ex — NDMI084 Introduction to approximation and randomized algorithms 5 2/1 C+Ex —

#### Discrete models and structures

 Code Subject Credits Winter Summer NDMI012 Combinatorics and Graph Theory II 6 2/2 C+Ex — NAIL063 Set Theory 3 — 2/0 Ex

#### Mathematical linguistics

 Code Subject Credits Winter Summer NPFL054 Introduction to Machine Learning 5 2/2 C+Ex — NPFL012 Introduction to Computer Linguistics 3 2/0 Ex —

#### State Final Exam

The state final exam has three parts in the bachelor programme:

oral examination in Mathematics
oral examination in Computer Science
defense of the bachelor thesis

#### Necessary conditions for taking the state final exam

obtaining of 180 credits at least
passing all obligatory courses of a given branch and specialization
obtaining a given number of credits for the elective courses
submitting the completed bachelor thesis by the specified deadline.

#### Knowledge requirements for the part Mathematics of the State Final Exam

1. Numbers
Properties of natural, whole, rational, real and complex numbers. Sequences and series of numbers. Cauchy sequences.

2. Fundamentals of differential calculus
Real functions of one variable. Continuity, limit of a function (ordinary, infinite). Some specific functions (polynomials, rational functions, trigonometric and inverse trigonometric functions, logarithms and exponential functions). Derivation: the definition, basic rules, theorems about the mean value, higher order derivatives. Applications (examination of properties of functions, Taylor polynomial).

3. Basics of the theory of multivariable functions
Partial derivatives and total differential, theorems about extreme values of multivariable functions, implicit function theorem.

4. Integral
Primitive functions, methods of calculation. Definite (Riemann) integral, applications of the definite integral. Multivariate integrals and Fubini's theorem.

5. Metric spaces
Definition of a metric space, examples. Continuity, open and closed sets. Compactness.

6. Elementary algebraic structures
Groups, rings, fields - definitions, examples. Fermat's Little Theorem. Divisibility and irreducible factorization of polynomials. Factorization for polynomials with real, rational and complex coefficients. Multiplicity of roots and their relationship with derivations of the polynomial.

7. Vector spaces
Basic properties of vector spaces, subspaces, generation, linear dependence and independence. Steinitz (exchange) theorem. Finitely generated vector spaces, basis. Linear mapping.

8. Scalar product
Properties in vector spaces over the real and complex fields. Norm. Cauchy-Schwarz inequality. Ortogonality. Orthogonal complement and its properties.

9. Systems of linear equations
Affine subspace in vector spaces and geometric interpretation. Solution of a system of linear equations as an affine subspace. Frobenius theorem. Solving system of linear equations by elimination. Solution of a system of linear equations and its orthogonal complement.

10. Matrices
Matrices, their rank. Operations with matrices and their properties. Inverse matrix. Nonsingular matrices, various characterizations. Matrices and linear mappings, changes of coordinate systems.

11. Determinants
Definitions and basic properties of determinant. Calculation of determinant. Geometric interpretation of a determinant. Minors and inverse matrices. Cramer's rule.

12. Eigenvalues and eigenvectors
Eigenvalues and eigenvectors of linear mapping and square matrix. Calculation, basic properties. Transformation of a matrix to a diagonal form, in the case of different eigenvalues. Jordan normal form of a matrix, in the general case (basic information).

13. Discrete Mathematics
Sets, ordered sets, mappings, relations, equivalences. Combinatorial counting. The principle of inclusion and exclusion. Generating functions.

14. Graph Theory
Basic concepts of graph theory, graph representation. Trees and their basic properties, spanning tree. Eulerian graphs. Planar graphs, graph colorings. Menger's theorem, duality of flows and cuts. Matching, matching in bipartite graphs (system of different representatives).

15. Probability and Statistics
Random events, conditional probability, independence of random events. Random variables, the mean, the distribution of random variables, normal and binomial distribution. Linear combinations of random variables. Point estimates, confidence intervals, hypothesis testing, t-test, chi-square test, linear regression.

16. Logic
Language, formula, semantics, tautology. Decidability, satisfiability, truth, provability. Compactness theorems, completeness of propositional and predicate logic. Normal forms of propositional formulas, prenex normal forms in predicate logic.

17. Algebra
Subgroups, normal subgroups, quotient groups, ideal. Homomorphisms of groups and other structures. Quotient fields.

#### Knowledge requirements for the part Computer Science of the State Final Exam

1. Automata and languages
Chomsky hierarchy, classes of automata and grammars, determinism and non-determinism. Closure properties of classes of languages.

2. Algorithms and Data Structures
Time complexity of algorithms, complexity in the worst and average case. Complexity classes P and NP, reducibility, NP-completeness. ``Divide-and-conquer" technique - applications and complexity analysis, dynamic programming. Binary search trees, balancing, heaps. Hashing. Sequential sorting, comparison based algorithms, bucket sorting, sorting networks. Graph algorithms - depth-first search and breadth-first search, connected components, strongly connected components in oriented graphs, topological sorting, shortest path, spanning tree, network flows. Transitive closure. Text search algorithms. Algebraic algorithms - DFT, Euclid's algorithm. RSA. Approximation algorithms.

3. Databases
Architectures of database systems. Conceptual, logical and physical database design. Algorithms for design of relational schemas, normal forms, referential integrity. Transactional processing, properties of transactions, locking protocols, deadlocks. ER-diagrams, methods for IS design. Overview of SQL.

4. Programming languages
Implementation principles of object-oriented languages, runtime support. Separate compilation, linking, build management. Concepts and principles of object-oriented design. Generic programming, templates and generics, compile time polymorphism. Non-procedural programming.

5. Computer Architecture and Operating Systems
Computer architecture. Processors, multiprocessors. Buses, protocols. Input and output devices. OS architecture. Relationship between OS and HW architecture, interruption handling. Processes, threads, scheduling. Synchronization primitives, mutual exclusion. Deadlock, deadlock recovery. Memory management, allocation algorithms. Principles of memory virtualization, paging, page replacement algorithms, page faults, page tables. File systems, directory structure.

6. Networking Fundamentals
Taxonomy of computer networks. ISO/OSI reference architecture. Overview of the TCP/IP protocol model. Routing. Addresses, ports, sockets. Client-server architectures. Fundamentals of HTTP, FTP and SMTP protocols.

7. Optimization Methods
Polyhedron, Minkowski-Weyl theorem. Basics of linear programming, duality theorems, algorithms for LP. Edmonds' algorithm. Integer programming.

8. For specialization Algorithms and optimization
Approximation algorithms for combinatorial problems (satisfiability, independent set, set cover, scheduling). Applications of linear programming in approximation algorithms. The use of probability in the design of algorithms. Voronoi diagrams, arrangements of (complex) hyperplanes, incidence of points and lines, elementary computational geometry algorithms. Error-correcting codes. The probabilistic method - examples of application.

8. For specialization Discrete models and structures
Sets and mappings. Subvalence and equivalence of sets. Good arrangement. Axiom of choice (Zermel's theorem, Zorn's lemma). Graph coloring (Brooks' and Vizing's theorem). Tutte's theorem. Extremal combinatorics (Ramsey's theorem, Erdös-Ko-Rado theorem). Error-correcting codes. The probabilistic method - application examples.

8. For specialization Computational linguistics
Formal languages and automata, basic formalisms for description of a natural language; morphological and syntactic analysis of a natural language; theory of information, language modeling.
{"ft_lang_label":"__label__en","ft_lang_prob":0.7166841,"math_prob":0.85094774,"size":14697,"snap":"2019-51-2020-05","text_gpt3_token_len":3831,"char_repetition_ratio":0.15680936,"word_repetition_ratio":0.19883326,"special_character_ratio":0.26032522,"punctuation_ratio":0.125,"nsfw_num_words":1,"has_unicode_error":false,"math_prob_llama3":0.96817225,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-01-20T04:57:50Z\",\"WARC-Record-ID\":\"<urn:uuid:672e111a-2730-4d22-967a-e0247ef19654>\",\"Content-Length\":\"71925\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:83fdac63-16ac-4437-bbca-b453d07d4d4d>\",\"WARC-Concurrent-To\":\"<urn:uuid:a5fd7bdd-e07d-45ec-9f2a-fd5e39dc0894>\",\"WARC-IP-Address\":\"195.113.27.221\",\"WARC-Target-URI\":\"https://www.mff.cuni.cz/en/students/bachelor-of-computer-science/degree-plans\",\"WARC-Payload-Digest\":\"sha1:CK5YNRZW22HSFDSSXMZ3QCWWFNFY3NGU\",\"WARC-Block-Digest\":\"sha1:K5AI5BUPER42EM7XTX7Q2EV4FDNAXQ6M\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-05/CC-MAIN-2020-05_segments_1579250597230.18_warc_CC-MAIN-20200120023523-20200120051523-00079.warc.gz\"}"}