For each syllabus lesson some theoretical results have been set as required to pass this course. Those results can be either definitions, or theorems, or algorithms. Problems students have to be able to solve have been classified into two categories:
- Problems of basic content: Those basic problems that can be solved by directly applying a definition, a formula, or an algorithm are called basic contents.
- Problems of advanced content: This kind of problems requires some previous modelization and/or interpretation, after which the problem is solved by applying a pertinent combination of basic techniques.
A table with the whole list of basic and advanced contents can be checked by clicking HERE or they can be checked below.
DETAILED BASIC AND ADVANCED CONTENTS
For each lesson the student must achieve the specified goals below. Apart from the goals set for each lesson, solving problems requiring a pertinent combination of several concepts, techniques, and algorithms is also considered as an advanced goal.
LESSON 1: SETS, MAPS AND RELATIONS
| BASIC GOALS |
ADVANCED GOALS |
- Identify subsets of a set, and use the symbols for set membership and set inclusion.
- Define basic set operations: union, intersection, complement, and perform them in simple cases.
- Define the Cartesian product of two sets and obtain that product for two finite sets.
- Define map and function as well as injective, surjective and bijective map.
- Identify maps on sets of small cardinality and determine where the map is injective, surjective or bijective.
- Determine the image of a set with similar characteristics to the previous item.
- Define map and function composition.
- Compute maps and map composition.
- Define inverse map and check that a given map is the inverse of another map.
- Define a relation on a set, and define reflexive, symmetric, antisymmetric, and transitive relation. Define equivalence relation.
- Determine from a graphical representation whether a relation is a reflexive, symmetric, antisymmetric, and transitive, and in certain simple cases, whether the relation is of order or equivalence
- Define equivalence class and quotent set.
- Obtain a canonical representative and find its equivalence class.
- Describe quotient set Zn as well as the elements of its classes.
- Define comparable and non-comparable elements in an order relation.
- Define total order, partially ordered set (poset), and distinguish those two concepts through their sagittal diagram.
- Obtain the Hasse diagram of an order relation on a finite set.
- Obtain the maximal and minimal elements as well as the maximum and minimum of an order relation out of the Hasse diagram.
|
- Obtain the power set of a finite set.
- Determine whether a map is injective, surjective, or bijective map.
- Obtain the explicit expression of the inverse of a given map.
- Determine whether a relation is of order or equivalence.
- Obtain the quotient set of an equivalence relation.
- Build the Hasse diagram of an order relation described by a set builder.
|
LESSON 2: COMBINATORICS AND DISCRETE PROBABILITY
| BASIC GOALS |
ADVANCED GOALS |
- State the basic principles of counting: sum rule, product rule and inclusion-exclusion principle.
- Define the diferent ways to count objects: r-permutations, k-combinations, with and without repetition.
- Solve problems on combinatorics by using all the previous counting techniques: r-permutations, k-combinations, with and without repetition.
- Apply the basic principles of counting to simple cases.
- Get acquainted with and correcty apply Newton’s Binomial Theorem.
- Build Pascal’s triangle and work out its relation to binomial coefficients.
- Solve discrete probability problems by applying Laplace’s inductive probability.
|
- Solve problems of similar difficulty to the ones posed in class, where the main tools are the basic principles of counting.
- Use recursive techniques to counts the elements of a set.
- Solve probability problems of similar difficulty to the ones posed in class; they include combinatorics techniques and Laplace’s inductive probability.
|
LESSON 3: PROPOSITIONAL LOGIC
| BASIC GOALS |
ADVANCED GOALS |
- Formalize statements by using propositional logic.
- Determine the main connective of a formula and obtain its structural tree.
- Compute functions defined by using the structural recursive principle.
- Compute the truth value of a given formula for a given valuation.
- Define model and non-model.
- Obtain models for a given formula.
- Define tautology, contradiction, satisfiable formula and contingent formula.
- Determine whether a formula is tautology, contradiction, satisfiable, or contingent.
- Define logically equivalent formula, and apply basic equivalences.
- Define satisfiable and unsatisfiable set.
- Determine whether a set of formulae is satisfiable by using the method of the analytic tableaux.
- Define a deductive argument.
- Define counterexample.
- State correctly the basic inference rules.
- Determine whether a deductive argument is correct by using the method of the analytic tableaux.
- Show that a deductive argument is correct by using inference rules.
- Show that a deductive argument is incorrect.
|
- Formalize sentences written in natural languages, and determine whether the deductive argument associated with it is correct.
- Define functions by using the structural recursion principle.
- Determe whether a set of formulae satisfies certain conditions.
- Use the characterization of a correct deductive argument in terms of satisfactibility to study properties of a set of formulae.
- Prove that a deductive argument is correct by using inference rules.
|
LESSON 4: INDUCTION AND RECURSION
| BASIC GOALS |
ADVANCED GOALS |
- State the differente versions of the induction principle.
- Show by induction that two expressions (two sets, or two functions) depending on a natural number are the same. Show by induction that two functions, one defined recursively and the other defined explicit, are actually the same function.
- Operate with elementary list functions (head, tail, rest and concatenation).
- Prove by induction that two list functions, one defined recursively and the other defined explicitly, are actually the same function.
- Define initial set, basis case, and recursive case of a recursive function.
- Compute the initial set of a recursive function.
- Compute the value of function at a point and find its dependency tree.
- Define simple recursive functions on natural numbers and plain lists.
|
- Make conjectures about a general expression depending on a natural number. Show by induction that it is correct, as done in the problem set.
- State the strong induction principle.
- Define recursive functions on natural numbers and lists, as done in the problem set.
- Recognize the set obtained by giving a recursive definition.
- Describe the behaviour of a function defined recursively.
- Given a recursive case, propose a basis case, when possible, so that a recursive function is obtained.
|
LESSON 5: GRAPHS
| BASIC GOALS |
ADVANCED GOALS |
- Model a given problem by choosing the most suitable type of graph.
- Define regular graph and bipartite graph; determine whether a graph has those properties.
- Find the number of vertices and edges of the following families of graphs: Kn, Kn,m, Qn, Cn y Pn.
- Recognize the basic properties of the following families of graphs: regular, Eulerian, bipartite, and Hamiltonian.
- State and apply Euler’s formula (the one connecting degree of vertices and number of edges).
- Find the subgraph induced by a set of vertices, and the subgraph obtained by removing vertices or edges.
- Distinguish walk(path)/trail(simple path) and circuit/simple circuit.
- Define Eulerian graph and semi-Eulerian graph.
- Apply Euler’s theorem to determine whether a graph is Eulerian/semi-Eulerian.
- Build a Eulerian circuit on a graph, if exists.
- Define Hamiltonian graph.
- Define isomorphic graphs, and state invariant properties under isomorphisms.
- Establish isomorphisms between two graphs in simple cases.
- Justify why two graphs cannot be isomorphic in simple cases.
- Recognize graphically bridges, cut vertices and connected components of a graph.
- Recognize a tree through any of its characterizations.
- Apply the formula connecting the number of vertices and connected components of an acyclic graph.
- Determine a mininum spanning tree of a graph.
- Describe briefly the steps of Kruskal’s algorithm.
- Apply Kruskal’s algorithm to obtain a minimum spanning tree of a weighted graph.
- Apply Dijkstra’s algorithm to find the distance from a vertex to the rest, along with a minimum path tree.
- Distinguish between minimum spanning tree and minimum path tree.
- Define and distinguish center and median.
- Compute the center and the median of a given graph.
- Distinguish between maximal element and maximum, and minimum and minimal element, and recognize those elements on a acyclic digraph.
- Describe an algorithm to detect whether a finite digraph is acyclic, and apply it to find a topological ordering.
- Find topological ordering compatible with certain constrains or prove otherwise.
- Model through a digraph a dependency relation for a task planning problem. Find whether a set of task can be accomplished.
- Find for a graph with weighted task, the minimum time to accomplish them.
|
- Determine whether a graph is Hamiltonian.
- Determine whether two graphs are isomorphic.
- Solve problems involving distances between vertices of a weighted graph by using Dijkstra’s algorithm.
- On an optimization problem recognize the following: minimum spanning tree, minimum path tree, center/median of a graph, center/median constrained to a set of vertices.
- Build set of graphs holding certain properties, or prove otherwise.
- Determine whether a given task planning is correct to accomplish a set of tasks; find its the minimum time to be accomplished.
- Find the lower bound on the number of computers to accomplish a given set of tasks in optimal time.
- Use the heuristic algorithm covered in class to obtain an approximation to a planning with a minimum number of computers.
|
