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

Coin Problem

Loading...

Mathematical Thinking in Computer Science

Universidade da Califórnia, San Diego

4.5 (567 classificações) | 31K 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. Do you have technical problems? Write to us: coursera@hse.ru

Visualizar o programa do curso

Habilidades que você aprenderá

Mathematical Induction, Proof Theory, Discrete Mathematics, Mathematical Logic

Avaliações

4.5 (567 classificações)

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!

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

Now, consider the following coin problem.

So our goal is to prove that any integer amount starting from 8 can

be paid using coins of denominations 3 and 5.

Okay?

So this is our problem, and let's try to investigate.

So first of all, let's check whether 8 and 9 and 10 and 11 can be indeed paid.

So this looks reasonable because 8 is 3 + 5,

9 is 3 + 3 + 3, 10 is 5 + 5,

11 is 3 + 3 + 5, so it seems to be possible.

However, it is still not at all clear whether it is possible for all values.

It is also not at all clear

why are we talking about this problem in the lesson called recursion.

Because recursion was about programs or about definitions.

At the same time, what we are going to do

is to prove that this is possible using recursion.

And in fact, we are going to implement the program that is going

to change any such amount into coins of denominations 3 and 5.

So for this, as usual, let's think about these problems.

So we know already that we can pay 8.

But this immediately that we can also pay 11, right?

Because 11 is just 8 + 3.

So in a sense, we reduce the problem of change in 11

into coins to the problem of changing 8 into coins.

But for 8, we that this is possible which means that for 8, for 11,

it is also possible.

Moreover, if you know how to change 8 then by adding just one single coin,

you had a change for 11, right?

And also 11 in terms, gives 14 then 17 then 20 and then so on.

So an infinite number of amounts can be changed into points 3 and

5 just because 8 can be changed into 3 and 5, right?

Then we would do the same trick with 9.

So it seems we know how to change 9 then we know how to change 12,

15, 21 and so on.

And 10 gives us 13, 16, 19, 22 and so on.

Right?

So this gives us the possibility to implement the following

recursive procedure.

We call the change, and it is given an amount that we need to change.

And the first thing to do,

we check whether the given amount is indeed greater than 8, right?

Then if it is equal to 8 then we just return the representation of 8,

the sum of 3 and 5.

So we just return a list of two points.

If it is equal to 9, we return three coins, 3, 3 and 3.

If it is equal to 10, we return two coins, 5 and 5.

On the other hand, if it is greater, then we do the following.

We first subtract 3 from the amount.

Then we make a recursive call which returns us the set of

points needed to change the amount- 3, right?

So we make a recursive call.

We solve the same permutational problem.

So with this point, we have some subset of coins,

some list of coins that sum up to amount- 3.

So if we add just one single coin with denomination 3

then we have a change for the whole amount, right?

And this is exactly what we do here.

We append 3 to coins, and we return the result in.

Okay, so this is a recursive program, which changes any amount.

And the fact that it changes any amount is guaranteed by the fact that if you get any

number, which is greater than 8.

And you start and you keep subtracting 3 from it,

then at some point, you will reach either 8 or 9 or 10, right?

So for this reason, this algorithm actually proves, this problem proves

that any amount can be changed using coins with denominations 3 and 5.

And it actually proves this constructively.

Meaning that it not only proves that it is possible,

it actually produces the answer for each possible amount.

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