CSI 2101 Summary.pdf

16 Pages
Unlock Document

University of Ottawa
Computer Science
Najib Zaguia

CSI 2101 Summary Winter 2013 CSI 2101 Summary, Winter 2013 Propositional Logic  PROPOSITION : a statement with some definite meaning, and has a truth value. You may not know the actual truth value, and the truth value may depend on the situation or the context. o Proving propositions are equivalent or consistent: show they yield the same truth values, for example using a truth table.  TAUTOLOGY : a compound proposition that is true regardless of the truth values of the atomic propositions  CONTRADICTION : a compound proposition that is false regardless of the truth values of the atomic propositions  CONTINGENCY : can be true or false, depending on the truth values of the atomic propositions. Predicate Logic  PREDICATE : modeled as a function from objects to propositions. If you have , is the variable, and is the property. Alternate definition: a function mapping an objectto proposition . o "The dog is sleeping." Same thing as saying is sleeping,where is the dog. is the property of sleeping. So, we have . o Convention: lowercase objects, uppercase predicates.  PREDICATES IN CMPUTING o PRECONDITION : what holds before the code segment. Can be denoted . o POSTCONDITION : what holds after the code segment. Can be denoted .  To verify a postcondition holds, we must start from the assumption that the precondition holds and go over every stop of the code and examine what it does to see whether the postcondition is really true.  Q UANTIFIERS: provide a notation that allows us to count how many objects in the universe of discourse satisfy a given predicate. o UNIVERSAL QUANTIFIER : means "for all."  True if allare true.  False if one is false o EXISTENTIAL QUANTIFIER: means "there exists."  True if there is one that is true  False if allare false  Can define new quantifiers, like means there exists exactly one in the universe of discourse. o FREE VARIABLE: a variable that is not defined. Example: in , is a free variable. o BOUND VARIABLE : when a variable is bounded by or . Example: in , is a bound variable.  Predicate becomes a proposition when all variables are bound. Proofs  PROOF : correct/well reasoned/logically valid, and complete/clear/detailed argument that rigorously and undeniably establishes the truth of a mathematical statement. o THEOREM : a statement that has been proven true. o AXIOM , POSTULATE, HYPOTHESIS , PEMISE : assumptions, often unproven defining the structures about which we are reasoning. 1 | P a g e CSI 2101 Summary, Winter 2013 o RULES OF INFERENCE: patterns of logically valid deductions from hypothesis to conclusions. o LEMMA : a minor theorem used as a stepping-stone to proving a major theorem. o OROLLARY C : a minor theorem proved as an easy consequence of a major theorem. o CONJECTURE : a statement whose truth value has not been proven. May be widely believed to be true, regardless. o THEORY : a set of all theorems that can be proven from a given set of axioms. o ORMAL PROOF F : sequence of statements ending in a conclusion. Statements preceding the conclusion are called premises. Each statement is either an axiom, or is derived from previous premises using a rule of inference. o IFORMAL PROOFS : Formal proofs are a pain and really tedious. We don't need that much detail. Obvious and easy steps are skipped or grouped together. Some axioms may be skipped (implicitly assumed). Must still be formal and precise to a certain degree.  PROVING EXISTENTIAL STATEMENTS : if in the form , just find one that satisfies .  DISPROVING THE NEGATION OF AN EXISTENTIAL STATEMENT : if in the form , just find one counterexample that satisfies .  DISPROVING AN EXISTENTIAL STATEMENT : to disprove, you need to prove the negation. In other words, if you're trying to disprove , then prove ( ) .  PROVING A UNIVERSAL THEOREM : if the theorem is in the form ( ), you can prove it by: o EXHAUSTION : works of the domain is finite or the number of for which holds is finite. Just prove for every in your domain. o DIRECT PROOF : assume and derive . o CONTRADICTION : show that . So assume the negation of the statement to be proven, and show it leads to some sort of nonsense. The fact that you reached nonsense means an assumption was wrong, this assumption being that you assumed . o CONTRAPOSITION : prove the contrapositive directly. The contrapositive is defined as ( ) .  Advantage: don't have to make potentially error-prone negation of the statement, and you know what you want to prove.  Disadvantage: only usable for statements that are universal and conditional.  CHECKLIST for writing good proofs:  Be clean and complete  State the theorem to be proven  Clearly mark the beginning of the proof  Make the proof self-contained (introduce and identify all the variables)  Write in full sentences Give reason for each assertion (by hypothesis, by definition, by substitution…)   Use connecting words (the, thus, hence, therefore, observe, note, let…)  STRATEGY : Say you're given if , then . Imagine elementsthat satisfy . Ask yourself, "Must they satisfy ?" If the answer is: o "Yes." Use the reasons why you feel this way as a basis for a direct proof. o "Not really." Think why, you may come up with a counterexample. If you can't find a counterexample, think of why.  Maybe from assuming , you can derive a contradiction.  Maybe from assuming , you can derive . 2 | P a g e CSI 2101 Summary, Winter 2013  N ORMAL INDUCTION : In order to prove statement by induction, we must first prove the base case, i.e. prove that is true. Then, we assume is true (induction hypothesis), and prove that , called the inductive step. If the base case and inductive step can be proved, then we say is proved by mathematical induction. o Is a rule of inference that says: ( )  W ELL-ORDERED : A set is “well-ordered” if every non-empty subset of has a least element.  STRONG INDUCTION : In order to prove statement by strong induction, we must first prove the base case, i.e. prove that is true. Then, we assume is true (induction hypothesis), and prove that , called the inductive step. If the base case and inductive step can be proved, then we say is proved by strong induction. o Is a rule of inference that says: TRUCTURAL INDUCTION  S : In order to prove statement by structural induction, we must first prove the base case, i.e. prove that is true for each element in the base definition of the set . For the inductive step, for every way to construct , show that . Complexity  COMPLEXITY : the number of steps that it takes to transform the input data into the desired output. It is a function of the size of the input (or size of the instance). In general, we will deal with the worst case complexity.  The main question is how the complexity behaves asymptotically, i.e. when the problem sizes tend to infinity.  We’re not interested in the exact time it takes to run, we usually just want to compare two algorithms. We will choose the right algorithm based on which has the better growth rate.  B -O : We say is "big oh" of if there exists two constants and such that for . To prove a function is ( ), find these two constants and  .Only the largest term matters. It means that an algorithm has the complexity of AT MOST .  B -O MEGA : We say is "omega" of , or if for all . It means an algorithm has the complexity of AT LEAST .  B -T HETA : We say is "theta" of , or if it is( ) ( ) It means the complexity IS EXACTLY . ( )  { ( ) ( ) 3 | P a g e CSI 2101 Summary, Winter 2013 Recursion  RECURSION : the practice of defining an object in terms of itself, or a part of itself. An inductive proof establishes the truth of recursively in terms of . o Can define a recursive function , and prove the explicit value of using induction. o Must be careful that it's well-defined  It is defined for each element in the domain  It is defined unambiguously o An infinite set may be defined recursively by giving:  A small finite set of base elements of  A rule for constructing new elements of from previously established elements  Implicitly, has no other elements but these  FIBONACCI N UMBERS : They are defined by the function . o HEOREM T : where √ . Proof is done by induction.  Recursive definitions can be used to describe algorithms. Typical problem solving approach: solve the problem for smaller/simpler sub-problems and obtain the result from that. Program Correctness  CORRECT : a program is correct if it produces the correct output for every input.  PARTIALLY CORRECT : a program is correct if it produces the correct output for every input for which the program eventually halts.  PRECONDITION : the initial assertiois the condition that the program’s input (its initial state) is guaranteed (by its user) to satisfy.  POST -ONDITION : the final assertionis the condition that the output produced by the program (its final state) is required to satisfy.  H OARE TRIPLE NOTATION : the notation { } means that for all inputs such that is true, if program (giveninput ) halts and produces output , then is true. That is,is partially correct with respect to specification . Deduction rules for Hoare Triple statements: o COMPOSITION RULE : if program given condition produces condition , and given condition produces , then the program followed by if given yields . { } { } { } o IF STATEMENTS: Let be the condition. Then { } { } o I -THEN-ELSE RULE: Let be the condition. Then { } { } { } o LOOP INVARIANTS : Let be the condition. For a while loop , we say that is a loop invariant of this loop if { } . So if is true before executing the body, then remains true after. { } { } 4 | P a g e CSI 2101 Summary, Winter 2013  PROVING THAT A LOOP HALTS : For each iteration , we associate an integer such that{ } is a decreasing sequence. Because of the well-ordering principle of any subset of integers, this sequence of integers { } is finite. Number Theory  DIVIDES: divides , denoted for if there is an integersuch that . o FACTOR /DIVISOR: if , then is a factor/divisor of . o M ULTIPLE: if , then is a multiple of . o FACTS:   If and , then  If , then  If and , then  If such that and , then when  DIVISION ALGORITHM : Let and . Then there are unique integers and , with , such that . remainder, dividend, quotient.  CONGRUENCE : If and then is congruent to modulo (denoted or ) if . o FACTS:  if and only if such that  If and , then and  We can add or multiply (not divide) the two sides of the congruence by the same integer. o ADDITION : the operation is defined by DDITIVE INVERSE  A : if is the additive inverse ofmodulo . Note that 0 is its own additive inverse.  ADDITIVE IDENTITY : if , then . o M ULTIPLICATION : the operation is defined by  M ULTIPLICATIVE INVERS: if , then is called the multiplicative inverse. Note that this inverse does not always exist.  M ULTIPLICATIVE IDENTITY : if , then .  PRIME : the number is prime if there are exactly two positive factors: 1 and itself. o FUNDAMENTAL HETREM OF A RITHMETIC: Every positive integer can be uniquely written as a prime or as the product of two or more primes, where the primes are written in order of non-decreasing size. The non-primes are called composite integers. o THEOREM : If is a composite integer, then has a prime divisor less than or equal to . √ Can be used to show that a number is prime. o Primes are the building blocks of the natural numbers.  M ERSENNE NUMBER : a number of the form , . o ERSENNE PRIME M : a prime number of the form , where is a prime number. o THEOREM : If is a Mersenne prime, then is a perfect number (i.e. its divisors equal itself). 5 | P a g e CSI 2101 Summary, Winter 2013  G REATEST COMMON DIVISOR : denoted where are integers, it is the largest integer such that and . o RELATIVELY PRIME : two numbers and are relatively prime if  LEAST COMMON MULTIPLE : denoted where are integers,it is the smallest positive integer that is divisible both byand  THEOREM : If and are integers, then  EUCLID: ( )  THEOREM : Let be integers. If we have , then .  THEOREM : , such that  LEMMA : , if and , then .  LEMMA : If is prime and , then there exists an such that .  THEOREM : If , and , then .  LINEAR CONGRUENCE : a congruence of the form . Solving the congruence is finding the 's that satisfy it. You can solve it by findinsuch that , where is the multiplicative inverse of . The inverse is unique. o THEOREM : If is prime, then . Note that the converse is not true.  FERMAT ' LTTLE HTOREM : If is prime and is an integer not divisible by , then . Furthermore, for every integer , .  CARMICHAEL NUMBER : a composite number such that for all relatively prime to . These numbers are important because they fool the Fermat primarily test; the are "Fermat liars." They have at least three prime factors. Hashing Functions  Two functions: 1. Indexing hash tables (data structures which support
More Less

Related notes for CSI2101

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.