August 20th, 2013

moose, transparent

о кванторах (математическое)

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", в последних классах школы или в начальных курсах колледжа? Почему не отложить строгий матанализ на после абстрактной алгебры и общей топологии? Может быть, как раз потому, что эпсилоны-дельты, как ни ненавидят их многие студенты, натаскивают их и доводят до того уровня автоматизма в понимании чередующихся кванторов, без которого им намного тяжелее давались бы эти другие предметы. Возможно, они, эпсилоны-дельты, играют таким образом более важную педагогическую роль, чем собственно строгое объяснение понятий пределов, непрерывности и производной.
moose, transparent

рыцари фейсбука