Explore
For Enterprise
Join for Free
Log In

Artes e Humanas
Negócios
Ciência da Computação
Ciência de Dados
Tecnologia da informação
da saúdesaúde
Matemática e Lógica
Desenvolvimento Pessoal
Ciência e Engenharia Física
Ciências Sociais
Línguas
Notas
Certificados

Explore todo o Coursera

Navegar
Pesquisar
For Enterprise
Entrar
Inscreva-se gratuitamente

Hanoi Towers

Loading...

Mathematical Thinking in Computer Science

Universidade da Califórnia, San Diego

4.4 (546 classificações) | 30K alunos inscritos

Curso 1 de 5 no Introduction to Discrete Mathematics for Computer Science Programa de cursos integrados

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.

Visualizar o programa do curso

Habilidades que você aprenderá

Mathematical Induction, Proof Theory, Discrete Mathematics, Mathematical Logic

Avaliações

4.4 (546 classificações)

5 stars
354 ratings
4 stars
120 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!

Na lição

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.

Coin Problem4:45

Hanoi Towers7:25

Ministrado por

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

Transcrição

Our final example is the well known Hanoi Towers puzzle.

In this puzzle, we're given three sticks.

Two of them are initially empty.

On the first stick, we have n discs,

sorted by size as shown here on the slide.

Our goal is to move all n discs to some other stick,

to one of the two empty sticks.

This would be easy if not given two constraints.

First of all, we are allowed to move only one disc at a time, and naturally we need

to take the top most disc from one stick, and to put it to some other stick, right?

And also we are not allowed to put a larger disc onto a smaller disc, okay?

So the question is whether it is possible for, and if it is possible,

then for which values of n this is possible, okay?

So it is known to be possible for every value of n.

At the same time, it is not clear at this point how can we be sure

that it is possible for every possible value of n.

We can check that it is possible for one, for two, for three, for four, and so on.

But it is not so clear how to ensure that just for

every even very huge number, it is always possible.

And of course, we are going to use recursion again

to show how to do this for every possible value of n.

For this, we will first explain that it is possible when n is equal to 1,

and then we will show that if it is possible for n minus 1, for example,

then it is possible for n.

This will ensure that, if it is possible for one, then it is possible for two.

If it is possible for two, then it is possible for three.

If it is possible for three, then it is possible for four, and so on.

So our goal is basically to show that it is possible in the beginning,

when n is equal to 1.

And then we need to show some generic procedure of building a solution for

n discs using a recursive solution for n minus 1 discs, okay?

So let's start.

So the simplest possible case is indeed when there is just one disc.

So in this case, n is equal to 1, and

our goal is to move this disc to some other place, to some other stick,

and of course it is very easy to do this so we just move it to another stick.

Now let's also consider two discs just to get a feeling of how

to solve this problem.

Now in this case, we first move the smallest disc.

So we move it to this stick, then we move the larger disc to another stick.

And finally, we move the smaller one onto larger one, right?

So for two discs, it is also possible.

Now let's consider a general case, where we have n discs.

And let's focus on the larger discs, on the large disc, I'm sorry.

So what is the condition under which we can move it?

So first of all, if we are moving the large disc,

this actually means that all the remaining n minus 1

discs are already on some other stick.

So probably a part of them are on one disc, and

all the remaining of them on the third stick.

I'm sorry.

So if we are moving this large disc, so for which stick we can move it?

So I'm claiming that the only stick for

which we can move it is the empty stick, right?

Because if there are any discs on this stick then we will be allayed the rules.

If there is at least one stick, at least one disc, I'm sorry, on this stick then by

moving the largest disc to this stick, we will put a larger disc onto a smaller one.

So this means that when we are moving the largest disc,

we should move it to an empty stick.

Which in turn means that all the other discs at this point

should be put to the same stick.

And since we know that all the discs are always in increasing order,

we know that at this point, all the other discs should be located as follows, right?

So when we are moving the large disc,

all the remaining discs should be at some other stick.

Which means that up to this point, we've moved all other n minus 1 discs.

So we actually solved the problem for n minus 1 discs, right?

And this gives us an idea for a recursive solution.

Because this is essentially the same problem which was solved for

n minus 1 discs, so a recursive solution in this case is the following.

So we first move n minus 1 discs recursively, to some other stick.

So then we will reach the following state.

After this, we move the largest disc, okay?

And then finally we move, once again, the n minus 1 discs.

Again, using a recursive call, okay?

So we know how to do this because we can call the same

procedure with parameter n minus 1.

And this finally gives us the solution, right?

So again, we reduce the problem with parameter n to the problem

with parameter n minus 1.

This problem in turn will be reduced through a problem with parameter

n minus 2, then with n minus 3, and so on.

Until we reach 1, and for 1, we know that it is possible, right?

So essentially, what we've proved is that it is possible for every value of n.

We can consider this for example like this.

We know that it is possible for 1, then it is possible for 2, right?

Then since it is possible for 2, it is also possible for 3, and so on.

So it will be possible for all the numbers.

Or put it otherwise, to solve the problem for n, we need to solve it for n minus 1.

To solve the problem for n minus 1, we need to solve it for n minus 2.

Meaning that if we know how to do this for n minus 2,

then we definitely know how to do this for n minus 1 and so on.

So going backwards, we will reach 1, and for 1, we know that it is possible.

So which actually proves that it is possible,

and what just happened is that actually we have proved that it is

possible by induction, which is a highly related notion to recursion.

So saying very roughly, induction is a mathematical method for

proving something, where recursion is a method of defining something or

a method of implementing something.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play

Coursera
Sobre
Liderança
Carreiras
Lista de cursos
Certificados
Certificados MasterTrack™
Notas
For Enterprise
For Government

Comunidade
Learners
Partners
Developers
Beta Testers
Translators

Conectar
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Tech Blog

Mais
Termos
Privacidade
Ajuda
Acessibilidade
Imprensa
Contato
Diretório
Afiliados