Просмотр исходного текста страницы Adaptation course in Discrete Math (факультатив)


== General Information ==
The main goal of the Discrete Mathematics Adaptation Course is to help students keep up with the course curriculum by discussing the most important and challenging topics in detail. The second very important goal of the course is to teach students to work competently with mathematical definitions and proofs, correctly logically build solutions to problems and prove statements. The topics of the course are coordinated with the "basic" course of the DSBA and SE program, but its study will also be useful for the direction of AMI. The approximate order of topics is sets and logic, functions and relations, the beginning of number theory, combinatorics, graphs, the foundations of probability theory, generating functions.

== Schedule ==

The classes are organised on Saturdays at 16:20.

== Course materials ==

[https://t.me/+113aheknlsxmYzVi Chat in Telegram]

'''First semester'''

{| class="wikitable"
|-
! Date !! Topic !! Problem Set !! Class note !! Video
|-
 || 21.09.22 || Statements, connectives, quantifiers || [https://drive.google.com/file/d/1kbtRp8c79zE2AspfVb4ZfGZLJRy9Z5j2/view?usp=drivesdk Problem Set 1]|| -  ||
|- 
|| 28.09.22 || Validity of statements, types of proof|| [https://drive.google.com/file/d/1Q2OlmVzXf4P0ocd3eBet4ktoJ1h1DZyn/view?usp=sharing Problem Set 2] || [https://drive.google.com/file/d/11pdljFmpW57o5OqBH40YwioTW_Ebs_gK/view?usp=sharing Solutions] || -
|- 
|| 7.10.22 || Three types of mathematical induction || [https://drive.google.com/file/d/14h2jy4W7KgxBffxE8TKh_13rSG3Wy_Ll/view?usp=sharing Problem Set 3] ||[https://drive.google.com/file/d/1yFnH5QBNxM-1ajoA5y7w9wV_31XeBwWp/view?usp=sharing Solutions] || [https://youtu.be/nljNhVjlnXg Video 3]
|- 
|| 14.10.22 || Proofs with induction || [https://drive.google.com/file/d/13vsHkpBV8riwyKOTCh1v1heuAqf0L9nK/view?usp=sharing Problem Set 4] ||[https://drive.google.com/file/d/1PZD-YWikatG9jCbcc1r_Eo5t0y-kdcpj/view?usp=sharing Solutions] || -
|- 
|| 21.10.22 || Divisibility. Calculation of remainders. Direct proofs. || [https://drive.google.com/file/d/1rHfC1WRv4IB8kNRMynVWv0C26PXGi137/view?usp=sharing Problem Set 5] ||[https://drive.google.com/file/d/1CvWAD5pDmMB8JFWSFNxOrrT7-Jfp_0Wd/view?usp=sharing Solutions] || 
[https://youtu.be/-OIYkDOkLyk Video 5]
|- 
|| 11.11.22 || Great commod divider, the main thorem of arithmetic, direct proofs. || [https://drive.google.com/file/d/1CrF9W2rXFiTMKFoxZO-PJDmhYAx6Ql84/view?usp=share_link Problem Set 6] ||[https://drive.google.com/file/d/1TWSgbLrRtZWRrbneebExE4BPoDzLU4-b/view?usp=share_link Solutions] || 
[https://youtu.be/_2RRlq21gqM Video 6]
|- 
|| 19.11.22 || Fermat's Little theorem, inverse elements in groups $\mathbb{Z}_p$, congruences. || [https://drive.google.com/file/d/1IF6rqwLN0Bq8n07mxQ3CAmoMfWplJ3OR/view?usp=share_link Problem Set 7] ||[https://drive.google.com/file/d/1FZevxpUjcPrrtCbxHn-HRh1odDamJqlq/view?usp=share_link Solutions] || 
[https://youtu.be/peuzIDzh1bE Video 7]
|- 
|| 25.11.22 || Fermat's Little theorem, inverse elements in groups $\mathbb{Z}_p$, congruences. || [https://drive.google.com/file/d/1CYGJ7B5d426ChuZBozzsLKwMVZeVPgQJ/view?usp=share_link Problem Set 8] ||[https://drive.google.com/file/d/1_PCu2dDhIgN7uE1ijLGLH1USapPskGWH/view?usp=share_link Solutions] || 
[ -]
|- 
|| 2.12.22 || Application of Euler's theorem and Euclidean algorithm, cryptography || [https://drive.google.com/file/d/1Oq3grvUbG-yBBbrHqhK_4Ylz4Io-D1Lw/view?usp=share_link Problem Set 9] ||[https://drive.google.com/file/d/1BFDh6-6KVmb65w7qDEQprP6BYUMUW6AQ/view?usp=share_link Solutions] || 
[https://youtu.be/HPpI7VpHrWY Video 9]
|- 
|| 9.12.22 || Sets, direct proofs of set identities || [https://drive.google.com/file/d/1C6I_cviJwznCLZ5BKtxUtlUrjpp4Kegw/view?usp=share_link Problem Set 10] ||[https://drive.google.com/file/d/179jjcjhdU0LschqhPEFMPJylunwRiofA/view?usp=share_link Solutions] || [https://youtu.be/7Gk3JxRpeWU Video 10]
|- 
|| 16.12.22 || Operations with sets, cardinality and power set || [https://drive.google.com/file/d/1D9A7QTq-7dPN8Xz_jQhsYIknX8cukhZD/view?usp=share_link Problem Set 11] ||[https://drive.google.com/file/d/1B1snvrzqMgUMDEEQqOHVzomfWVwf2t07/view?usp=share_link Solutions] || 
[https://youtu.be/TK4BNYF4vEU Video 11]
|- 
|| 21.01.23 || Sets once again, proofs that a statement is wrong|| [https://drive.google.com/file/d/15hSnMr1jVCSJ6boGK5KuEUldlx3-8Pvv/view?usp=share_link Problem Set 12] ||[https://drive.google.com/file/d/1PDsR6DjO_K9-XfoqprA0UsYWh-2fSb8T/view?usp=share_link Solutions] || 
[https://youtu.be/2J8qDgwpivU Video 12]
|- 
|| 28.01.23 || Relations, main definitions || [https://drive.google.com/file/d/1IJAqHsXCQaSFlzZFaH5TpfnNdibKAzen/view?usp=share_link Problem Set 13] ||[https://drive.google.com/file/d/188uRSv9ALwy4IsPreEbS8J61PDMw9uVw/view?usp=share_link Solutions] || 
[ Video 13]
|- 
|| 11.02.23 || Relations, proofs of inclisions and construction of counterexamples. || [https://drive.google.com/file/d/1BL5L3ZneQh61HWjLcok0iDMIR3IMjFbA/view?usp=share_link Problem Set 14] ||[https://drive.google.com/file/d/1aC59jPGQT3e_RBrbar_Z1hgdabfqojG0/view?usp=share_link Solutions] || 
[https://youtu.be/KrKWF381vtc Video 14]
|- 
|| 17.02.23 || Functions and their properties. || [https://drive.google.com/file/d/1ONrAr-5rX6T_2vGTPJ63AJmanSh_H-bP/view?usp=share_link Problem Set 15] ||[Solutions] || 
[ Video 15]
|}

[https://drive.google.com/file/d/163PgGw33FTt3PUVdVBYCjIHluftfZVol/view?usp=sharing Last year retake]

[https://drive.google.com/file/d/1bljTOb3x0kvYy7cslTOC4B3StYOHi3CX/view Last year test 1]

== Homeworks ==
[https://forms.gle/TAgL2eUkhSyhZKLD9 Homework 1 (Logics)], Deadline 31st October

[https://forms.gle/pVA1a8xbeP54RqAQ7 Homework 2 (Induction)], Deadline 31st November, better to complete before the November Test

Hint🦉 in Problem 5: Do not try to prove P(n) out of P(n-1). Assume that P(1), P(2), ...P(n-1) are all true. For proving P(n) say: lets find the biggest Fibonacci number F_i<n. Then, n = F_i + k. For the k apply your assumption😉😉 

[https://drive.google.com/file/d/1k8SKmN9J_DdSs8ibP_9b52n8LxiPf_8U/view?usp=share_link Homework 3]: write down solutions to exam 1 in a perfect manner (like you you are going to print a book of your solutions), Deadline 25th November. You can pass them written or orally on Fridays evenings. Do it if you want to have MAX in the retake(if so happened) and in the exam in the end of the course.

[https://forms.gle/DQUEyuh1vuXgdtr6A Homework 4 (Number theory)], Deadline with bonus 29th December

==Semester 1 ==

[https://docs.google.com/spreadsheets/d/1YHhkk8TCm_qPF0tXyGe7rc-DzubrgSESZUoW6fHMLZA/edit?usp=sharing Current grades and comments]

== References ==

1. [http://discrete.openmathbooks.org/dmoi3.html Discrete Mathematics (An Open Introduction) by Oscar Levin,] p. 197 Logics. Many simple problems with solution to feel the topic.

2. [https://drive.google.com/file/d/1mmNLLQ0--EDihGNRKwSyXLOA1KL7A0lD/view?usp=sharing Lecture notes by Evgeny Dashkov]
 
PLUS: there is a [https://youtube.com/playlist?list=PLEwK9wdS5g0pk-1YWDc3hezRt_rNpQDf8 folder with records on wikipage ]

3. [http://www.mccme.ru/free-books/shen/shen-induction.pdf Шень А., Математическая индукция. 5-е изд, М.: МЦНМО, 2016.] Many problems to work with three different versions of induction.

== Grading and Results ==

'''Final grade''' = Average(HWs)+ Bonus points

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


<!---
[Таблица результатов]

--->