?

Log in

о кванторах (математическое) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

о кванторах (математическое) [авг. 20, 2013|04:01 am]
Anatoly Vorobey
I 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", в последних классах школы или в начальных курсах колледжа? Почему не отложить строгий матанализ на после абстрактной алгебры и общей топологии? Может быть, как раз потому, что эпсилоны-дельты, как ни ненавидят их многие студенты, натаскивают их и доводят до того уровня автоматизма в понимании чередующихся кванторов, без которого им намного тяжелее давались бы эти другие предметы. Возможно, они, эпсилоны-дельты, играют таким образом более важную педагогическую роль, чем собственно строгое объяснение понятий пределов, непрерывности и производной.
СсылкаОтветить

Comments:
[User Picture]From: vesch9
2013-08-20 03:25 am
В конце курса матанализа наш преподаватель переживал за нас: "Как же вы будете жить без эпсилон больше нуля?!" :)
(Ответить) (Thread)
[User Picture]From: sspr
2013-08-20 03:26 am

Просьба

Можно для общего развития ссылку на литературу по этому вопросу?
(Ответить) (Thread)
[User Picture]From: a_konst
2013-08-20 07:57 am
Я хоть и не автор, но спрошу - по какому вопросу?
Вообще про кванторы? Про пределы и непрерывность в мат-анализе?
Про обучение восприятию длинных цепочек кванторов?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: stf_life
2013-08-20 04:08 am
Да простят меня знатоки, но объясните, обязательно ли самоучкам знать мат. анализ? Возможно он им действительно никогда не пригодится в тех работах, которые встретит. Но и буду благодарен за пример работы, где без мат.. анализа ну никак не выкрутиться.
(Ответить) (Thread)
[User Picture]From: aafin
2013-08-20 04:44 am
Максимум минимум искать понадобится самоучкам?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: buddha239
2013-08-20 05:03 am
Мне коллеги говорили, что в былые годы первокурсников матмеха косил матан, а вот в последнее время - алгебра.
(Ответить) (Thread)
[User Picture]From: a_konst
2013-08-20 07:56 am
О, времена меняются. Наших однокурсников, помнится, тоже больше косил матан. А потом фан.
(Ответить) (Parent) (Thread)
[User Picture]From: xp0m0u
2013-08-20 05:42 am
на радиофаке УПИ всё ещё так и дают с первого курса - матан+линейная алгебра, потом уже остальное
(Ответить) (Thread)
From: ztarlitz
2013-08-20 05:56 am
В Урфу надо сказать этим же все примерно и заканчивается, никакой современной математики там не было и не предвидится, правда и в других вузах дело обстоит не лучше.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: d_ohrenelli
2013-08-20 06:19 am
Как программист самоучка согласен. Кванторы и работу с ними я учил в, прости господи, политехническом институте во время курса высшей математики и с ними на самом деле может быть сложно пока не привыкнешь.
Человек учащий это привыкает не столько к кванторам, сколько к строгости и плотности нотации в общем виде и вообще математическому языку: ему элементарно надо выучить что обозначают эти странные закорючки.

Мой младший брат во время армии взял какой-то начальный математический курс в открытом университете (линейная алгебра, вроде). Он служил в Гивати, в роте Цабар. Так вот, какой-то деятель из роты попросил у него посмотреть учебник и отреагировал на увиденное внутри так: "Эти идиоты не знают английского потому что А и Е пишут наоборот."
(Ответить) (Thread)
From: molnij
2013-08-20 06:21 am
Я в цепочке застрял на "больше n ∃ существует " существует-существует??

А про курсы.. Матан и дифуры (ну и тензоры по хорошему) сильно привязаны например к физике, которая у нас была 1-3 курсах. Отодвигать непрофильный предмет на старшие курсы - спорная затея. Давать физику без матана в универе - вообще время терять.
А кванторы в той же топологии, логике и прочей алгебре вроде встречаются в куда более жестком виде чем в матане, на мой вкус по крайней мере.
(Ответить) (Thread)
[User Picture]From: avva
2013-08-20 06:35 am
Исправил описку, спасибо.
(Ответить) (Parent) (Thread)
[User Picture]From: vodianoj
2013-08-20 06:26 am
Толик, а можешь прислать линк на обьяснение двойных нотаций ∀∃ и ∃∀? Я чего-то их не припомню :-(
Или ты имеешь ввиду, что они не идут так подряд, а просто утверждения типа: "для любого х существуют такие у, что..."
(Ответить) (Thread)
[User Picture]From: avva
2013-08-20 06:34 am
Да, именно это имею в виду, ничего особенного.
(Ответить) (Parent) (Thread)
From: morfizm
2013-08-20 07:12 am
Я не вижу какой-то проблемы в понимании формулировки леммы, но я тут явно biased, т.к. у меня в университете была куча логики, абстрактной алгебры, теорий алгоритмов и формальных спецификаций (хоть и конкретно с этой леммой я не сталкивался).

Но ИМХО, человеку, в целом, сообразительному, должно быть сравнительно легко растолковать, только это займёт не 2 минуты, за которые большинство людей привыкли решать все насущные математические вопросы, а, может, час-другой. Проблема в лени, человеку не хочется разбираться час, но вот на написание поста вроде этого у него час нашёлся.

Но при этом соглашусь, что лемма, правда, слишком заумно сформулирована.
Куда легче сказать, что регулярные языки это те и только те, которые распознаются конечными автоматами, и дальше всё совсем очевидно: у конечного автомата, ясен пень, конечное число состояний (скажем, N), поэтому, как ни крути, совершенно очевидно, что после попадания одно из конечных состояний (не более, чем за N-1 шагов), не позже, чем через ещё N-1 шагов возникнет цикл. Следовательно слово, сооветствующее этому циклу, может повторяться сколько хочешь раз, и всё равно будет матчиться, ЧТД (выбираем p >= N и понеслась...)


Edited at 2013-08-20 07:13 (UTC)
(Ответить) (Thread)
[User Picture]From: plakhov
2013-08-20 11:46 am
Мне кажется, что верно более сильное утверждение. Помимо её (преполагаемой) педагогической ценности, другой пользы от pumping lemma просто нет. Я не знаю примеров языков, нерегулярность которых проще и понятней доказывается с использованием pumping lemma, чем без неё.

Например, классический язык "сбалансированных скобочек". Вот доказательство его нерегулярности без этой леммы: возьмем конечный автомат А, и докажем, что, каким бы он ни был, он этот язык не распознает. В самом деле, найдутся n и m такие, что после (n и после (m автомат А находится в одном и том же состоянии. Это означает, что он ошибется либо на строчке (n)n, либо на строчке (m)n. Доказательство с применением pumping lemma не лучше, кажется, ни в каком смысле. Оно и длиннее, и хуже воспринимается.

Edited at 2013-08-20 11:47 (UTC)
(Ответить) (Parent) (Thread) (Развернуть)
(Удалённый комментарий)
[User Picture]From: d_ohrenelli
2013-08-20 07:18 am
На самом деле изучение матанализа нельзя откладывать из за физики.
И если механику хоть как-то можно попытаться преподать обьясняя матанализ на ходу, что обычно и делается, так как механика начинается в первом семестре,
то уравнения максвелла с их ротором и дивергенцией без матанализа фиг обьяснишь.

На самом деле начала нормальной алгебры можно давать еще в школе. Колумбийская программа unified modern mathematics для школьников тому примером.
(Ответить) (Thread)
From: aerffadf
2013-08-20 08:03 am
Не, не поэтому. А потому что обучают от частного к общему. Ну а чем беднее теория, тем больше в ней требуется перемен кванторов, поэтому понимание закономерно падает.
(Ответить) (Thread)
[User Picture]From: xaxam
2013-08-20 08:11 am
Даже профессиональные математики (за редкими исключениями) с большим трудом понимают высказывания, содержащие три и более квантора.

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

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

Помогают еще "психологические подпорки", когда какие-то объекты объявляются "переменными", какие-то - "параметрами" и т.д.

В любом случае, на понимание сложной конструкции с многими кванторами надо затратить длительное время.
(Ответить) (Thread)
[User Picture]From: the_aaa13
2013-08-20 11:13 am
Ну вот так на ровном месте ввести два лишних определения - это тоже как-то не здорово. По моему проще жить с многоуровневыми высказываниями, чем с объектами, которые нужны только для разбиения конкретного высказывания на две части.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: gul_kiev
2013-08-20 10:28 am
Про кванторы:
(Ответить) (Thread)
[User Picture]From: xgrbml
2013-08-20 07:09 pm
:)))
(Ответить) (Parent) (Thread)
[User Picture]From: cousin_it
2013-08-20 12:11 pm
В тему кванторов: branching quantifiers видели? Я сильно удивился, когда узнал.
(Ответить) (Thread)
[User Picture]From: avva
2013-08-20 02:27 pm
Да, я когда-то подробно вникал в "independence-free logic" Хинтикки, которую он предложил считать более фундаментальной, чем обычная логика первого порядка, но ее семантика, если я правильно помню, определялась только через игры (что возможно и для обычной логики первого порядка, конечно), и это не добавляло уверенности.
(Ответить) (Parent) (Thread)
[User Picture]From: migmit
2013-08-21 01:50 pm
Помнится, нам К.П. Кохась давал задачку "написать определение того, что эпсилон стремится к нулю, когда дельта стремится к нулю".
(Ответить) (Thread)