關於此課程：Mathematical thinking is crucial in all areas of computer science: algorithms, bioinformatics, computer graphics, data science, machine learning, etc. In this course, we will learn the most important tools used in discrete mathematics: induction, recursion, logic, invariants, examples, optimality. We will use these tools to answer typical programming questions like: How can we be certain a solution exists? Am I sure my program computes the optimal answer? Do each of these objects meet the given requirements? In the course, we use a try-this-before-we-explain-everything approach: you will be solving many interactive (and mobile friendly) puzzles that were carefully designed to allow you to invent many of the important ideas and concepts yourself. Prerequisites: 1. We assume only basic math (e.g., we expect you to know what is a square or how to add fractions), common sense and curiosity. 2. Basic programming knowledge is necessary as some quizzes require programming in Python.
此課程適用人群：Our intended audience are all people that work or plan to work in IT, starting from motivated high school students. Prerequisites: 1. We assume only basic math (e.g., we expect you to know what is a square or how to add fractions), common sense and curiosity. 2. Basic programming knowledge is necessary as some quizzes require programming in Python.
製作方： 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
| 基本信息 | |
| 級別 | 初級 |
| 承諾學習時間 | 6 weeks, 2–5 hours/week |
| 語言 | English |
| 如何通過 | 通過所有計分作業以完成課程。 |
| 用戶評分 |
授課大綱
第 1 週
Making Convincing Arguments
Why some arguments are convincing and some are not? What makes an argument convincing? How to establish your argument in such a way that there is no possible room for doubt left? How mathematical thinking can help with this? In this week we will start digging into these questions. We will see how a small remark or a simple observation can turn a seemingly non-trivial question into an obvious one. Through various examples we will observe a parallel between constructing a rigorous argument and mathematical reasoning.
10 個視頻, 4 個閱讀材料
- 視頻: Proofs?
- Элемент LTI: Puzzle: Tile a Chessboard
- 視頻: Proof by Example
- 視頻: Impossibility Proof
- 視頻: Impossibility Proof, II and Conclusion
- Материал для самостоятельного изучения: Slides
- Материал для самостоятельного изучения: Python
- 視頻: One Example is Enough
- 視頻: Splitting an Octagon
- 視頻: Making Fun in Real Life: Tensegrities
- 視頻: Know Your Rights
- 視頻: Nobody Can Win All The Time: Nonexisting Examples
- Материал для самостоятельного изучения: Slides
- Материал для самостоятельного изучения: Acknowledgements
已評分: Tiles, dominos, black and white, even and odd
已評分: Puzzle: Two Congruent Parts
已評分: Puzzle: Pluses, Minuses and Splitting
第 2 週
How to Find an Example?
How can we be certain that an object with certain requirements exist? One way to show this, is to go through all objects and check whether at least one of them meets the requirements. However, 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. In this module, we will learn various techniques for showing that an object exists and that an object is optimal among all other objects. 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 個閱讀材料, 1 個練習測驗
- 視頻: Narrowing the Search
- 視頻: Multiplicative Magic Squares
- 視頻: More Puzzles
- 視頻: Integer Linear Combinations
- 視頻: Paths In a Graph
- Материал для самостоятельного изучения: Slides
- Элемент LTI: Puzzle: N Queens (Optional)
- 視頻: N Queens: Brute Force Search (Optional)
- Материал для самостоятельного изучения: N Queens: Brute Force Solution Code (Optional)
- 視頻: N Queens: Backtracking: Example (Optional)
- 視頻: N Queens: Backtracking: Code (Optional)
- Материал для самостоятельного изучения: N Queens: Backtracking Solution Code (Optional)
- Элемент LTI: Puzzle: 16 Diagonals (Optional)
- 視頻: 16 Diagonals (Optional)
- Тренировочный тест: Number of Solutions for the 8 Queens Puzzle (Optional)
- Материал для самостоятельного изучения: Slides (Optional)
- 視頻: 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
- Материал для самостоятельного изучения: Slides
已評分: Puzzle: Magic Square 3 times 3
已評分: Puzzle: Different People Have Different Coins
已評分: Puzzle: Free accomodation
已評分: Is there...
已評分: 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 make convincing arguments for arbitrarily large and complex problems 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 個閱讀材料
- 視頻: Coin Problem
- 視頻: Hanoi Towers
- Материал для самостоятельного изучения: 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
- Блокнот: Bernoulli's Inequality
- 視頻: Coins Problem
- 視頻: Cutting a Triangle
- 視頻: Flawed Induction Proofs
- 視頻: Alternating Sum
- Материал для самостоятельного изучения: 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 how to make convincing arguments by giving 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 creating convincing arguments. We will discuss how to construct a negation to the statement, and you will see how to win an argument by showing your opponent is wrong with just one example called counterexample!. 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 making convincing arguments: Reductio ad Absurdum.
10 個視頻, 2 個閱讀材料
- 視頻: Counterexamples
- 視頻: Basic Logic Constructs
- 視頻: If-Then Generalization, Quantification
- Материал для самостоятельного изучения: Slides
- 視頻: Reductio ad Absurdum
- 視頻: Balls in Boxes
- 視頻: Numbers in Tables
- 視頻: Pigeonhole Principle
- 視頻: An (-1,0,1) Antimagic Square
- 視頻: Handshakes
- Материал для самостоятельного изучения: 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 個練習測驗
- 視頻: `Homework Assignment' Problem
- Материал для самостоятельного изучения: Slides
- Тренировочный тест: Coffee with Milk
- 視頻: Invariants
- Тренировочный тест: More Coffee
- 視頻: More Coffee
- 視頻: Debugging Problem
- Материал для самостоятельного изучения: Slides
- Тренировочный тест: Football Fans
- 視頻: Termination
- 視頻: Arthur’s Books
- Материал для самостоятельного изучения: Slides
- 視頻: Even and Odd Numbers
- 視頻: Summing up Digits
- 視頻: Switching Signs
- 視頻: Advanced Signs Switching
- Материал для самостоятельного изучения: 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 個練習測驗
- 視頻: Permutations
- 視頻: Proof: The Difficult Part
- 視頻: Mission Impossible
- 視頻: Classify a Permutation as Even/Odd
- 視頻: Bonus Track: Fast Classification
- Материал для самостоятельного изучения: Slides
- 視頻: Project: The Task
- Материал для самостоятельного изучения: Even permutations
- Материал для самостоятельного изучения: Bonus Track: Finding The Sequence of Moves
- Тренировочный тест: 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?
常見問題解答
運作方式
Задания курса
Каждый курс — это интерактивный учебник, который содержит видеоматериалы, тесты и проекты.
Помощь сокурсников
Общайтесь с тысячами других учащихся: обсуждайте идеи, материалы курса и помогайте друг другу осваивать новые понятия.
Сертификаты
Получите документы о прохождении курсов и поделитесь своим успехом с друзьями, коллегами и работодателями.
製作方
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
價格
| 購買課程 | |
|---|---|
| 訪問課程材料 | 可用 |
| 訪問評分的材料 | 可用 |
| 收到最終成績 | 可用 |
| 獲得可共享的課程證書 | 可用 |
評分和審閱
Nice course! I want to say thanks to teachers. Course was informative and new for me!
This course helps you to put your arguments forward to convince self and other people. There are several techniques to do that. Sometimes providing a single example does the trick while providing counter examples become necessary in other situations. Learners of this course will get new insight about known puzzles. How to find examples is an important part of this course. Alex and Michale are pretty good to put the thoughts that they have. Other lecturers sometimes may confuse pupil. Overall a great start to learn discrete mathematics.
I like the new title "Mathematical Thinking in Computer Science" rather than "What is a proof?". Good course for beginners of the subject discrete mathematics. It really does what the title says. It helps improve your mathematical thinking and prepares you for computer science studies.
EZ
The course is well structured, and made interesting with interactive puzzles.