在本章节中,语言和文法,有输出的有限状态机器,没有输出的有限状态机器,语言识别,图灵机
总复习(2 学时)
Chapter 1: Logic and proofs basics(6Hours)
In this chapter, focus on concepts, definition and rules, include: propositional and predicate logic, rules of
inference, proof methods and strategy
Chapter 2: Basic Discrete Structures(2 Hours)
In this chapter, focus on concepts, main content include: Sets, Functions, Sequences, Sums and Matrices
Chapter 3: Searching and sorting algorithms,(2 Hours)
In this chapter, Introduction to rules and paradigm of algorithms, with discussion on brute-force algorithms
and greedy algorithms.
Chapter 4: Study of the set of integers and their properties(2 Hours)
In this chapter, introduction to several important application of number theory, include generating
pseudorandom numbers, assigning memory locations, error detection, introduction to application of number
theory in classical cryptography and application of modern cryptography in electronic communication
Chapter 5: Induction and Recursion(4 Hours)
In this chapter,Introduction to mathematic induction and its application in proofs, recursive definition in
sequences and recursive algorithms, focus on the application of methodologies.
Chapter 6: Counting(2 Hours)
In this chapter, Introduction to the basics of counting, include permutations and combinations, binomial
coefficients and identities, generalized permutations and combinations
.Chapter 7: Probability (2 Hours)
In this chapter, Introduction to the basics of discrete probability, include probability theory, Bayes’s
theorem, expected value and variance
Chapter 8: Advanced Counting Techniques(2 Hours)
In this chapter,Applications of recurrence relations, solving linear recurrence relations, divide-and-conquer
algorithms and recurrence relations, generating functions, inclusion- exclusion and its applications
Mid-term evaluation course(2 Hours)
Chapter 9: Relations(4 Hours)
In this chapter, Definition of relations and their properties, n-ary relations and their applications, representing
relations, closure of relations, equivalence relations and partial orderings
Chapter 10: Graphs(4Hours)
In this chapter, Definition of graph and graph models, Euler Paths , Hamilton Paths
Chapter 11: Trees(4 Hours)
In this chapter, Introduction to trees and applications, tree traversal, spanning trees and minimum spanning
trees.
Chapter 12: Boolean Algebra(4 Hours)
In this chapter, Boolean functions, representing Boolean functions, logic gates, minimization of circuits
Chapter 13: Modelling Computation(6Hours)
In this chapter, Language and grammars, finite state machines with output, finite state machines without
output, language recognition, Turing machine
Final evaluation course(2 Hours)