Proofs?

Loading...

Del curso dictado por University of California San Diego

Mathematical Thinking in Computer Science

262 calificaciones

University of California San Diego

Mathematical Thinking in Computer Science

262 calificaciones

Curso 1 de 5 en SpecializationIntroduction 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.

De la lección

Making Convincing Arguments

Why some arguments are convincing and some are not? What makes an argument convincing? How to establish your argument in such a way that there is no possible room for doubt left? How mathematical thinking can help with this? In this week we will start digging into these questions. We will see how a small remark or a simple observation can turn a seemingly non-trivial question into an obvious one. Through various examples we will observe a parallel between constructing a rigorous argument and mathematical reasoning.

Proof by Example1:50

Impossibility Proof2:34

Impossibility Proof, II and Conclusion3:53

Conoce a los instructores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Vladimir Podolskii
Associate Professor
Computer Science Department

Hello. This is the first part of

our discrete math course and this part is about proofs in general.

And you probably will be surprised why we so care about proofs.

Mathematicians are crazy about them,

but programmers why do they need proofs?

If you write a video game or a search engine,

probably you would not try to prove its correctness.

Still, if you are interested in some more complicated system,

no not complicated but different types of system,

like operating system or cryptographic protocol,

to prove that this operating system will not stop or rather some point,

cryptographic protocol is safe,

it's something worth proving indeed.

And main reason why people don't like proving they don't understand what it is actually.

So, they think that proves something boring, long, meaningless,

you need to learn them to reproduce during the exam,

but it's kind of nonsense.

But it's just a bit understanding.

Proof is not like this.

Proof is an argument,

that should be really convincing for you.

And it's so convincing for you,

that you are even ready to convince other using the same argument.

This is what is a proof in real life.

And in mathematics the tools are different,

but still the proof of something like this.

And to get such a proof you need to understand the problem.

So, this is why the proofs are important.

And last but not least, they're funny.

And it is our course objective so,

we want to learn how to understand proof,

how to invent proof, how to explain proof,

and how to enjoy proof.

This is most important thing.

And we don't assume anything.

Probably you should know what our numbers or some common senses also needed,

but no special things except for curiosity.

If you give a puzzle,

you should immediately stop and think about this puzzle before,

just not wait until we provide the solution,

but just think immediately whether it's true or not or what is the solution so on.

Then it will be much better.

You will much better understand our explanation later.

And let me tell you a story.

There was a Hungarian mathematician Paul Erdős, very famous one.

And he used to say that

mathematicians it's not important whether they believe in God or not,

but what they should really believe is the book.

God has a book that contains all the proofs,

for each statement contains the best possible proof,

clear, nice, and funny.

And you see that some people even try to write a draft of such a book.

And this draft is rather popular,

you see with fifth edition.

So many people enjoy.

This book is probably more difficult.

There are more difficult proofs than we know of course.

But still if you see it you can try and many of them are easy.

And let's start with a puzzle.

So, it's very easy puzzle.

Probably you will wonder why why we ask this,

just but starting slowly.

So, can a chessboard,

here the chessboard eight times eight.

Can it be titled by domino tiles?

Domino tile is a rectangle.

One times two and you can do,

try to put some.

Then somehow, they should not overlap and there shouldn't be no empty space.

That's what is required.

So, can you do it or not?

Explora nuestro catálogo

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

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2018 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play