What is a Proof?

Product type
Logo Coursera (CC)
Provider rating: starstarstarstar_borderstar_border 6.3 Coursera (CC) has an average rating of 6.3 (out of 4 reviews)

Need more information? Get more details on the site of the provider.

Description

When you enroll for courses through Coursera you get to choose for a paid plan or for a free plan

  • Free plan: No certicification and/or audit only. You will have access to all course materials except graded items.
  • Paid plan: Commit to earning a Certificate—it's a trusted, shareable way to showcase your new skills.

About this course: There is a perceived barrier to mathematics: proofs. In this course we will try to convince you that this barrier is more frightening than prohibitive: most proofs are easy to understand if explained correctly, and often they are even fun. We provide an accompanied excursion in the “proof zoo” showing you examples of techniques of different kind applied to different topics. We use some puzzles as examples, not because they are “practical”, but because discussing them we learn important reasoning and problem solving techniques that are useful. We hope you enjoy playing with the puzzles and inventing/understandings the proofs. As prerequisites we assume only basic math …

Read the complete description

Frequently asked questions

There are no frequently asked questions yet. If you have any more questions or need help, contact our customer service.

Didn't find what you were looking for? See also: Python, Aggression Management, Business Writing, Reading & Writing, and Communication Skills.

When you enroll for courses through Coursera you get to choose for a paid plan or for a free plan

  • Free plan: No certicification and/or audit only. You will have access to all course materials except graded items.
  • Paid plan: Commit to earning a Certificate—it's a trusted, shareable way to showcase your new skills.

About this course: There is a perceived barrier to mathematics: proofs. In this course we will try to convince you that this barrier is more frightening than prohibitive: most proofs are easy to understand if explained correctly, and often they are even fun. We provide an accompanied excursion in the “proof zoo” showing you examples of techniques of different kind applied to different topics. We use some puzzles as examples, not because they are “practical”, but because discussing them we learn important reasoning and problem solving techniques that are useful. We hope you enjoy playing with the puzzles and inventing/understandings the proofs. As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students.

Who is this class for: Our intended audience are all people that work or plan to work in IT, starting from motivated high school students. Almost no math background is assumed.

Created by:  University of California, San Diego, Higher School of Economics
  • Taught by:  Alexander S. Kulikov, Visiting Professor

    Department of Computer Science and Engineering
  • Taught by:  Michael Levin, Lecturer

    Computer Science
  • Taught by:  Vladimir Podolskii, Associate Professor

    Computer Science Department
Basic Info Course 1 of 5 in the Introduction to Discrete Mathematics for Computer Science Specialization Level Beginner Commitment 6 weeks, 2–5 hours/week Language English How To Pass Pass all graded assignments to complete the course. 课程作业

每门课程都像是一本互动的教科书,具有预先录制的视频、测验和项目。

来自同学的帮助

与其他成千上万的学生相联系,对想法进行辩论,讨论课程材料,并寻求帮助来掌握概念。

证书

获得正式认证的作业,并与朋友、同事和雇主分享您的成功。

University of California, San Diego UC San Diego is an academic powerhouse and economic engine, recognized as one of the top 10 public universities by U.S. News and World Report. Innovation is central to who we are and what we do. Here, students learn that knowledge isn't just acquired in the classroom—life is their laboratory. Higher School of Economics National Research University - Higher School of Economics (HSE) is one of the top research universities in Russia. Established in 1992 to promote new research and teaching in economics and related disciplines, it now offers programs at all levels of university education across an extraordinary range of fields of study including business, sociology, cultural studies, philosophy, political science, international relations, law, Asian studies, media and communications, IT, mathematics, engineering, and more. Learn more on www.hse.ru

Syllabus


WEEK 1


Why proofs?



What is a proof? Why do we care about proofs? Are the boring long tedious arguments usually known as `mathematical proofs' really needed outside the tiny circle of useless theoreticians that pray something called `mathematical rigor'? In this course we will try to show that proofs can be simple, elegant, convincing, useful and (don't laugh) exciting. Later we will try to show different proof techniques and tools, but first of all we should break the barrier and see that yes, one can understand a proof and one can enjoy the proof. We start with simple puzzles where one small remark can disclose "what really happens there" and then the proof becomes almost obvious.


9 videos, 3 readings expand


  1. Video: Proofs?
  2. LTI 项目: Interactive Quiz: Tile a Chessboard
  3. Video: Proof by Example
  4. Video: Impossibility Proof
  5. Video: Impossibility Proof, II and Conclusion
  6. 阅读: Slides
  7. Video: One Example is Enough
  8. Video: Splitting an Octagon
  9. Video: Making Fun in Real Life: Tensegrities
  10. Video: Know Your Rights
  11. Video: Nobody Can Win All The Time: Nonexisting Examples
  12. 阅读: Slides
  13. 阅读: Acknowledgements

Graded: Tiles, dominos, black and white, even and odd
Graded: Two Congruent Parts
Graded: Pluses, Minuses and Splitting

WEEK 2


How to Find an Example?



One example is enough to prove an existential statement, but how to find an example? In many cases the search space is enormous. A computer may help, but some reasoning that narrows the search space, is important both for computer search and for "bare hands" work — how can this be done? What do we need to prove if we claim that our solution is optimal? As usual, we'll practice solving many interactive puzzles. We'll show also some computer programs that help us to construct an example.


16 videos, 5 readings expand


  1. Video: Magic Squares
  2. Video: Narrowing the Search
  3. Video: Multiplicative Magic Squares
  4. Video: Puzzles
  5. Video: Integer Linear Combinations
  6. Video: Paths In a Graph
  7. 阅读: Slides
  8. Video: N Queens: Brute Force Search
  9. 阅读: N Queens: Brute Force Solution Code
  10. Video: N Queens: Backtracking: Example
  11. Video: N Queens: Backtracking: Code
  12. 阅读: N Queens: Backtracking Solution Code
  13. LTI 项目: Puzzle: 16 Diagonals
  14. Video: 16 Diagonals
  15. 阅读: Slides
  16. Video: Warm-up
  17. Video: Subset without x and 100-x
  18. Video: Rooks on a Chessboard
  19. Video: Knights on a Chessboard
  20. Video: Bishops on a Chessboard
  21. Video: Subset without x and 2x
  22. 阅读: Slides

Graded: Magic Square 3 times 3
Graded: Different People Have Different Coins
Graded: Free accomodation
Graded: Is there...
Graded: Puzzle: N Queens
Graded: Number of Solutions for the 8 Queens Puzzle
Graded: Maximum Number of Two-digit Integers
Graded: Puzzle: Maximum Number of Rooks on a Chessboard
Graded: Puzzle: Maximum Number of Knights on a Chessboard
Graded: Puzzle: Maximum Number of Bishops on a Chessboard
Graded: Puzzle: Subset without x and 2x

WEEK 3


Recursion and Induction



We'll discover two powerful methods of defining objects, proving concepts, and implementing programs — recursion and induction. These two methods are heavily used, in particular, in algorithms — for analysing correctness and running time of algorithms as well as for implementing efficient solutions. You will see that induction is as simple as falling dominos, but allows to prove complex things by decomposing them and moving step by step. You will learn how famous Gauss unexpectedly solved his teacher's problem intended to keep him busy the whole lesson in just two minutes, and in the end you will be able to prove his formula using induction. You will be able to generalize scary arithmetic exercises and then solve them easily using induction.


13 videos, 1 reading expand


  1. Video: Recursion
  2. Video: Coin Problem
  3. Video: Hanoi Towers
  4. 阅读: Slides
  5. Video: Introduction, Lines and Triangles Problem
  6. Video: Lines and Triangles: Proof by Induction
  7. Video: Connecting Points
  8. Video: Odd Points: Proof by Induction
  9. Video: Sums of Numbers
  10. Video: Bernoulli's Inequality
  11. 笔记本: Bernoulli's Inequality
  12. Video: Coins Problem
  13. Video: Cutting a Triangle
  14. Video: Flawed Induction Proofs
  15. Video: Alternating Sum

Graded: Largest Amount that Cannot Be Paid with 5- and 7-Coins
Graded: Pay Any Large Amount with 5- and 7-Coins
Graded: Puzzle: Hanoi Towers
Graded: Number of Moves to Solve the Hanoi Towers Puzzle
Graded: Puzzle: Two Cells of Opposite Colors
Graded: Puzzle: Connect Points
Graded: Induction

WEEK 4


Logic



We have already invoked mathematical logic when we discussed proofs by examples. This week we will turn mathematical logic full on. We will discuss its basic operations and rules. We will see how logic can play a crucial and indispensable role in proofs. We will discuss how to construct a negation to the statement and we will meet the notion of a counterexamples. We will see tricky and seemingly counterintuitive, but yet (an unintentional pun) logical aspects of mathematical logic. We will see one of the oldest approaches to proving statements: Reductio ad Absurdum.


10 videos, 1 reading expand


  1. Video: Examples
  2. Video: Counterexamples
  3. Video: Basic Logic Constructs
  4. Video: If-Then Generalization, Quantification
  5. Video: Reductio ad Absurdum
  6. Video: Balls in Boxes
  7. Video: Numbers in Tables
  8. Video: Pigeonhole Principle
  9. Video: An (-1,0,1) Antimagic Square
  10. Video: Handshakes
  11. 阅读: Slides

Graded: Always Prime?
Graded: Examples, Counterexamples and Logic
Graded: Puzzle: Balls in Boxes
Graded: Numbers in Boxes
Graded: Numbers on the Chessboard
Graded: Numbers in Boxes
Graded: How to Pick Socks
Graded: Pigeonhole Principle
Graded: Puzzle: An (-1,0,1) Antimagic Square

WEEK 5


Invariants



"There are things that never change". Apart from being just a philosophical statement this phrase turns out to be an important idea that can actually help. In this module we will see how it can help in problem solving. Things that do not change are called invariants in mathematics. They form an important tool of proving with numerous applications, including estimating running time of algorithms. We will get some intuition of what they are, see how they can look like and get some practice in using them.


11 videos, 4 readings, 3 practice quizzes expand


  1. Video: Double Counting
  2. Video: `Homework Assignment' Problem
  3. 阅读: Slides
  4. 练习测验: Coffee with Milk
  5. Video: Invariants
  6. 练习测验: Coffee
  7. Video: Coffee
  8. Video: Debugging Problem
  9. 阅读: Slides
  10. 练习测验: Football Fans
  11. Video: Termination
  12. Video: Arthur’s Books
  13. 阅读: Slides
  14. Video: Even and Odd Numbers
  15. Video: Summing up Digits
  16. Video: Switching Signs
  17. Video: Advanced Signs Switching
  18. 阅读: Slides

Graded: Puzzle: Sums of Rows and Columns
Graded: 'Homework Assignment' Problem
Graded: 'Homework Assignment' Problem 2
Graded: Chess Tournaments
Graded: Debugging Problem
Graded: Merging Bank Accounts
Graded: Puzzle: Arthur's Books
Graded: Puzzle: Piece on a Chessboard
Graded: Operations on Even and Odd Numbers
Graded: Puzzle: Summing Up Digits
Graded: Switching Signs
Graded: Recolouring Chessboard

WEEK 6


Solving a 15-Puzzle



In this module we consider a well known 15-puzzle where one needs to restore order among 15 square pieces in a square box. It turns out that the behavior of this puzzle is determined by mathematics: it is solvable if and only if the corresponding permutation is even. We learn the basic properties of even and odd permutations. The task is to write a program that determines whether a permutation is even or odd. There is also a much more difficult bonus task: to write a program that actually computes a solution (sequence of moves) for a given position assuming that this position is solvable.


8 videos, 3 readings, 1 practice quiz expand


  1. Video: The Rules of 15-Puzzle
  2. Video: Permutations
  3. Video: Proof: The Difficult Part
  4. Video: Mission Impossible
  5. Video: Classify a Permutation as Even/Odd
  6. Video: Bonus Track: Fast Classification
  7. 阅读: Slides
  8. Video: Project: The Task
  9. 阅读: Even permutations
  10. 阅读: Bonus Track: Finding The Sequence of Moves
  11. 练习测验: Bonus Track: Algorithm for 15-Puzzle
  12. Video: Quiz Hint: Why Every Even Permutation Is Solvable

Graded: Interactive 15-puzzle
Graded: Transpositions and Permutations
Graded: Neighbor transpositions
Graded: Is a permutation even?
There are no reviews yet.
  • View related products with reviews: Python.

Share your review

Do you have experience with this course? Submit your review and help other people make the right choice. As a thank you for your effort we will donate £1.- to Stichting Edukans.

There are no frequently asked questions yet. If you have any more questions or need help, contact our customer service.