美国加州大学圣地亚哥分校

Mathematical Thinking in Computer Science

116 评分

课程 1（共 5 门，Specialization Introduction to Discrete Mathematics for Computer Science）

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.

从本节课中

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.

Proofs?3:47

Proof by Example1:50

Impossibility Proof2:34

Impossibility Proof, II and Conclusion3:53

与讲师见面

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Vladimir Podolskii
Associate Professor
Computer Science Department

This indeed is impossible.

So, let's see why it's impossible.

It's our second impossibility proof.

It's a bit more complicated than the first one,but not that complicated.

So, the question is can we tile this board?

The answer is negative,

and there is a reason for that.

So, stop now if you don't want to see the spoiler and I'll show it now.

So, this is the Chessboard coloring,

so you know that the chessboard has black and white cells,

and we have two corners that we deleted.

They are both black,

and why this is important?

Because originally we have 664 cells and 32 of them were black and 32 white.

They were just four in each,

black and four white in each row and in each column.

So, now we have,

if you use a tile,

we use always one black cell and one white cell.

So, if we have an equal number,

we have 32 white and on restore it to black.

So, two whites will remain because they don't have black pairs,

so, it's impossible to cover the board.

So, let's make the serious,

explain it like mathematician seriously,

pretend that we are serious mathematicians.

So, a theorem, a Chessboard 8*8 without

two opposite corner cannot be tiled by dominos 1*2.

Why?

The proof.

First, we note that in the coloring we have

black and white cells and in each row and each column we have four black and four white.

So, we can count the total number of cells.

And opposite corners are black,

they can be also white,

but let's consider the case when they are black.

And then we have 30 black and 32 white cells,

and this numbers are different each domino has two different colors,

so, it covers one black and one white.

And there is no chance that we cover everything at least two white should

remain and like mathematician like say ''quod erat demostradum''.

It's Latin which means that,

that's what we wanted to prove.

So, this is the prove.

Now, let's see what we can learn from these examples.

So, I hope that you are now convinced that indeed we cannot tile the board.

The proof can be really convincing hopefully.

And there are many questions we can ask after that,

imagine we cut two corners but they are not opposite corners,

but corners on one side.

Can we tell the rest,

they are actually of different colors.

So, the obstacle doesn't exist,

can you tile the rest?

Or imagine we just cut any two cells of different colors,

is it always possible to tile the rest?

And I will not tell you the solution,

but I will just show you some picture which contains some ideas.

So, this picture is a bit strange but still it's look like this.

So, why the snake?

There is a snake going like.

So, why the snake?

What is the connection of the snake with our problem.

So, we cut two cells of different colors, black and white.

And we want to tile the rest with the dominos,

how the snake can help us, do you see this.