Join for Free
Log In

艺术与人文
商务
计算机科学
数据科学
信息技术
健康
数学和逻辑
个人发展
物理科学与工程
社会科学
语言学习
學位
證書

瀏覽 Coursera 的全部課程

瀏覽
搜索
企業版
登錄
免費加入

Even and Odd Numbers

Loading...

Mathematical Thinking in Computer Science

加州大学圣地亚哥分校

4.5（567 個評分） | 31K 名學生已註冊

課程 1（共 5 門，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. Do you have technical problems? Write to us: coursera@hse.ru

查看授課大綱

您將學習的技能

Mathematical Induction, Proof Theory, Discrete Mathematics, Mathematical Logic

審閱

4.5（567 個評分）

5 stars
369 ratings
4 stars
126 ratings
3 stars
47 ratings
2 stars
12 ratings
1 star
13 ratings

KL

Nov 29, 2018

The course is excellent and most stuff is being taught in a nicely presented way. The main disappointment is 15-puzzle, because it's too difficult to understand without proper material.

DG

Jun 30, 2018

Love the quality of thought that goes into each lesson. The professors speak with acute clarity and really demonstrate and empathy for the student to truly understand the topics!

從本節課中

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.

Even and Odd Numbers4:36

Summing up Digits4:36

Switching Signs3:19

Advanced Signs Switching8:30

教學方

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Vladimir Podolskii
Associate Professor

腳本

Hi, I'm Vladimir Poldoskii,

and today we're going to discuss the properties of numbers to be even or odd.

Even numbers are integer numbers that are divisible by two.

And odd numbers are all other integer numbers.

For example, numbers 2, 4, 6,

8, and so on are even. They're divisible by two.

And numbers 1, 3, 5,

7, are odd, they're not divisible by two.

What about number zero?

Zero is also an even number, it is divisible by two.

We can divide zero by two and obtain zero.

It is also an integer,

so zero is even.

It is also useful to look at numbers on the number line.

Let's position all numbers in the increasing order, all integer numbers.

And let's color even numbers in green color and odd numbers in the red color.

Now we can see that odd and even numbers are interchangeable on this line.

Zero is even and one is odd and two is even and three is odd and so on,

and the same in reverse direction.

So even and odd numbers are interchangeable and this is good to keep in mind.

The properties of numbers to be even or odd

are important invariants that I use very often.

Let's see it on the example.

Consider a full on problem.

We have a chessboard and a piece which can move in one move,

in one move it can move to one cell that is adjacent by edge to the current one.

It can one cell the right,

to the left, up, or down.

Can it return to the original position after 17 moves or after 18 moves?

So there are two questions in this problem.

So let's proceed to a solution and let's start with a more simple case of 18 moves.

This case is more simple because it's possible to

return to the initial position in this case

and it is usually more simple to show

possibility to do something than impossibility to do something.

Okay, let's see how to do this.

It turns out that you can return to the initial position just after just two steps.

And you can do for example in this way,

you can move to the right first and then on the second step we can move

back and so they are back in the initial position after just two steps.

And now we can just repeat it nine times and

we'll be back in the initial position after 18 moves.

And note that here in the solution we used,

that 18 is an even number.

It is divisible by two,

so we can return to the initial position just two steps and then it

repeats a certain number of times and get to the initial position two after 18 moves.

So now let's proceed to the second part.

The previous solution doesn't work because 17 is odd,

and we can not just apply the same argument we used that 18 is even.

So now we have to do something else and it turns out that even more of it,

in this case this is impossible.

And let's see why.

It turns out that we can make a full on observation.

After even number of steps this piece is always on the white field.

And after odd number of steps it is always on the black field.

Indeed it, initially zero steps,

it is on the white field.

Then it moves after the first steps,

the number of steps becomes odd and the piece should move to the black cell,

and then after a second step it moves to the white cell.

But now the number of steps is two and it is even, and so on and so forth.

So we can observe it this also,

this property always is satisfied,

and this is our invariant.

And this means that there is no way to get back after odd number of steps.

Let's observe 17 as odd again.

Because after 17 number of steps you will be on

the black square and our initial square is white.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2019 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取

Coursera
關於
管理團隊
工作機會
目錄
證書
MasterTrack™ 證書
學位
企業版
政府版

社區
Learners
Partners
Developers
Beta Testers
Translators

連接
博客
Facebook
領英
Twitter
Instagram
YouTube
技術博客

更多
條款
隱私
幫助
內容訪問
媒體
聯繫我們
目錄
附屬公司