Explore
For Enterprise
Join for Free
Log In

Blättern
Suche
Für Unternehmen
Anmelden
Kostenlose Teilnahme

Integer Linear Combinations

Loading...

Mathematical Thinking in Computer Science

University of California San Diego

4.5 (612 Bewertungen) | 33K Teilnehmer angemeldet

Kurs 1 von 5 in Introduction to Discrete Mathematics for Computer Science Spezialisierung

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

Lehrplan anzeigen

Kompetenzen, die Sie erwerben

Mathematical Induction, Proof Theory, Discrete Mathematics, Mathematical Logic

Bewertungen

4.5 (612 Bewertungen)

5 stars
399 ratings
4 stars
138 ratings
3 stars
51 ratings
2 stars
11 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!

Aus der Unterrichtseinheit

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

Unterrichtet von

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

Skript

Now we have a scientific name for our topic. It's Integer Linear Combinations. But the problem is quite elementary. Let's see. So, imagine a country where there are only two types of coins, the unit is, for example, florin and there are two coins, seven and 13 and there are two people, a buyer and a seller, and each of them has many coins of each type and one of them wants to pay six florin to the other. Is it possible or not? Probably, you will say that we are kidding because it is obvious that six is 13 minus seven so you pay 13 and you get back seven and everything is done. But now, what about paying one florin? Also you can explicitly compute these, you pay twice sevens fourteens and you get 13 back. So it's one. But also you can make a more, I would say, bottom up approach. So, we know that we already can pay six and initially we can pay seven. So you can pay seven and get six back. And this is one. So you somehow capitalize on what you know already. What about two florins? Again, you can make a direct search and find something like this. So you get to it this way. Again you can capitalize on what you know already. Do you see how? You see that it's possible to get one. And so if you can pay one florin, you can do it twice and then you pay two florins. So it's just two times one is two, one is possible. So this works for every integer amount. So any integer amount is payable and in mathematical language one can say that for every integer c this equation, this x and y are just the number of coins and the negative number means that the coins are going that direction. And this equation has integer solution and in other terms, every integer can be an integer linear combination of seven and 13. That is probably a more mathematical way to say the same thing. Now look at another case. Imagine another country which has only 15 and 21 coins. Again, how can we pay six? And again it is trivial. It's 21 minus 15, but now look, can we pay eight or not? What do you think? There is an obstacle. Look at this, all the coins are multiples of three. So whatever you pay or you get is always a multiple of three and eight is not a multiple of three, so no chances for eight and for the same reason, there is no chances to pay one. And three, can we three? What do you think? We know that we can pay six, this we already know. Now see that we can pay nine. And because it's 15 minus six, 15 we know and six we all of us know. Now, we know nine. And so we can capitalize on this and say that we can pay nine and six and get three. So this is called Euclid's algorithm actually, probably you heard about this and we will come to this in number theory again. For now we see that three is payable. And if you want to unfold this you can just compute for each of the number you can compute how you pay, so how you pay nine, how you pay six, how you pay three and then you get this and you can also check directly this is 45 and this is 42. Yeah. So three is payable and for the same reason, any multiple of three is payable. And we can say that this equation has integer solutions if and only if C is a multiple of three. So if C is a multiple, then there are solutions. If C is not a multiple, there is no solution. So in other terms, integer linear combinations of seven and 13 are exactly multiples of three. The general statement of this form says that there are multiple of them. If we have coins of two types, their linear combinations are multiple of the greatest common divisor but this will be a topic of the number theory course.

Durchsuchen Sie unseren Katalog

Melden Sie sich kostenlos an und erhalten Sie individuelle Empfehlungen, Aktualisierungen und Angebote.

Coursera arbeitet mit erstklassigen Universitäten und Organisationen zusammen, um Online-Kurse anzubieten und dadurch universellen Zugriff auf die weltweit beste Ausbildung zu ermöglichen.

© 2019 Coursera Inc. Alle Rechte vorbehalten.

Erhältlich bei Google Play

Coursera
Info
Leitung
Jobs
Katalog
Zertifikate
MasterTrack™-Zertifikate
Abschlüsse
Für Unternehmen
Für Regierungen
For Campus

Community
Learners
Partners
Developers
Beta Testers
Translators

Verbinden
Blog
Facebook
LinkedIn
Twitter
Instagram
Youtube
Tech-Blog

Mehr
Nutzungsbedingungen/AGB
Datenschutz
Hilfe
Barrierefreiheit
Presse
Kontakt
Verzeichnis
Partnerunternehmen