Explore
For Enterprise
Join for Free
Log In

Explorar
Buscar
For Enterprise
Inicia Sesión
Únete de forma gratuita

Narrowing the Search

Loading...

Mathematical Thinking in Computer Science

Universidad de California en San Diego

4.5 (650 calificaciones) | 35K estudiantes inscritos

Curso 1 de 5 en Introduction to Discrete Mathematics for Computer Science Programa Especializado

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

Destrezas que aprenderás

Mathematical Induction, Proof Theory, Discrete Mathematics, Mathematical Logic

Revisiones

4.5 (650 calificaciones)

5 stars
426 ratings
4 stars
147 ratings
3 stars
52 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!

De la lección

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.

Magic Squares3:26

Narrowing the Search6:47

Multiplicative Magic Squares5:16

More Puzzles9:21

Integer Linear Combinations5:15

Paths In a Graph4:35

Impartido por:

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

Transcripción

Now, we learn how to narrow the search. Actually there are many combinations, but some clever tricks can condense, delete most of them and restrict our search to some small set. So, let's see how it's done. We're looking for 3×3 magic square. In fact, the truth is that they exist for all and starting from three, three, four, five and so on. It's not so easy to prove actually.But we are now interested only in 3×3 magic square, and what is called brute force search this mean that we should check all the possible positions of this nine numbers, and actually we know how many of them we have. If you don't know, you will know after the combinatorics course, part of this our course. But, there are nine possibilities for the first cell and for each possibility for the first cell there are eight possibility for the second one and so on. And if you multiply all those number you get 300,000. It's not much for a computer, but still still for us it's completely impossible. So, let's try to think how we can narrow the search. The first observation is we can know in advance what this... We know that the sum is in all the rows and columns are the same, but what is the sum? We can find it in a very easy way. So we know that in all the square together we have 45, and this 45 is made of three rows or of three columns. So, each column should have sum one third of 45 so it's 15. Why it's important? Let me show you before going farther. So, now, if for example, we know what is here, then the rest is the term to include. So, we can make a search only for all possibilities to fill this square. And this is much smaller actually, we have only nine, eight, seven, six. So I think it's 120 times smaller. Still it's a large number anyway, so we need more tricks and this is one of the tricks which I showed too early. And the trick is that we can predict what is in the center. So look, we have sum up four lines. This is the one line, this is the second line, third line and fourth line. First we know that if we sum all these numbers along these lines, we get four times the constant, this s, which is the sum of each line and each diagonal. So we have 4S. On the other hand, we can see that everything is counted exactly once, except for the center which is count for four lines, it's count four times. So the center, there is additional to 3×center. So 4S is the total sum which we know is 3S and 3×center. So the center is one third, so this four and three, so the difference is S. And the center is one third of the sum on every line. In our case is five. So, here is the equation and here is the solution in general, and in our case it's five. Good. So we know that we have five here. And this is again, our search space become smaller and smaller. And the next step is to think where we should place one. There is a minimal number one and it should be somewhere. And there are essentially two possibilities, either it's in the corner or it's in the middle of the side. So, this is our question, corner or middle? Now we should consider make a case analysis. So let's imagine one is in the corner, what happens then? Then we know that if this one is six, we have nine here. What do we know about other things? So there is three lines which should have key 15. This line, this line, and this line. So this is 14. So this should be 14 and this should be 14. But then let's look how we can get 14. 14 is 5+9 is this one. And there are other possibilities; this for example, you can get 6+8. You don't have number bigger than nine, so the only thing you can decrease this nine and then you get six here. And the next step is get 7+7, but this is not possible because we cannot use 7 twice. So actually there are only two ways to get 14; 5+9 and 6+8. And we have three positions when the 14 is needed. So we get a contradiction, one cannot be in the corner. This case is closed. Okay. Then, it should be in the middle. Let's put it in the middle for example, in the bottom line. Now, actually there is also symmetry, like we can turn it over this line. So we can assume for example, then on this line we should have 14, and this 14 we know that the only possibility is 8+6. But the question is whether eight here and six here or vice versa. But it's symmetric, so we consider one case. Now everything is determined. If we know we can compute all of the things. So if we have 13, we have 2 and in this lines 11, 4 and there is 12, 3 and 2+8+7. And what is very important which can be predicted, that we have correct sums everywhere, you can check this. And also, all the numbers are different. We can also check this easily by looking in the picture. So, we are lucky and indeed we get a major square 3×3. So we know that our existential statement with the magic square of size 3×3 exists is proven, we have an example it's enough.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. Todos los derechos reservados.

Consíguelo en Google Play

Coursera
Acerca de
Liderazgo
Empleo
Catálogo
Certificados
Certificados MasterTrack™
Grados
For Enterprise
For Government
Para el campus

Comunidad
Learners
Partners
Developers
Beta Testers
Translators

Conectar
Blog
Facebook
LinkedIn
Twitter
Instagram
Youtube
Blog de Tecnología

Más
Términos
Privacidad
Ayuda
Accesibilidad
Prensa
Contacto
Directorio
Afiliados