о кванторах (математическое)
Aug. 20th, 2013 04:01 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaI hate the Pumping Lemma (англ.)
Интересная запись: автор объясняет, почему он не любит лемму о накачке в регулярных языках (ее формальное утверждение включает в себя четыре чередующихся квантора, и это весьма тяжело понять многим студентам), и рассказывает о другом, более мощном и красивом способе доказательства нерегулярности формального языка.
В обсуждении на Hacker News кто-то справедливо заметил, что лемму о накачке следует объяснять, начиная с доказательства, потому что оно практически тривиально и очень интуитивно. Правда, даже если доказательство понятно, многим трудно переварить что-то вроде "∀ регулярного языка L ∃ n > 0, так что ∀ слова длиной больше n ∃ такая его разбивка, что.... (и еще внутри этого: ∀ степени i...)".
Но может быть, подумал я, это как раз является одной из причин, по которым лемма о накачке неизбежно оказывается частью обучения степени Computer Science? Для студента CS она оказывается обычно первым "заумным" с точки зрения логики утверждением, таким, которое требует нормального понимания чередующихся кванторов. А это понимание надо наработать в себе тем или иным образом, надо сквозь него пройти. Более сложный материал в более сложных курсах потом всегда будет принимать это понимание как данное.
Людям, вообще говоря, трудно даются цепочки чередующихся кванторов: утверждения типа "для каждого X сущестует такое Y, что для каждого Z..." Никто не понимает такие утверждения, встретив их впервые, сразу и интуитивно: надо сломать на них мозги, надо как следует продумать их. Даже цепочка длиной 2 уже трудна для неподготовленного человека; студенты-первокурсники часто путают ∀∃ с ∃∀. Многие, пройдя сквозь этот процесс тренировки, забывают о нем потом; цепочки длиной 2-3 кажутся им тривиальными и немедленно доступными любому.
Как раз недавно мне попался типичный пример - на том же форуме HN обсуждали запись в блоге программиста-самоучки (без высшего образования), о том, как понять нотацию O() без математики. Запись, по-моему, была не очень удачная, но меня поразил один комментарий: "да вообще-то это просто. Скажем, время работы O(n) означает, что есть такая константа..." и дальше словами выписано, что такое для функции быть O(n), и заканчивается так: "видите, хоть и математика, но очень просто!". Причем это было написано совершенно без иронии, автор комментария был искренне уверен, что выписанное словами утверждение с чередующимися кванторами будет совершенно прозрачным для любого программиста-самоучки без высшего образования.
Похожий процесс тренировки работы с кванторами происходит, мне кажется, у студентов-математиков (и других) во время первого строгого курса анализа, когда они встречаются с доказательствами с эпсилонами-дельтами. В западных университетах, если я правильно понимаю, "настоящие" математические предметы обычно начинаются со строгого матанализа, и часто одновременно линейной алгебры, а абстрактная алгебра остается на потом. При этом, вообще говоря, необязательно это устраивать именно так: почему бы не начать с линейной алгебры и абстрактной алгебры, скажем, тем более, что студенты обычно уже учили анализ в нестрогом виде, как "calculus", в последних классах школы или в начальных курсах колледжа? Почему не отложить строгий матанализ на после абстрактной алгебры и общей топологии? Может быть, как раз потому, что эпсилоны-дельты, как ни ненавидят их многие студенты, натаскивают их и доводят до того уровня автоматизма в понимании чередующихся кванторов, без которого им намного тяжелее давались бы эти другие предметы. Возможно, они, эпсилоны-дельты, играют таким образом более важную педагогическую роль, чем собственно строгое объяснение понятий пределов, непрерывности и производной.
Интересная запись: автор объясняет, почему он не любит лемму о накачке в регулярных языках (ее формальное утверждение включает в себя четыре чередующихся квантора, и это весьма тяжело понять многим студентам), и рассказывает о другом, более мощном и красивом способе доказательства нерегулярности формального языка.
В обсуждении на Hacker News кто-то справедливо заметил, что лемму о накачке следует объяснять, начиная с доказательства, потому что оно практически тривиально и очень интуитивно. Правда, даже если доказательство понятно, многим трудно переварить что-то вроде "∀ регулярного языка L ∃ n > 0, так что ∀ слова длиной больше n ∃ такая его разбивка, что.... (и еще внутри этого: ∀ степени i...)".
Но может быть, подумал я, это как раз является одной из причин, по которым лемма о накачке неизбежно оказывается частью обучения степени Computer Science? Для студента CS она оказывается обычно первым "заумным" с точки зрения логики утверждением, таким, которое требует нормального понимания чередующихся кванторов. А это понимание надо наработать в себе тем или иным образом, надо сквозь него пройти. Более сложный материал в более сложных курсах потом всегда будет принимать это понимание как данное.
Людям, вообще говоря, трудно даются цепочки чередующихся кванторов: утверждения типа "для каждого X сущестует такое Y, что для каждого Z..." Никто не понимает такие утверждения, встретив их впервые, сразу и интуитивно: надо сломать на них мозги, надо как следует продумать их. Даже цепочка длиной 2 уже трудна для неподготовленного человека; студенты-первокурсники часто путают ∀∃ с ∃∀. Многие, пройдя сквозь этот процесс тренировки, забывают о нем потом; цепочки длиной 2-3 кажутся им тривиальными и немедленно доступными любому.
Как раз недавно мне попался типичный пример - на том же форуме HN обсуждали запись в блоге программиста-самоучки (без высшего образования), о том, как понять нотацию O() без математики. Запись, по-моему, была не очень удачная, но меня поразил один комментарий: "да вообще-то это просто. Скажем, время работы O(n) означает, что есть такая константа..." и дальше словами выписано, что такое для функции быть O(n), и заканчивается так: "видите, хоть и математика, но очень просто!". Причем это было написано совершенно без иронии, автор комментария был искренне уверен, что выписанное словами утверждение с чередующимися кванторами будет совершенно прозрачным для любого программиста-самоучки без высшего образования.
Похожий процесс тренировки работы с кванторами происходит, мне кажется, у студентов-математиков (и других) во время первого строгого курса анализа, когда они встречаются с доказательствами с эпсилонами-дельтами. В западных университетах, если я правильно понимаю, "настоящие" математические предметы обычно начинаются со строгого матанализа, и часто одновременно линейной алгебры, а абстрактная алгебра остается на потом. При этом, вообще говоря, необязательно это устраивать именно так: почему бы не начать с линейной алгебры и абстрактной алгебры, скажем, тем более, что студенты обычно уже учили анализ в нестрогом виде, как "calculus", в последних классах школы или в начальных курсах колледжа? Почему не отложить строгий матанализ на после абстрактной алгебры и общей топологии? Может быть, как раз потому, что эпсилоны-дельты, как ни ненавидят их многие студенты, натаскивают их и доводят до того уровня автоматизма в понимании чередующихся кванторов, без которого им намного тяжелее давались бы эти другие предметы. Возможно, они, эпсилоны-дельты, играют таким образом более важную педагогическую роль, чем собственно строгое объяснение понятий пределов, непрерывности и производной.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2013-08-20 03:25 am (UTC)Просьба
Date: 2013-08-20 03:26 am (UTC)no subject
Date: 2013-08-20 04:08 am (UTC)no subject
Date: 2013-08-20 04:44 am (UTC)no subject
Date: 2013-08-20 05:03 am (UTC)no subject
Date: 2013-08-20 05:42 am (UTC)no subject
Date: 2013-08-20 05:56 am (UTC)no subject
Date: 2013-08-20 06:19 am (UTC)Человек учащий это привыкает не столько к кванторам, сколько к строгости и плотности нотации в общем виде и вообще математическому языку: ему элементарно надо выучить что обозначают эти странные закорючки.
Мой младший брат во время армии взял какой-то начальный математический курс в открытом университете (линейная алгебра, вроде). Он служил в Гивати, в роте Цабар. Так вот, какой-то деятель из роты попросил у него посмотреть учебник и отреагировал на увиденное внутри так: "Эти идиоты не знают английского потому что А и Е пишут наоборот."
no subject
Date: 2013-08-20 06:21 am (UTC)А про курсы.. Матан и дифуры (ну и тензоры по хорошему) сильно привязаны например к физике, которая у нас была 1-3 курсах. Отодвигать непрофильный предмет на старшие курсы - спорная затея. Давать физику без матана в универе - вообще время терять.
А кванторы в той же топологии, логике и прочей алгебре вроде встречаются в куда более жестком виде чем в матане, на мой вкус по крайней мере.
no subject
Date: 2013-08-20 06:26 am (UTC)Или ты имеешь ввиду, что они не идут так подряд, а просто утверждения типа: "для любого х существуют такие у, что..."
no subject
Date: 2013-08-20 06:34 am (UTC)no subject
Date: 2013-08-20 06:35 am (UTC)no subject
Date: 2013-08-20 07:12 am (UTC)Но ИМХО, человеку, в целом, сообразительному, должно быть сравнительно легко растолковать, только это займёт не 2 минуты, за которые большинство людей привыкли решать все насущные математические вопросы, а, может, час-другой. Проблема в лени, человеку не хочется разбираться час, но вот на написание поста вроде этого (http://bosker.wordpress.com/2013/08/18/i-hate-the-pumping-lemma/) у него час нашёлся.
Но при этом соглашусь, что лемма, правда, слишком заумно сформулирована.
Куда легче сказать, что регулярные языки это те и только те, которые распознаются конечными автоматами, и дальше всё совсем очевидно: у конечного автомата, ясен пень, конечное число состояний (скажем, N), поэтому, как ни крути, совершенно очевидно, что после попадания одно из конечных состояний (не более, чем за N-1 шагов), не позже, чем через ещё N-1 шагов возникнет цикл. Следовательно слово, сооветствующее этому циклу, может повторяться сколько хочешь раз, и всё равно будет матчиться, ЧТД (выбираем p >= N и понеслась...)
no subject
Date: 2013-08-20 07:18 am (UTC)И если механику хоть как-то можно попытаться преподать обьясняя матанализ на ходу, что обычно и делается, так как механика начинается в первом семестре,
то уравнения максвелла с их ротором и дивергенцией без матанализа фиг обьяснишь.
На самом деле начала нормальной алгебры можно давать еще в школе. Колумбийская программа unified modern mathematics для школьников тому примером.
no subject
Date: 2013-08-20 07:56 am (UTC)no subject
Date: 2013-08-20 07:57 am (UTC)Вообще про кванторы? Про пределы и непрерывность в мат-анализе?
Про обучение восприятию длинных цепочек кванторов?
no subject
Date: 2013-08-20 08:03 am (UTC)no subject
Date: 2013-08-20 08:11 am (UTC)Более того, появление таких высказываний надо считать большим педагогическим грехом. Есть разные способы препарировать длинные логические конструкции, вводя промежуточные понятия и упражняясь с ними.
Например, обсуждая пресловутые эпсилон-дельты, можно сначала ввести понятие стабилизации числовой последоватьности и поупражняться с ним, привыкнув к тому, что разные последовательности стабилизируются в разное время, потом ввести понятие "приближенной" стабилизации, или эпсилон-стабилизации, после чего уже в один шаг даётся определение сходящейся последовательности как такой, которая эпсилон-стабилизируется при любой наперед заданной точности измерения эпсилон.
Помогают еще "психологические подпорки", когда какие-то объекты объявляются "переменными", какие-то - "параметрами" и т.д.
В любом случае, на понимание сложной конструкции с многими кванторами надо затратить длительное время.
no subject
Date: 2013-08-20 10:28 am (UTC)no subject
Date: 2013-08-20 11:13 am (UTC)no subject
Date: 2013-08-20 11:31 am (UTC)no subject
Date: 2013-08-20 11:46 am (UTC)Например, классический язык "сбалансированных скобочек". Вот доказательство его нерегулярности без этой леммы: возьмем конечный автомат А, и докажем, что, каким бы он ни был, он этот язык не распознает. В самом деле, найдутся n и m такие, что после (n и после (m автомат А находится в одном и том же состоянии. Это означает, что он ошибется либо на строчке (n)n, либо на строчке (m)n. Доказательство с применением pumping lemma не лучше, кажется, ни в каком смысле. Оно и длиннее, и хуже воспринимается.
no subject
Date: 2013-08-20 11:49 am (UTC)Промежуточные определения помогают на первых порах, если их вводить с умом, конечно.
no subject
Date: 2013-08-20 12:11 pm (UTC)да
Date: 2013-08-20 12:47 pm (UTC)