Brain storm

[dmitrits]

А чему стоит учить не самых слабых первокурсников (программирование и Computer Science) в первом семестре на курсе "Основы дискретной математики и математической логики"?

Уточнение: алгоритмам их будут учить много на отдельном курсе. Отдельный курс "математическая логика и теория алгоритмов" будет позже.

Comments

[nikolenko]

В моё время ПОМИ-группу теории графов учили. Собственно, ДВК.

[dmitrits]

Это мне известно. Но это не ответ на мой вопрос :)

[nikolenko]

В том смысле, что мы были самыми слабыми первокурсниками? :)
Ну может быть. :) Но вообще мне моё матмеховское образование очень даже нравится.

[dmitrits]

У вас была другая специальность. Я имел в виду, что я спрашиваю, чему стоит учить, а ты ответил, чему тебя учили. Ок, буду это понимать, как твой вариант ответа, чему стоит учить. Спасибо!

[abreslav]

Мне кажется, что тех первокурсников, которые пойдут в АУ, стоит учить:
* базовым представлениям о множествах и операциях над ними,
* было бы очень здорово научить их строить логические утверждения с кванторами существования и всеобщности, и правильно их отрицать,
* очень базовой комбинаторике (никаких чисел Каталана, лучше они поймут нормально, почему у байта 256 различных значений, и что сумма C(n, k) это 2^n, а также, что 15! это очень много),
* очень простым свойствам графов (базовые представления о связности, планарности и пр), с какими-нибудь наглядными объяснениями из повседневной жизни, зачем это все,
* было бы здорово научить их писать рекуррентные формулы и доказывать что-нибудь по индукции, желательно не про числа, а, скажем, про деревья.

Да, я ставлю на то, что они после школы этого не умеют, и надо учить как будто с нуля.

[dmitrits]

Спасибо!

[rus4]

Я учу комбинаторике математиков в первом семестре (могу прислать материалы) - это немного другое, конечно, потому что логика у них отдельно и теория графов тоже отдельно - но можно использовать, думаю. Для программистов/теоретиков компьютера эти предметы не менее важны, чем для математиков (скорее более), так что скидок по этой части я бы не делал.

[dmitrits]

Федя, спасибо! Пришли, пожалуйста, думаю, что будет полезно.

[rus4]

Послал ссылку на папку в дропбоксе.

[dmitrits]

А лекции по этому предмету есть? Или только задачи по листочкам?

[a_shen]

вот что мы с Володей Подольским попытались составить для "факультета компьютерных наук" ВШЭ - правда, не рассчитывая на сильных студентов.

https://www.dropbox.com/s/hme5d0zgqckdxad/discrete.pdf

[dmitrits]

Спасибо, я тоже не рассчитываю на сильных, я рассчитываю на не самых слабых! А эта программа на сколько часов?

[a_shen]

А хрен его знает - как получится. Самый оптимистический (нереально) вариант, что каждая тема - более или менее одна лекция, реально, конечно, будет сильно больше, и это может растянуться на весь первый курс или даже не уложиться (по плану там 3/4 года, одна лекция и один семинар в неделю). А какие будут комментарии? (Это пока что только план)

[abreslav]

Я какой-то ужасный пессимист, наверное, но мне кажется, что этот курс можно добросовестно преподать (чтобы студенты на экзамене понимали, что говорят, и зачем это надо) в лучшем случае за два года, и то, вряд ли все успеется.

Еще у меня вопрос по компоновке:

Что мотивирует рассказывать сложность алгоритма через разрешающие деревья, кроме доказательства нижней оценки для сортировки? Это ведь довольно неестественная модель, ее трудно связать с реальностью.

[mon_ii]

На мат.обес в 2003-2004 - на первом курсе (одна пара в неделю), кажется - учили "Дискретному анализу" (еще там были студенты с прикладной математики и социологии, а задачи и упражнения были для не самых глупых или хотя бы не ленивых). У Вас ведь был этот курс тоже, наверное, и по нему есть хорошая книжка.