Discrete Mathematics DSBA2020/2021 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(→‎Colloquium)
 
(не показано 60 промежуточных версии 5 участников)
Строка 1: Строка 1:
 
== Exam ==
 
== Exam ==
  
−
We shall have the final exam at the end of the 3rd Module.
+
We shall have the final exam on April, 2. An attendee of the exam can bring some printed or handwritten materials on paper that may help in solving the given problems. All other sources of information apart from the attendee's brain are '''strictly prohibited'''.
 +
 
 +
Exam starts at 16:00 MSK and takes place in rooms R401 and R405. For distribution of students into rooms please check the exam sheet of [https://docs.google.com/spreadsheets/d/1pRPFATJnzV_wqy3qekYrbQldkBFpDJNfc2ZDaiuB_lA/edit?usp=sharing the table].
 +
 
 +
The [https://drive.google.com/file/d/1SWZ42VEnWSVKPZJuEisljyX2pCIEEDBB/view?usp=sharing list] of students approved for online exam.
 +
 
 +
Year 2020 [https://drive.google.com/file/d/1CiJIWycZwsg4avMP2zTqHa-m_dwvxuCb/view?usp=sharing variant] of the exam with the [https://drive.google.com/file/d/12JagxAhzH8XIvgo1_PLEv08DcCMOot1E/view?usp=sharing solution].
  
 
== Colloquium ==
 
== Colloquium ==
  
 
Please follow [https://drive.google.com/file/d/1DxI0b3g7RpjfN5Womn-BiBUntblMw7pz/view?usp=sharing this link] for the Colloquium Rules and Question List.
 
Please follow [https://drive.google.com/file/d/1DxI0b3g7RpjfN5Womn-BiBUntblMw7pz/view?usp=sharing this link] for the Colloquium Rules and Question List.
 +
 +
Get the colloquium cards for Group #203 by this [https://drive.google.com/file/d/1628OAnEPU5Owa6YYBx-jph-MqO6dvTm5/view?usp=sharing link] (December, 11)
  
 
The Colloquium schedule is as follows:
 
The Colloquium schedule is as follows:
Строка 15: Строка 23:
  
 
The links to the conferences will appear there:
 
The links to the conferences will appear there:
−
* Ivanov Anton.  
+
* [https://meet.edashkov.net/dm-colloq-201-ivanov Ivanov Anton.]
−
* Danilov Boris.  
+
* Danilov Boris.
−
* Karimov Rustam.  
+
* [https://us04web.zoom.us/j/5238400448?pwd=QTBFYUlpQ3dQLy9CcG5VL0hvK01FZz09 Karimov Rustam.]
−
* Ivanova Darya.  
+
* Ivanova Darya.
 
* Trofimova Anastasia.  
 
* Trofimova Anastasia.  
 +
* [https://us02web.zoom.us/j/4777752603?pwd=WnNLVEFjYUhrcEF1dmc0blM1dGxMQT09 Fishman Maxim.]
 +
* [https://meet.edashkov.net/dsba-ed Evgeny Dashkov.]
  
 
The list may update in the future
 
The list may update in the future
Строка 36: Строка 46:
 
* HW 1, Tasks 1--5: September 18
 
* HW 1, Tasks 1--5: September 18
 
* HW 1, Tasks 6--9: September 25
 
* HW 1, Tasks 6--9: September 25
 +
* HW 4, Tasks 1--13: January, 31
 +
* HW 5, Tasks 1--16: March, 1
 +
* HW 6, Tasks 1--10: March, 20
 +
* HW 7, Tasks 1--14: March, 28
  
 
'''For Group 202:'''
 
'''For Group 202:'''
Строка 48: Строка 62:
 
* HW 3, Tasks 1--5: December, 1
 
* HW 3, Tasks 1--5: December, 1
 
* HW 3, Tasks 6--12: December, 15
 
* HW 3, Tasks 6--12: December, 15
 +
* HW 4, Tasks 1--13: January, 31
 +
* HW 5, All tasks: March, 11
 +
* HW 6, All tasks: March, 18
 +
* HW 7, All tasks: March, 28
  
 
'''For Group 203:'''
 
'''For Group 203:'''
Строка 60: Строка 78:
 
* HW 3, Tasks 1--5: December, 1
 
* HW 3, Tasks 1--5: December, 1
 
* HW 3, Tasks 6--12: December, 15
 
* HW 3, Tasks 6--12: December, 15
 +
* HW 4, Tasks 1--13: January, 31
 +
* HW 5, All tasks: March, 11
 +
* HW 6, All tasks: March, 18
 +
* HW 7, All tasks: March, 28
  
 
'''For Group 204:'''
 
'''For Group 204:'''
  
−
* HW 1, Tasks 1--3: September 16
+
*1. HW 1, Tasks 1--3: September 16
−
* HW 1, Tasks 4: September 23
+
*2. HW 1, Tasks 4: September 23
−
* HW 1, Tasks 5-6: September 30
+
*3. HW 1, Tasks 5-6: September 30
−
* HW 1, Tasks 7-9: October 7
+
*4. HW 1, Tasks 7-9: October 7
−
* HW 2, Tasks 1-3: October 14
+
*5. HW 2, Tasks 1-3: October 14
−
* HW 2, Tasks 4-10: October 23
+
*6. HW 2, Tasks 4-10: October 23
−
* HW 2, Tasks 11-15: November 7
+
*7. HW 2, Tasks 11-15: November 7
−
* HW 2, Tasks 16, 17, 21, 22: November 15
+
*8. HW 2, Tasks 16, 17, 21, 22: November 15
−
* HW 2, Tasks 18-20: November 19
+
*9. HW 2, Tasks 18-20: November 19
−
* HW 3, Tasks 1-5: December 5
+
*10. HW 3, Tasks 1-5: December 5
−
* HW 3, Tasks 6-12: December 16
+
*11. HW 3, Tasks 6-12: December 19
 +
*12. HW 4, Tasks 1-9: January 30
 +
*13. HW 4, Tasks 10-13: February 6
 +
*14. HW 5, Tasks 1, 4, 6, 10 : February 16
 +
*15. HW 5, Tasks 2,5,8,9,13: February 20
 +
*16. HW 5, Tasks 7,12: February 27
 +
*17. HW 5, Tasks 3, 11, 14-16: March 6
 +
*18. HW 6: March 20
 +
*19. HW 7: March 28
  
 
== Course Materials ==
 
== Course Materials ==
Строка 98: Строка 128:
 
|-
 
|-
 
  || [https://drive.google.com/file/d/1v1asEu8HdsRB2DLo-dBIwtPuDfG1XdYO/view?usp=sharing cw7] || ---
 
  || [https://drive.google.com/file/d/1v1asEu8HdsRB2DLo-dBIwtPuDfG1XdYO/view?usp=sharing cw7] || ---
 +
|-
 +
|| [https://drive.google.com/file/d/1gyUIRhjx8bvPX8-BdmLgcbUdVgIEhmUF/view?usp=sharing cw8] || [https://drive.google.com/file/d/1sOO1X4vjohqORhe8w7LExL-vU7MNp8ZR/view?usp=sharing hw4]
 +
|-
 +
|| [https://drive.google.com/file/d/1x-WdHokZasGHOolDZ36tovcLg1VSrHfw/view?usp=sharing cw9] || [https://drive.google.com/file/d/1iM3t2NN3bf7Nwbc8uZgPte9wV6IG95Sl/view?usp=sharing hw5]
 +
|-
 +
|| [https://drive.google.com/file/d/1f3a6Ia7KcGMuPWwBo9N9ozTJV6-Wrj7l/view?usp=sharing cw10] || [https://drive.google.com/file/d/19oDtLCiZGFZMXdjg1KWYyyLky4Yj6BtT/view?usp=sharing hw6]
 +
|-
 +
|| [https://drive.google.com/file/d/1Rlloq03Y56MyTeP-dSLC6l7RbVQJ-R1i/view?usp=sharing cw11] || [https://drive.google.com/file/d/1kFHcZANVMMBb-EagzVM1PKv3MxYB61Xz/view?usp=sharing hw7]
 +
|-
 +
|| [https://drive.google.com/file/d/1m_UQ9aXdhsgyDFPCcDIFbS4DXJ4CiNl9/view?usp=sharing cw12] || [https://drive.google.com/file/d/16kzIfd_DxXwkJ9MZH0yJU-9Df4nUBkOD/view?usp=sharing hw8]
 
|}
 
|}
  
Строка 114: Строка 154:
  
 
[https://youtu.be/yntz0HGncAk Lecture 13:] Functional, injective, total, and surjective relations; these classes under conversion and composition; functions and their values; the composition of two functions; function equality criterion; injections, surjections, and bijections.
 
[https://youtu.be/yntz0HGncAk Lecture 13:] Functional, injective, total, and surjective relations; these classes under conversion and composition; functions and their values; the composition of two functions; function equality criterion; injections, surjections, and bijections.
 +
 +
[https://youtu.be/8hdZOKGWOBA Lecture 14:] bijectivity criterion; Galileo's 'paradox'; set equivalence and its first properties; \N^2 is equivalent to \N; Cantor's Theorem.
 +
 +
[https://youtu.be/_JaQV-dc2JU Lecture 15:] Identities for set products and exponentials; indicator functions and subsets.
 +
 +
[https://youtu.be/Y1m_4LG-zwY Lecture 16:] Ordered tuples and finite domain functions; embeddings; Cantor--Schroeder--Bernstein Theorem with applications; Continuum Hypothesis.
 +
 +
[https://youtu.be/XNpRv6ANMH4 Lecture 17:] Finite and infinite sets; the Pigeonhole Principle and related results; the cardinality (size, number of elements) of a finite set.
 +
 +
[https://youtu.be/kpRi1-BT4Pg Lecture 18:] Subsets of a countable set; a countable set is minimal infinite; the Rules of Sum and Product; counting tuples, functions, and subsets for finite sets; a countable set is the least infinite set.
 +
 +
Please find the '''later recordings''' [https://eduhseru-my.sharepoint.com/:f:/g/personal/kroslovtseva_hse_ru/EoaaBvp3DQ9BuXO5g6y19ycBPQ4FvEUSLGcJZ0-D5EjwVg?e=BAbbro here].
  
 
==== Seminars by Evgeny Dashkov ====
 
==== Seminars by Evgeny Dashkov ====
Строка 121: Строка 173:
  
 
[https://youtu.be/99WqhOgnbAo Seminar 13.] Binary relations. Converse relation, composition, set algebra operation. Set image under relation.
 
[https://youtu.be/99WqhOgnbAo Seminar 13.] Binary relations. Converse relation, composition, set algebra operation. Set image under relation.
 +
 +
[https://youtu.be/WJLf8ZihfOg Seminar 14.] Images and pre-images. Funtional, injective, total, and surjective relations.
 +
 +
[https://youtu.be/8AxmVUkEakw Seminar 15.] Functions, injections, surjections, bijections.
 +
 +
[https://youtu.be/nG4O8WwYCL0 Seminar 16.] A continuation of the above; indicator functions.
 +
 +
[https://youtu.be/D_ofaC9dkl8 Seminar 17.] Cantor--Schroeder--Bernstein Theorem.
 +
 +
[https://youtu.be/mXojm_Achc0 Seminar 18.] Cantor--Schroeder--Bernstein Theorem. Countable sets. The Pigeonhole Principle.
 +
 +
Please find the '''later recordings''' [https://eduhseru-my.sharepoint.com/:f:/g/personal/kroslovtseva_hse_ru/EoaaBvp3DQ9BuXO5g6y19ycBPQ4FvEUSLGcJZ0-D5EjwVg?e=BAbbro here].
  
 
==== Miscellaneous ====
 
==== Miscellaneous ====
Строка 179: Строка 243:
 
* TA of group 201: Darya Ivanova. Contact via Telegram https://t.me/ivanovskayaaaaa
 
* TA of group 201: Darya Ivanova. Contact via Telegram https://t.me/ivanovskayaaaaa
 
* TA of group 202: Rustam Karimov. Contact via Telegram https://t.me/dergalaktischekaiser
 
* TA of group 202: Rustam Karimov. Contact via Telegram https://t.me/dergalaktischekaiser
−
* TA of group 203: Maxim Fishman. Contact via Telegram https://t.me/co_ban
+
* TA of group 203: Anton Ivanov. Contact via Telegram https://t.me/Olenek53
−
* TA of group 204: Anton Ivanov. Contact via Telegram https://t.me/Olenek53
+
* TA of group 204: Maxim Fishman. Contact via Telegram https://t.me/co_ban
  
 
== Recommended Reading ==
 
== Recommended Reading ==

Текущая версия на 13:23, 2 апреля 2021

Exam

We shall have the final exam on April, 2. An attendee of the exam can bring some printed or handwritten materials on paper that may help in solving the given problems. All other sources of information apart from the attendee's brain are strictly prohibited.

Exam starts at 16:00 MSK and takes place in rooms R401 and R405. For distribution of students into rooms please check the exam sheet of the table.

The list of students approved for online exam.

Year 2020 variant of the exam with the solution.

Colloquium

Please follow this link for the Colloquium Rules and Question List.

Get the colloquium cards for Group #203 by this link (December, 11)

The Colloquium schedule is as follows:

  • Group #201 - 16:20 MSK, December, 10
  • Group #202 - 18:10 MSK, December, 10
  • Group #203 - 16:20 MSK, December, 11
  • Group #204 - 16:20 MSK, December, 9

The links to the conferences will appear there:

The list may update in the future

Test

We shall have a written test on November, 24. The test is scheduled for 6:10 pm MSK. You are supposed to send you work via a Google-form.

Current Results

You can check your progress up to now via the DM1 Register Online.

Homework Deadlines

For Group 201:

  • HW 1, Tasks 1--5: September 18
  • HW 1, Tasks 6--9: September 25
  • HW 4, Tasks 1--13: January, 31
  • HW 5, Tasks 1--16: March, 1
  • HW 6, Tasks 1--10: March, 20
  • HW 7, Tasks 1--14: March, 28

For Group 202:

  • HW 1, Tasks 1--3: September 15
  • HW 1, Tasks 4--5: September 22
  • HW 1, Tasks 7--9: September 28
  • HW 2, Tasks 1--3: October 13
  • HW 2, Tasks 4--9: October 27
  • HW 2, Tasks 10--12: November, 2
  • HW 2, Tasks 13--22: November, 19
  • HW 3, Tasks 1--5: December, 1
  • HW 3, Tasks 6--12: December, 15
  • HW 4, Tasks 1--13: January, 31
  • HW 5, All tasks: March, 11
  • HW 6, All tasks: March, 18
  • HW 7, All tasks: March, 28

For Group 203:

  • HW 1, Tasks 1--3: September 15
  • HW 1, Tasks 4--5: September 22
  • HW 1, Tasks 7--9: September 28
  • HW 2, Tasks 1--3: October 13
  • HW 2, Tasks 4--9: October 27
  • HW 2, Tasks 10--11: November, 2
  • HW 2, Tasks 12--22: November, 19
  • HW 3, Tasks 1--5: December, 1
  • HW 3, Tasks 6--12: December, 15
  • HW 4, Tasks 1--13: January, 31
  • HW 5, All tasks: March, 11
  • HW 6, All tasks: March, 18
  • HW 7, All tasks: March, 28

For Group 204:

  • 1. HW 1, Tasks 1--3: September 16
  • 2. HW 1, Tasks 4: September 23
  • 3. HW 1, Tasks 5-6: September 30
  • 4. HW 1, Tasks 7-9: October 7
  • 5. HW 2, Tasks 1-3: October 14
  • 6. HW 2, Tasks 4-10: October 23
  • 7. HW 2, Tasks 11-15: November 7
  • 8. HW 2, Tasks 16, 17, 21, 22: November 15
  • 9. HW 2, Tasks 18-20: November 19
  • 10. HW 3, Tasks 1-5: December 5
  • 11. HW 3, Tasks 6-12: December 19
  • 12. HW 4, Tasks 1-9: January 30
  • 13. HW 4, Tasks 10-13: February 6
  • 14. HW 5, Tasks 1, 4, 6, 10 : February 16
  • 15. HW 5, Tasks 2,5,8,9,13: February 20
  • 16. HW 5, Tasks 7,12: February 27
  • 17. HW 5, Tasks 3, 11, 14-16: March 6
  • 18. HW 6: March 20
  • 19. HW 7: March 28

Course Materials

Lecture Notes

You can find some useful materials (including the Lecture Notes) here.

Problem sets

Class Problems Homework Assignments
cw1 hw1
cw2 hw2
cw3 ---
cw4 ---
cw5 ---
cw6 hw3
cw7 ---
cw8 hw4
cw9 hw5
cw10 hw6
cw11 hw7
cw12 hw8

Videos

Lectures

Lecture 8: The Extended Euclidean Algorithm; solving linear Diophantine equations in two variables.

Lecture 9: Solving linear congruence; the Chinese Remainder Theorem; practical solving of simultaneous congruences.

Lecture 10: Sets: an axiomatic approach; elementhood relation; set inclusion and equality; the Axioms of Foundation and Equality; the "Substitution Principle"; set construction principles; grouping a few sets together; singletons; specifying a subset; the empty set; powersets; the union of two sets (and a more general case); the intersection and difference of two sets.

Lecture 11: Expressing inclusion in terms of equality; set algebra identities (with application examples); (Kuratowski's) ordered pair; pair equality criterion; Cartesian product; ordered tuples; Cartesian power.

Lecture 12: Binary relation between two sets; the domain, range, and field of a relations; relation diagram; relation on a set; the identity relation; the converse relation; the converse of the converse and of the union of relations; the composition of two relations; composition associativity; the converse of the composition; the composition with the identity; set image and pre-image under a relation.

Lecture 13: Functional, injective, total, and surjective relations; these classes under conversion and composition; functions and their values; the composition of two functions; function equality criterion; injections, surjections, and bijections.

Lecture 14: bijectivity criterion; Galileo's 'paradox'; set equivalence and its first properties; \N^2 is equivalent to \N; Cantor's Theorem.

Lecture 15: Identities for set products and exponentials; indicator functions and subsets.

Lecture 16: Ordered tuples and finite domain functions; embeddings; Cantor--Schroeder--Bernstein Theorem with applications; Continuum Hypothesis.

Lecture 17: Finite and infinite sets; the Pigeonhole Principle and related results; the cardinality (size, number of elements) of a finite set.

Lecture 18: Subsets of a countable set; a countable set is minimal infinite; the Rules of Sum and Product; counting tuples, functions, and subsets for finite sets; a countable set is the least infinite set.

Please find the later recordings here.

Seminars by Evgeny Dashkov

Seminar 11. Sets.

Seminar 12. Set algebra identities. Cartesian product.

Seminar 13. Binary relations. Converse relation, composition, set algebra operation. Set image under relation.

Seminar 14. Images and pre-images. Funtional, injective, total, and surjective relations.

Seminar 15. Functions, injections, surjections, bijections.

Seminar 16. A continuation of the above; indicator functions.

Seminar 17. Cantor--Schroeder--Bernstein Theorem.

Seminar 18. Cantor--Schroeder--Bernstein Theorem. Countable sets. The Pigeonhole Principle.

Please find the later recordings here.

Miscellaneous

Although we had no regular recording of lectures or seminars until Module 2, a few videos on selected topics are available.

Video 1

An equivalence proof for the Strong Induction, Mathematical Induction and Least Number Principles.

Watch it!

Video 2

The definition of the greatest common divisor (GCD); the uniqueness and existence theorem.

Watch it!

Video 3

A compensatory seminar for Group 201. The main topics are GCD and LCM.

Watch it!

Video 4

A supplementary material partly covered at the extra class with groups 202 and 203 on October, 30. The main topics are common divisors and common multiples, solutions to exercises 4, 5, 7-9 from the classwork sheet #4.

Watch it! and get the whiteboard!

Other Resources

  • We encourage everyone to join Google Classroom for this course: there is a global classroom for everyone and group-specific classrooms. Connect using class codes below:
For all groups Group 201 Group 202 Group 203 Group 204
civetu3 7pmgfzr nf3kg65 36dtkir 76a5te5

Professors

The Lecturer

My name is Evgeny Dashkov. Feel free to contact me via email: edashkov@gmail.com, Telegram: @edashkov, or VK.

Technical Support

My name is Boris Danilov. Please, address me all issues and questions related to distant learning technologies that we use in our course. My contacts: brdanilov@gmail.com, Telegram @brdann .

Seminar Instructors

  • Group 201: Evgeny Dashkov
  • Group 202: Boris Danilov
  • Group 203: Boris Danilov
  • Group 204: Anastasia Trofimova

Teaching Assistants

Recommended Reading

Please notice that The Book for our Course does not exist. The latter is based on many sources.

  1. Anderson J. A., Discrete Mathematics With Combinatorics. Prentice Hall, 2003.
  2. Biggs N. L., Discrete mathematics. 2nd ed., New York; Oxford: Oxford University Press, 2004.
  3. Gavrilov G. P., Sapozhenko A. A. Problems and Exercises in Discrete Mathematics. Kluwer Texts in the Mathematical Sciences 14. Springer, 1996.
  4. Lehman E., Thomson Leighton F., Meyer A. R. Mathematics for Computer Science, 2017.
  5. Lovasz L., Vesztergombi K. Discrete Mathematics. Lecture Notes; Yale University, 1999.
  6. Melnikov O., Sarvanov V., Tyshkevich R., Yemelichev V., Zverovich I. Exercises in Graph Theory. Kluwer Texts in the Mathematical Sciences 19. Springer, 1998.
  7. Rosen K. H. Discrete Mathematics and Its Applications. McGraw-Hill, 1999.
  8. Stein C., Drysdale R. L., Bogart K. Discrete mathematics for computer scientists. Addison-Wesley, 2010.
  9. Vinogradov I. M. Elements of number theory. Dover, 1954.

In Russian

If you understand Russian (by any chance), you will probably benefit from reading the following books.

  1. Виноградов И. М. Основы теории чисел. 9-е изд., М.: Наука, 1981.
  2. Вялый М., Подольский В., Рубцов А., Шварц Д., Шень А. Лекции по дискретной математике.
  3. Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. 3-е изд., М.: ФИЗМАТЛИТ, 2004.
  4. Дашков Е. В. Введение в математическую логику. Множества и отношения. М.: МФТИ, 2019.
  5. Зубков А. М., Севастьянов Б. А., Чистяков В. П. Сборник задач по теории вероятностей. 2-е изд., М.: Наука, 1989.
  6. Мельников О. И. Теория графов в занимательных задачах. 5-е изд., М.: Книжный дом "ЛИБРОКОМ", 2013.
  7. Шень А., Математическая индукция. 5-е изд, М.: МЦНМО, 2016.

Grading System

Intermediate grade-2 = (1/3) test-1 + (1/3) colloquium-2 + (1/3) homework-2.

Cumulative grade-3 = (3/10) test-1 + (3/10) colloquium-2 + (4/10) homework-3.

Final grade-3 = min(10, (7/10) cumulative grade-3 + (3/10) final exam + (1/10) bonus points).

The number in a grade’s name is the number of the module when grading takes place. The grade homework-n is the normalized average grade for the homework in Modules from 1 to n. The Intermediate and Final grades are subject to rounding half up to an integer. All the other grades are reported with the greatest precision available.

Bonus point number is between 0 to 20. Such points may be given for a variety of auxiliary activities.

Источник — «http://wiki.cs.hse.ru/index.php?title=Discrete_Mathematics_DSBA2020/2021&oldid=52723»