01-logistics_and_mathematical terminology.pdf

FOUNDATIONS OF COMPUTING Fall 2024 Instructor: Azam Asilian Bidgoli Course Info Instructor Azam Asilian Bidgoli Email: [email protected] Offices: N2076J, Science Building Office hours: Wednesdays: 16:00-17:00 by appointment Meeting times: Mondays and...

FOUNDATIONS OF COMPUTING Fall 2024 Instructor: Azam Asilian Bidgoli Course Info Instructor Azam Asilian Bidgoli Email: [email protected] Offices: N2076J, Science Building Office hours: Wednesdays: 16:00-17:00 by appointment Meeting times: Mondays and Wednesdays: 17:30-18:50 TA: TBA Recommended Textbooks 1. Michael Sipser, "Introduction to the Theory of Computation “, 3rd edition 2. John C. Martin “Introduction to Languages and Theory of Computation”, 4th edition Requirements Students must score 50% or more in the weighted average of midterm and final exam to pass the course i.e. (weighted marks in the midterm exam + weighted marks in the final exam) ≥ 30. If the student passes the final exam, then the final score will be the sum of Grades in Assignments, Quizzes, Midterms, and Final exam as per the following distribution: Assessment Weighting Four Assignments 28% (7% each) Quizzes 12% Midterm Exam 25% Final Exam 35% Class Participation 3% (Bonus)  5 Policies 1. Assignments will be accepted up to 2 days late, but 15% will be deducted for each day late, rounded up to the nearest day. No credit will be given for assignments submitted after 2 days. 2. Quizzes must be taken individually during lecture time. The number of quizzes will depend on time constraints. Each quiz's schedule will be announced one week in advance. 3. The assignments can be done in groups of up to 2 students. You need to register in a group by 4. The submitted work will be checked for plagiarism. The submitted work checked for plagiarism and involved students will be awarded Zero. It is considered Academic Misconduct to provide your work to another student for any reason.  6 Policies Missed Midterm If a midterm exam is missed, it will be graded as 0 unless there's a legitimate documented reason. The option to shift the exam's weight is reserved exclusively for students with confirmed exceptional circumstances. An exceptional circumstance refers to an unusual and significant event that is beyond the student's control or predictability, such as a severe accident or an urgent medical condition. Big questions in foundations of computing What problems are computers capable of solving? What resources are needed to solve a problem? Are some problems harder than others? Making a decision or computing a value based on some input Questions about algorithms Are they correct (for given specification)? Is there a better approach to solving the same problem? Does each problem have a solution? If so, can that solution be found by an algorithm? Central areas of the foundations of computing Automata Computability Complexity What are the fundamental capabilities and limitations of computers? Complexity What makes some problems computationally hard and others easy? the sorting problem is an easy one a scheduling problem can be hard one Researchers have discovered an elegant scheme for classifying problems according to their computational difficulty. options when you confront a computationally hard problem: by understanding difficult aspect of the problem you may be able to settle for less than a perfect solution to the problem some problems are hard only in the worst case situation, but easy most of the time Computability Theory the classification of problems is by those that are solvable and those that are not. certain basic problems cannot be solved by computers. one example of this phenomenon: the problem of determining whether a mathematical statement is true or false. Automata Theory deals with the definitions and properties of mathematical models of computation. automata theory is an excellent place to begin the study of the foundations of computation. Activity Goal: find treasure hidden somewhere in grid. Describe an algorithm for each robot. Do you need to assume anything? Do you need to keep track of any information? Robot 1: can move North, East, West, South. Robot 2: can move in four diagonal directions. Bird's eye view of CP414 Pick a model of computation Study what problems it can solve Prove its limits Models of computation Finite automata: used in text processing, compilers, and hardware design Context-free grammars: used in programming languages and artificial intelligence Turing machines: a much more accurate model of a general purpose computer Bird's eye view Classification: is input of type Pick a model of computation A or not? e.g. is n prime? is list sorted? Study what problems it can solve Computation: for specific input, what value should I output? Prove its limits e.g. what's min cost of Hamiltonian tour? Bird's eye view Classification: is input of type Pick a model of computation A or not? Decision problem Study what problems it can solve Computation: for specific input, what value should I output? Prove its limits Function problem Bird's eye view Pick a model of computation Classification: is input of type A or not? Decision problem Study what problems it can solve { w | w is of type A} PRIME = { 2, 3, 5, 7, … } Prove its limits SORTED = { , …} Decision problems are coded by sets of strings So let's get going ☺ First topic: Mathematical Notions and Terminology Mathematical Notions And Terminology SETS a set is a group of objects represented as a unit. the objects in a set are called its elements or members. S = {7, 21, 57} the symbols ∈ and ∉ denote set membership and nonmembership. 7 ∈ {7, 21, 57} and 8 ∉ {7, 21, 57} a is a subset of B, written A ⊆ B, if every member of A also is a member of B. An infinite set contains infinitely many elements. set of natural numbers N {1, 2, 3,... } set of integers Z is written as {... , -2, -1, 0, 1, 2,...}. Sets set with zero members is called the empty set and is written ∅ Union: A∪B, is the set we get by combining all the elements in A and B into a single set Intersection: A ∩ B, is the set of elements that are in both A and B complement of A, written A', is the set of all elements under consideration that are not in A Sequences and Tuples A sequence of objects is a list of these objects in some order. (7, 21, 57) Order and repetition do matter in a sequence As with sets, sequences may be finite or infinite Finite sequences often are called tuples. Cartesian product or cross product A × B, is the set of all ordered pairs wherein the first element is a member of A and the second element is a member of B A = {1, 2} and B = {x, y, z} A × B = { (1, x), (1, y), (1, z), (2, x), (2, y), (2, z) }. The set N2 equals N × N. It consists of all ordered pairs of natural numbers. We also may write it as {(i, j)| i, j ≥ 1} Functions and Relations A function is an object that sets up an input–output relationship f(a) = b A function also is called a mapping The set of possible inputs to the function is called its domain. The outputs of a function come from a set called its range. f : D→R add : Z × Z→Z Graphs An undirected graph, or simply a graph, is a set of points with lines connecting some of the points. The number of edges at a particular node is the degree of that node. We may allow an edge from a node to itself, called a self-loop the pair (i, j) represents the edge that connects i and j. If V is the set of nodes of G and E is the set of edges, we say G = (V, E). ({1, 2, 3, 4, 5}, {(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)}) Graphs We say that graph G is a subgraph of graph H if the nodes of G are a subset of the nodes of H, and the edges of G are the edges of H on the corresponding nodes. A path in a graph is a sequence of nodes connected by edges. A graph is connected if every two nodes have a path between them. Graphs A path is a cycle if it starts and ends in the same node. A graph is a tree if it is connected and has no simple cycles A directed graph has arrows instead of lines A directed graph is strongly connected if a directed path connects every two nodes. A path in which all the arrows point in the same direction as its steps is called a directed path. Strings and Languages we define an alphabet to be any nonempty finite set The members of the alphabet are the symbols of the alphabet. We generally use capital Greek letters Σ and Γ to designate alphabets and a typewriter font for symbols from an alphabet. A string over an alphabet is a finite sequence of symbols from that alphabet If Σ1 = {0,1}, then 01001 is a string over Σ1 the length of w, written |w|, is the number of symbols that it contains. for a string x over Σ and an element σ ∈ Σ, nσ (x) = the number of occurrences of the symbol σ in the string x The string of length zero is called empty string and is written ε A language is a set of strings Languages any set of strings over an alphabet of symbols. The set of all strings over Σ will be written Σ*. For the alphabet {a, b}, we have {a, b}* = {ε, a, b, aa, ab, ba, bb, aaa, aab,... } A language over Σ is a subset of Σ*. Here are a few examples of languages over {a, b}: 1. The empty language ∅. 2. {ε, a, aab}, another finite language. 3. {x ∈ {a, b}∗ | na(x) > nb(x)}. 4. {x ∈ {a, b}∗ | |x| ≥ 2 and x begins and ends with b}. 5. The language Expr of legal algebraic expressions involving the identifier a, the binary operations + and ∗, and parentheses. Some of the strings in the language are a, a + a ∗ a, and (a + a ∗ (a + a)). 6. The language of numeric “literals” in Java, such as -41, 0.03, and 5.0E-3. Strings and Languages The reverse of w, written wR, is the string obtained by writing w in the opposite order the string ordering of all strings over the alphabet {0,1} is (ε, 0, 1, 00, 01, 10, 11, 000,...). string x is a prefix of string y if a string z exists where xz = y concatenation operation: if x = ab and y = bab, then xy = abbab and yx = babab. In general, for two strings x and y, |xy| = |x| + |y| For two languages L1 and L2 over the alphabet Σ, L1 ∪ L2, L1 ∩ L2, and L1 - L2 are also languages over Σ. If L1 and L2 are both languages over Σ, the concatenation of L1 and L2 is the language L1 L2 = {xy | x ∈ L1 and y ∈ L2} For example, {a, aa}{ε, b, ab} = {a, ab, aab, aa, aaab}. Strings and Languages “exponential” notation for the concatenation of k copies of a single symbol a: ak = aa... a Similarly: For a single string x, or a single language L. xk and Lk In the special case where L is simply the alphabet Σ (which can be interpreted as a set of strings of length 1), Σk = {x ∈ Σ∗ | |x| = k} for a language L over an alphabet Σ, we use the notation L∗ to denote the language of all strings that can be obtained by concatenating zero or more strings in L ∗ L = ራ{Lk| k ∈ N} We can create languages with various operations, we will use precedence rules similar to the algebraic rules you are accustomed to. An example: (L1 ∪ L2)L3*, L1 ∪ (L2L3)∗, and (L1 ∪ L2L3)∗ refer to different languages. Creating infinite languages by formulas: 1. L1 = {ab, bab}∗ ∪ {b}{ba}∗{ab}∗ 2. L2 = {x ∈ {a, b}∗ | na(x) > nb(x)} Boolean Logic Boolean logic is a mathematical system built around the two values TRUE and FALSE. Boolean operations: negation or NOT operation, designated with the symbol ¬. conjunction or AND operation with the symbol ∧. disjunction or OR operation is designated with the symbol ∨. exclusive or, or XOR, operation is designated by the ⊕ symbol equality operation, written with the symbol implication operation is designated by the symbol → Boolean Logic Equivalent expressions distributive law Boolean Logic truth tables Boolean Logic A tautology is a compound proposition that is true for every possible combination of truth values of its constituent propositions (e.g., p ∨ ¬p) A contradiction is the opposite, a proposition that is false in every case (e.g., p ∧ ¬p) Finding Proofs two-part statement: 1. Finding proof of the statement has the form “P if and only if Q”, often written “P iff Q” (i.e., P ⟺ Q ): forward direction : the first part is “P only if Q,” which means: If P is true, then Q is true, written P ⇒ Q. reverse direction: the second is “P if Q,” which means: If Q is true, then P is true, written P ⇐ Q. 2. statement states that two sets A and B are equal The first part states that A is a subset of B, and the second part states that B is a subset of A. one common way to prove that A = B is: to prove that every member of A also is a member of B, and that every member of B also is a member of A. Finding Proofs Example 1: For every graph G, the sum of the degrees of all the nodes in G is an even number. Proof: Every edge in G is connected to two nodes. Each edge contributes 1 to the degree of each node to which it is connected. Therefore, each edge contributes 2 to the sum of the degrees of all the nodes. Hence, if G contains e edges, then the sum of the degrees of all the nodes of G is 2e, which is an even number. Finding Proofs Example 2: Prove that for any two sets A and B,. Types of Proof Proof by Contradiction: we assume that the theorem is false and then show that this assumption leads to an obviously false consequence, called a contradiction. Example: For all integers n, if n3 + 5 is odd then n is even. Let n be any integer and suppose, for the sake of contradiction, that n3 + 5 and n are both odd. In this case integers j and k exist such that n3 + 5 = 2k + 1 and n = 2j + 1. Substituting for n we have 2k + 1 = n3 + 5 2k + 1 = (2j + 1)3 + 5 2k + 1 = 8j3 + 3(2j)2 (1) + 3(2j)(1)2 + 13 + 5 2k = 8j3 + 12j2 + 6j + 5. Dividing by 2 and rearranging we have k − 4j3 − 6j2 − 3j = 5/2. This, however, is impossible: 5/2 is a non-integer rational number, while k − 4j3 − 6j2 − 3j is an integer by the closure properties for integers. Therefore, it must be the case that our assumption that when n 3 +5 is odd then n is odd is false, so n must be even. Types of Proof Proof By Induction Our goal is to prove that P(k) is true for each natural number k: we want to prove that P(1) is true, as well as P(2), P(3), P(4), and so on. Steps: 1. basis: proves that P(1) is true. 2. induction: For each i ≥ 1, assume that P(i) is true and use this assumption to show that P(i + 1) is true. Types of Proof Example of Proof By Induction: