Что достаточно выучить, чтобы получить тройку?

[Munin]

Профессор Снэйп в сообщении #537072 писал(а):

Вы полагаете, что студент, избрав профессию математика (ну, или, по меньшей мере довольно серьёзную подготовку к этой профессии), уже в начале первого курса способен избрать конкретную узкую специальность, которой он после окончания университета будет заниматься, и разделить предметы на "важные" и "неважные"?

Может, он и не способен, но уже это делает :-) И вы можете только помочь ему адекватнее принимать решения.

Профессор Снэйп в сообщении #537072 писал(а):

А на первом курсе студент обязан изучать всё, что ему даютъ

Особенно физвоспитание. Ага, студент будет счастлив от такой максимы.

Профессор Снэйп в сообщении #537072 писал(а):

Правда от ТА напрямую зависит один-единственный курс - матлогика

Я думаю, от неё напрямую зависит ещё изрядный пучок предметов в области программирования, хотя это и не математика, а прикладная область. Не знаю, как там у вас конкретно с этим построено, но уметь программировать - такая же обязательная часть культуры, так что на это тоже можно упирать.

Профессор Снэйп в сообщении #537072 писал(а):

Но на первой лекции слова обычно летят мимо ушей. Увы...

Можно на пятой повторить :-)

[whiterussian]

Munin в сообщении #537039 писал(а):

Tакой вопрос - если он возникает у 80 % учащихся - результат неумения/невозможности дать им более глубокую мотивацию.

Munin
Не получится. На мои лекции - waiting list, чуть ли не единственный у "натуралов" (Natural Sciences). А мои студенты работают в NASA, Lockheed Martin, Los Alamos, при этом в письмах ко мне благодарят за то, что "открыла" им физику и ее прелести...


Профессор Снэйп
Я в своем syllabus заранее расписываю критерии оценки. Так что, когда спрашивают, перечитываю вмeсте с ними - все вопросы отпадают.

[Профессор Снэйп]

Munin в сообщении #537101 писал(а):

Я думаю, от неё напрямую зависит ещё изрядный пучок предметов в области программирования

Нэ напрямую, будем справедливы.

Кстати, я на первой лекции примерно обозначаю содержание читаемого курса относительно к программированию. Обычно это делается путём произнесения следующей последовательности слов:

(Оффтоп)

Вот, казалось бы, теория алгоритмов, должно быть что-то близкое к программированию... Но не заблуждайтесь. Представьте себе, что Вы работаете где-нибудь в Макларене и Ваш болид участвует в гонках формула-1. И Вы переживаете: ну мы же столько конструктивных новшеств напихали в мотор! Наш болид, управляемый самими Шумахером, поедет теперь по трассе со скоростьью 350... нет, 380... нет, даже 400 км./ч. Да, поедет! И тут к ним в аудиторию заходит физик и заявляет: а, сколько не старайтесь, быстрее скорости света не поедет!

Прав этот физик?! На все 100 прав. Имеет ли какую-либо ценность его заявление? Вряд ли, конструирование гоночных болидов рассматривает более приземлённые вопросы...

Так вот: наша теория по отношению к практическому программированию - это что-то вроде физики. Мы будем говорить о невычислимых, но перечислимыъх множествах, однако программировать их перечисление - занятие сугубо непрактичное. Но зато у нас всё будет строго доказано. В-общем, добро пожаловать в мир абстрактной вычислимости! Давайте приступим...

[Munin]

(Оффтоп)

Вынужден слинять из дискуссии. И конкретные проблемы преподавания я не так себе представлял, и содержание курса ТА - чем-то более приближенным к алгебре, скорее. Всем извинения, если кого чем задел.
whiterussian
Более конкретным названием и содержанием вашего курса можно поинтересоваться? [да/нет/в ЛС]

[Профессор Снэйп]

Munin в сообщении #537067 писал(а):

в том числе, и на "Теории автоматов", к которой мы сейчас и приступим.

ТА - это "теория алгоритмов", а не "теория автоматов" Автоматы занимают лишь малую её часть.

[Sonic86]

(Оффтоп)

Оффтопик, но насчет чистой абстрактности ТА, Профессор Снэйп, Вы зря. Там же есть результат о неразрешимости проблемы остановки машины Тьюринга (или это не оттуда?). Этот результат вполне понятен и интересен обычным программистам, для его нестрогого доказательства даже спецтермины не нужны (я его недавно на работе рассказал, один не поверил, а вот когда текст из Вики они увидели, чего-то замолчали ). На эту тему сначала даже интересно поболтать: превосходит ли здесь ИИ ЕИ или нет (т.е. студенты могут тем мотивироваться). Может там и еще чего есть.

[Профессор Снэйп]

Неразрешимость проблемы остановки... Ну да, это один из фактов нашей теории.

Моё отношение к этому такое: каждый грамотный программист сей факт должен знать, однако на практике он ему никогда не понадобится.

Для сугубых программеров есть ещё один интересный факт, проистекающий из абстрактной теории вычислимости. Теорема о неподвижной точке влечёт существование вирусов на любом достаточно сложном вычислительном устройстве. В частности, на одной из лекций я демонстрирую студентам возможность написания вируса на машине Тьюринга

Но этой пары ягодок совершенно недостаточно для нормальной мотивации будущих программеров. К тому же у нас в НГУ есть ФИТ (факультет информационных технологий), там готовят программистов. А у нас факультет механико-математический и мы готовим учёных-математиков. Кстати, на ФИТ конкурс побольше и бывает, что некоторые студенты, не сумев поступить на ФИТ, подают документы на мехмат, мечтая после окончания университета в любом случае работать в IT-сфере. Но далеко не все. Есть и такие, которым интересна математика, а программирование по барабану. Кстати, они обычно воспринимают курс ТА гораздо лучше остальных. Всё-таки это сугубо математический курс, от которого за версту разит чистой математикой.

(Оффтоп)

К сожалению, есть и такие, которым вообще ничего не интересно. И их, увы, очень много.

[Sonic86]

Профессор Снэйп в сообщении #537353 писал(а):

Для сугубых программеров есть ещё один интересный факт, проистекающий из абстрактной теории вычислимости. Теорема о неподвижной точке влечёт существование вирусов на любом достаточно сложном вычислительном устройстве. В частности, на одной из лекций я демонстрирую студентам возможность написания вируса на машине Тьюринга

О! А где об этом можно почитать? А определение вируса дается (в книжке Касперского было довольно мутное описание)? (значит и во мне тоже вирусы есть...)

[Профессор Снэйп]

Ну... вирус имелся в виду в таком примитивном понимании.

Программа, которая воспроизводит свой собственный текст. Плюс, возможно, ещё что-то. То есть ситуация примерно такая: есть программа $P$, которая, получая на вход какие-то данные, на выходе через конечное время выдаёт тексты других программ. И вот для каждой такой $P$ (равномерно по этой $P$) можно написать программу $P_1$, которая будет брать входные данные в том же формате, что и $P$, а на выходе выдавать программу, в которой сначала идёт кусочек, идентичный самой $P_1$, а после него - то, что должна была выдавать $P$ при этих входных данных. Если этот выход потом запускать на другой машине, то тиражирование $P_1$ будет продолжаться. И т. д. Короче, $P_1$ - это тот самый вирус, который заражает другие программы. При этом $P_1$ можно варьировать, добавляя туда разные "вредоносные" команды.

Где это можно прочитать? Да хотя бы здесь на форуме. Сейчас дела, а вечером сяду за комп и спокойно напишу. Там немного и не сложно

PS Как-то раз мне прислали на рецензию статью какого-то французика для буржуйского журнала. Вот он там всю эту банальщину, которую я с лёту объясняю первокурсникам, пытался выдать за какое-то серьёзное научное достижение. Я написал отрицательную рецензию, но статью почему-то всё равно напечатали. Хотя понятно почему. Было несколько независимых рецензентов, как это практикуется в серьёзных изданиях, и у других отзывы были положительные

[Профессор Снэйп]

Sonic86 в сообщении #537357 писал(а):

значит и во мне тоже вирусы есть...

Ага. Вирус гриппа, например. Или вирус иммунодефицита человека

[Sonic86]

Профессор Снэйп в сообщении #537437 писал(а):

Ага. Вирус гриппа, например. Или вирус иммунодефицита человека

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

Профессор Снэйп в сообщении #537375 писал(а):

Программа, которая воспроизводит свой собственный текст. <...> При этом $P_1$ можно варьировать, добавляя туда разные "вредоносные" команды.

Прочел все. Мне понятно
Назовем антивирусом $A$ машину Тьюринга, которая, прочитав входные номер $N$ машины Тьюринга $M$ и входные данные $X$ для $M$, выдает $1$, если $M$, приняв на входе $X$, пишет на ленте свой собственный код, иначе выдает $0$ (вроде правильно все написал).
Существует ли антивирус? Или с ним та же проблема, что и с проблемой остановки? Содержательна ли вообще такая задачка с точки зрения ТА?

[Профессор Снэйп]

Sonic86 в сообщении #537465 писал(а):

Существует ли антивирус? Или с ним та же проблема, что и с проблемой остановки? Содержательна ли вообще такая задачка с точки зрения ТА?

Задача содержательна. Должна быть неразрешима, но точно скажу завтра. Висят над душой, просят освободить компьютер!

[Munin]

(Оффтоп)

Sonic86 в сообщении #537357 писал(а):

значит и во мне тоже вирусы есть...

А вы вычислительное устройство?

[Профессор Снэйп]

Профессор Снэйп в сообщении #537467 писал(а):

Sonic86 в сообщении #537465 писал(а):

Существует ли антивирус? Или с ним та же проблема, что и с проблемой остановки? Содержательна ли вообще такая задачка с точки зрения ТА?

Задача содержательна. Должна быть неразрешима, но точно скажу завтра. Висят над душой, просят освободить компьютер!

Не, ну тут всё довольно просто.

Пусть $\varphi_n(x)$ - функция, вычислимая программой с (гёделевским) кодом $n$. Для простоты назовём программу с кодом $n$ $x$-вирусом, если $\varphi_n(x) = n$.

Задача антивируса заключается в том, чтобы по любой паре $\langle n,x \rangle$ эффективно распознать, является $n$ $x$-вирусом или нет. И тогда универсальный антивирус существует в том и только в том случае, когда множество

$$ V = \{ \langle n,x \rangle : \varphi_n(x) = n \} $$

вычислимо.

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

$$ K = \{ x : \varphi_x(x) \text{ определено} \} $$

$m$-сводится к V ($m$-сводимость в другую сторону имеет место, поскольку $V$ вычислимо перечислимо).

Пусть

$$ \psi(n,k,x) = \begin{cases} n, & k \in K \\ \text{не определено}, & k \not\in K \end{cases} $$

Имеем $\psi(n,k,x) = \varphi_{f(n,k)}(x)$ для некоторой вычислимой всюду определённой функции $f$. По теореме о неподвижной точке (известной также как теорема о рекурсии) существует вычислимая всюду определённая функция $n(k)$, такая что $\varphi_{f(n(k),k)} = \varphi_{n(k)}$ для любого $k \in \mathbb{N}$. Осталось заметить, что функция $k \mapsto \langle n(k), 0 \rangle$ осуществляет $m$-сводимость $K$ к $V$. Что и требовалось доказать.

Короче, задача распознавания вирусов с точностью до вычислимого изоморфизма суть та же проблема остановки

-- Вс фев 12, 2012 18:02:56 --

Munin в сообщении #537702 писал(а):

А вы вычислительное устройство?

Наверное, недаром тест Тьюринга получил такую широкую огласку и является общепринятым текстом на искусственный интеллект.

Рассмотрим человека как некий чёрный ящик, в который можно класть бумажку с написанным натуральным числом и который после ознакомления с бумажкой через конечное время либо выдаёт в ответ своё натуральное число, либо не выдаёт никакого ответа. Конечно, ответ может зависеть от времени ввода исходных данных.

Для простоты будем считать, что работа человеческого мозга в плане отвечания натуральным числом на натуральное число детерминирована. То есть если взять две идентичные копии одного и того же человека (например, размещённые в двух параллельных и полностью идентичных друг другу Вселенных), то в случае, когда этим копиям в одно и то же время дают одно и то же число, они выдают один и тот же ответ (либо ни одна копия не выдаёт ответа).

Для простоты считаем, что время дискретно. Пусть $n(k,t)$ - частичная функция, значение которой равно числу, выдаваемому человеком в ответ на задание ему числа $k$ в момент времени $t$. Тогда, согласно тезису Тьюринга, человек является вычислительным устройством в том и только в том случае, если функция $n(k,t)$ вычислима на машине Тьюринга.

Другими словами, человек считается вычислительным устройством если и только если класс частичных функций, которые он может вычислять (при условии, что его снабдят неограниченным количеством карандашей и бумаги) совпадает с классом частично рекурсивных функций.

Ясно, что любую частично рекурсивную функцию человек может вычислить. Способен ли он вычислить какую-нибудь функцию, не являющуюся частично-рекурсивной? А чёрт его знает? Поскольку мы находимся на научном форуме, для нас естественно, отложив в сторону всяческую мистику (прозрение, общение с Богами и т. п.), считать, что человек - объект физической Вселенной и его поведение описывается физическими законами. Если бы в этих законах отсутсвовал элемент случайности, всё бы было понятно. Однако в современной физике есть квантовая механика, принцип неопределённости и т. д. Типа Бог рулит человеком как марионеткой, полностью задавая его поведения, но при этом Он всё же играет в кости

Так что ответ на вопрос "является ли человек вычислительным устройством" лично для меня неясен. Современная наука не даёт на него ответа

[KVV]

Профессор Снэйп в сообщении #537820 писал(а):

Так что ответ на вопрос "является ли человек вычислительным устройством" лично для меня неясен. Современная наука не даёт на него ответа

Знакомы ли вы с точкой зрения и аргументами Пенроуза по этому вопросу?