关于此课程： 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.
此课程适用人群： 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.
制作方： University of California, San Diego, National Research University Higher School of Economics
教学方： Alexander S. Kulikov, Visiting Professor
Department of Computer Science and Engineering
教学方： Michael Levin, Lecturer
Computer Science
教学方： Vladimir Podolskii, Associate Professor
Computer Science Department
| 基本信息 | |
| 级别 | Beginner |
| 承诺学习时间 | 6 weeks, 2–5 hours/week |
| 语言 | English |
| 如何通过 | 通过所有计分作业以完成课程。 |
| 用户评分 |
授课大纲
第 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 视频, 3 阅读材料
- 视频: Proofs?
- LTI Item: Puzzle: Tile a Chessboard
- 视频: Proof by Example
- 视频: Impossibility Proof
- 视频: Impossibility Proof, II and Conclusion
- Reading: Slides
- 视频: One Example is Enough
- 视频: Splitting an Octagon
- 视频: Making Fun in Real Life: Tensegrities
- 视频: Know Your Rights
- 视频: Nobody Can Win All The Time: Nonexisting Examples
- Reading: Slides
- Reading: Acknowledgements
已评分: Tiles, dominos, black and white, even and odd
已评分: Puzzle: Two Congruent Parts
已评分: Puzzle: Pluses, Minuses and Splitting
第 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 视频, 5 阅读材料
- 视频: Magic Squares
- 视频: Narrowing the Search
- 视频: Multiplicative Magic Squares
- 视频: More Puzzles
- 视频: Integer Linear Combinations
- 视频: Paths In a Graph
- Reading: Slides
- 视频: N Queens: Brute Force Search
- Reading: N Queens: Brute Force Solution Code
- 视频: N Queens: Backtracking: Example
- 视频: N Queens: Backtracking: Code
- Reading: N Queens: Backtracking Solution Code
- LTI Item: Puzzle: 16 Diagonals
- 视频: 16 Diagonals
- Reading: Slides
- 视频: Warm-up
- 视频: Subset without x and 100-x
- 视频: Rooks on a Chessboard
- 视频: Knights on a Chessboard
- 视频: Bishops on a Chessboard
- 视频: Subset without x and 2x
- Reading: Slides
已评分: Puzzle: Magic Square 3 times 3
已评分: Puzzle: Different People Have Different Coins
已评分: Puzzle: Free accomodation
已评分: Is there...
已评分: Puzzle: N Queens
已评分: Number of Solutions for the 8 Queens Puzzle
已评分: Maximum Number of Two-digit Integers
已评分: Puzzle: Maximum Number of Rooks on a Chessboard
已评分: Puzzle: Maximum Number of Knights on a Chessboard
已评分: Puzzle: Maximum Number of Bishops on a Chessboard
已评分: Puzzle: Subset without x and 2x
第 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 视频, 2 阅读材料
- 视频: Recursion
- 视频: Coin Problem
- 视频: Hanoi Towers
- Reading: Slides
- 视频: Introduction, Lines and Triangles Problem
- 视频: Lines and Triangles: Proof by Induction
- 视频: Connecting Points
- 视频: Odd Points: Proof by Induction
- 视频: Sums of Numbers
- 视频: Bernoulli's Inequality
- Notebook: Bernoulli's Inequality
- 视频: Coins Problem
- 视频: Cutting a Triangle
- 视频: Flawed Induction Proofs
- 视频: Alternating Sum
- Reading: Slides
已评分: Largest Amount that Cannot Be Paid with 5- and 7-Coins
已评分: Pay Any Large Amount with 5- and 7-Coins
已评分: Puzzle: Hanoi Towers
已评分: Number of Moves to Solve the Hanoi Towers Puzzle
已评分: Puzzle: Two Cells of Opposite Colors
已评分: Puzzle: Connect Points
已评分: Induction
第 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 视频, 2 阅读材料
- 视频: Examples
- 视频: Counterexamples
- 视频: Basic Logic Constructs
- 视频: If-Then Generalization, Quantification
- Reading: Slides
- 视频: Reductio ad Absurdum
- 视频: Balls in Boxes
- 视频: Numbers in Tables
- 视频: Pigeonhole Principle
- 视频: An (-1,0,1) Antimagic Square
- 视频: Handshakes
- Reading: Slides
已评分: Puzzle: Always Prime?
已评分: Examples, Counterexamples and Logic
已评分: Puzzle: Balls in Boxes
已评分: Puzzle: Numbers in Boxes
已评分: Puzzle: Numbers on the Chessboard
已评分: Numbers in Boxes
已评分: How to Pick Socks
已评分: Pigeonhole Principle
已评分: Puzzle: An (-1,0,1) Antimagic Square
第 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 programs and algorithms. We will get some intuition of what they are, see how they can look like, and get some practice in using them.
11 视频, 4 阅读材料, 3 练习测试
- 视频: Double Counting
- 视频: `Homework Assignment' Problem
- Reading: Slides
- Practice Quiz: Coffee with Milk
- 视频: Invariants
- Practice Quiz: More Coffee
- 视频: More Coffee
- 视频: Debugging Problem
- Reading: Slides
- Practice Quiz: Football Fans
- 视频: Termination
- 视频: Arthur’s Books
- Reading: Slides
- 视频: Even and Odd Numbers
- 视频: Summing up Digits
- 视频: Switching Signs
- 视频: Advanced Signs Switching
- Reading: Slides
已评分: Puzzle: Sums of Rows and Columns
已评分: 'Homework Assignment' Problem
已评分: 'Homework Assignment' Problem 2
已评分: Chess Tournaments
已评分: Debugging Problem
已评分: Merging Bank Accounts
已评分: Puzzle: Arthur's Books
已评分: Puzzle: Piece on a Chessboard
已评分: Operations on Even and Odd Numbers
已评分: Puzzle: Summing Up Digits
已评分: Puzzle: Switching Signs
已评分: Recolouring Chessboard
第 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 will 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 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 视频, 3 阅读材料, 1 练习测试
- 视频: The Rules of 15-Puzzle
- 视频: Permutations
- 视频: Proof: The Difficult Part
- 视频: Mission Impossible
- 视频: Classify a Permutation as Even/Odd
- 视频: Bonus Track: Fast Classification
- Reading: Slides
- 视频: Project: The Task
- Reading: Even permutations
- Reading: Bonus Track: Finding The Sequence of Moves
- Practice Quiz: Bonus Track: Algorithm for 15-Puzzle
- 视频: Quiz Hint: Why Every Even Permutation Is Solvable
已评分: Puzzle: 15
已评分: Transpositions and Permutations
已评分: Neighbor transpositions
已评分: Is a permutation even?
常见问题解答
运作方式
Coursework
Each course is like an interactive textbook, featuring pre-recorded videos, quizzes and projects.
Help from Your Peers
Connect with thousands of other learners and debate ideas, discuss course material, and get help mastering concepts.
Certificates
Earn official recognition for your work, and share your success with friends, colleagues, and employers.
制作方
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.
National Research University 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
价格
| 购买课程 | |
|---|---|
| 访问课程材料 | 可用 |
| 访问评分的材料 | 可用 |
| 收到最终成绩 | 可用 |
| 获得可共享的课程证书 | 可用 |
评分和审阅
Simple explanations made math more easy to handle. Thanks to the prof's for timely responses in Forums.
Broken English and an inflated $79 to take practice tests, but the professor is knowledgeable and makes proofs fun.
Pretty good course, although the topics were sometimes confusing. I think this is to be expected given the nature of the topic, as it's a whole new way of thinking about mathematical problems. I wish the course put some of the techniques used when solving the puzzles into a more explicit or formal context. After some of the puzzles, I was left wondering how to generalize the specific problem-solving technique or insight.
m
Love the teaching style.