))Это краткий рассказ о восьмидесятых годах прошлого столетия обычной молодой девушки-москвички.
В 2007 году, в конце августа, мне захотелось вспомнить, как у меня протекали прошедшие 80-90-е гг. Это время пришлось на мою юность и молодость. Настолько многое изменилось сейчас, что пока я ещё помню какие-то вещи, постараюсь восстановить в памяти ушедшее.
До учёбы в университете каких-либо изменений было не так много (хотя, конечно, можно вспомнить и подробнее: например, в 1980 г. в Москве летом проходила Олимпиада, и наш класс 8 "А", м. б., часть учеников, по обмену, как это происходило в предыдущие годы, если бы не Олимпиада, поехал бы в Чехословакию. Но вместо этой необычной поездки нас долго агитировали, даже стращая тем, что не возьмут в следующий 9-й класс, поехать в трудовой лагерь в Ворошиловградскую область. В тех краях мы пробыли, как сейчас помню, с 8 июля по 15 августа. Конечно, в целом, там было неизмеримо скучно. Какую-то часть времени мы проводили в полях, собирая огурцы (это точно), наверное, прореживали или окучивали свёклу. Но все-таки наша работа была организована не слишком хорошо. И мне было там довольно тоскливо, я каждый день думала о том, когда же мы поедем обратно. Прежде мне не доводилось бывать в степной зоне, только в Подмосковье и два раза в Абхазии, где мне, конечно, понравилось, но, видимо, климат оказался не совсем подходящим... А вот такой сухой горячий воздух с горьким запахом полыни, ковыля, скудной зеленью, бескрайними ровными с небольшими ложбинками просторами пришёлся мне по душе.
Следующие два года я с удовольствием проучилась в вечерней ФМШ при МАИ, где по окончании получила в числе четырёх человек красный диплом. В июле, благодаря приятелю, я попробовала сдать экзамены на мех/мат и, к удивлению, прошла, набрав полупроходной балл - 19,5.
Первый семестр был для меня крайне тяжёлым, все-таки многие готовились к учёбе в МГУ заранее, да и порядочное количество человек часть читаемого курса уже знало, учась в спецшколах или классах. Коллоквиум по высшей алгебре мне пришлось сдавать В. Н. Латышеву, нашему лектору и семинаристу, четыре раза, даже удивительно, что я его (коллоквиум) и экзамен Латышеву же каким-то образом сдала. До сих пор мне трудно понять образ его мышления, но для меня, наверное, было в чем-то полезно так долго сдавать алгебру. Некоторые вещи, казавшиеся мне очевидными, я очень быстро "проскакивала", в чем состоит сложность и суть некоторых доказательств я не улавливала, возможно, "непрозрачные", а "надуманные" доказательства бессознательно мной отвергались, но постепенно я поняла, что от меня хотят, и некоторая искусственная логика "прояснилась" для меня. Математический анализ был гораздо сложнее, на мой взгляд. К сдаче экзамена я осознала, что не понимаю ничего, даже списывание билета мне бы не помогло, понимала и знала я ровно один билет № 2 - "Множества". Именно его я вытянула, что меня и спасло... Через год, к весенней сессии, я уже немного осмыслила и разобралась с языком "epsilon - delta" и т. д.
После первого курса мы втроём с мамой и братом поехали в Хаапсалу (Эстония). Август был очень тёплым, даже жарким. Когда мы пересели из поезда в электричку, мне показалось, что мы в другой стране, настолько чистота и приветливость лиц поразили меня. Конечно, такая поездка была для нас достаточно дорогим удовольствием, и пришлось, особенно к концу месяца, экономить. Помню вкуснейшие рыбные салаты из копчёной трески с луком и картофелем! Такой трески я, пожалуй, раньше и не ела, хотя в 70-80-е гг. хорошая жареная треска у нас дома часто готовилась. Сейчас свежей трески давно нет. Да и рыба стала дорогой, а ещё недавно в начале 2000-х гг. можно было купить относительно недорогую свежезасоленную форель. Действительно, даже хорошо пропечённый и вкусный хлеб можно купить у нас на даче под Клином. Он долго не черствеет и вкусен. (Честно говоря, в этом году качество хлеба, мяса и молока заметно ухудшились.) Много продуктов с добавками для длительного хранения. Что хорошо - так это то, что много такой еды не съешь, хотя нельзя сказать. что она дёшева.
Начало второго курса было довольно печальным. Ведущий семинарских занятий по матанализу, старик 86 лет, практически на глазах терял память и разум. Ребята из нашей группы (точно помню, что Олег Волков, м. б., Сергей Березнер и Саша Исаев) ходили в учебную часть с просьбой заменить преподавателя. Но там отказали. Я считаю, что правильно сделали. Все эти задачи можно было и самим вполне разобрать при желании. На каком-то занятии (возможно, на последнем) человеку стало совсем плохо, я думаю, что произошёл инсульт, он побледнел, запнулся, несколько раз попробовал закончить фразу, но это никак не удавалось. Затем он просто сел и, кажется, занятие на этом закончилось. В октябре он умер. Его похороны (а это были первые похороны, на которых я присутствовала) произвели на меня тягостное впечатление. Он был куратором нашей группы, и, видимо, ещё поэтому (в других группах он, кажется, не вёл занятий) всей группе велено было участвовать в похоронах. Кроме начальника курса и нас, присутствовала ещё его семья: жена и слабоумный сын. Мероприятие происходило в трёхзальном корпусе. Все, как всегда, было организовано бестолково, медленно и мучительно. Были ли мы на кладбище - я даже не помню. (Наверное, в крематории.)
Новым семинаристом был назначен Чубариков В. Н. (тогда зам. декана Лупанова, в наст. вр. и. о. декана. Замечу, что Латышев стал впоследствии зав. каф. алгебры, куда перевёлся Дима. Пути Господни неисповедимы!) Не могу сказать, чтобы (для меня, по крайней мере) семинары стали полезнее. Чубариков, в основном, апеллировал к достаточно небольшой группе подготовленных ребят, так что в целом мне было непонятно, о чем идёт речь, к тому же, говорил он довольно-таки тихо.
Хорошо помню (это произошло примерно через месяц) день смерти Брежнева. Какая-то сотрудница со слезами на глазах в лифте сообщила: "Умер Леонид Ильич. Какое горе!" К сожалению, я не почувствовала, какое это горе, и опустила глаза. Уже не помню, почему я взяла билеты в т-р Маяковского на "Банкрота" (м. б., посоветовали?) и именно на этот день. Посмотреть комедию, разумеется, не удалось, спектакль заменили "Бегом". Играли Немоляева и Ромашин, Лазарев, Стриженов (?). Спектакль был хорошим, но мрачным (вернее, таково содержание пьесы), да и время нач. 80-х гг. я воспринимаю как мрачноватое, и мне хотелось, возможно, посмотреть какую-нибудь комедию, но не пришлось). Хорошо помню, как мы возвращались с братом из театра до станции "Площадь Свердлова". Улицы совершенно пустынные, никого в центр города не пускают, только по билетам.
В зимние каникулы мы с подругой Кариной Гурарий поехали в Ленинград, где остановились у моего двоюродного деда, брата бабушки, и его жены тёти Лили. Эта поездка запомнилась мне посещением в БДТ спектакля "Пиквикский клуб" (Басилашвили, Трофимов и др.) Благодаря настойчивости Карининой подруги нам выдали контрамарки для студентов, и мы сидели наверху на ступенях. Это были поистине блестящие: как режиссура, так и актёрский ансамбль! Больше подобных постановок я не помню (хотя, м. б., "Тартюф" МХАТа).
Летом мы с мамой поехали по курсовке, которую достала бабушка, в Сукко, под Анапой. Как выяснилось, там же был лагерь от МГУ, и я встретила свою однокурсницу Веронику Шелехову и даже одногруппника Рыжова, который снимал... за 1 рубль в сутки какой-то сарай и ел (бесплатно) в нашей столовой, поскольку наличие талонов проверялось лишь в начале заезда новой партии отдыхающих. По окончании путёвки я договорилась со своим бывшим одноклассником погостить у его отца в Анапе, а затем в п. Утриш на биостанции.
В начале третьего курса, как это было принято, наш курс поехал на картошку более, чем на месяц. Для меня это было достаточно тяжёлым трудом, да и бытовые условия были явно не для меня. Шли дожди, и в комнате, где мы проживали, было неимоверно холодно. Спали в куртках и варежках. Все происходило, как во сне. Где-то 13 сентября (помню, холодное ясное утро на поле) произошёл какой-то перелом, пришло "второе дыхание". Через некоторое время я даже поправилась: кормили там не очень хорошо, но молочных продуктов было вволю - свежие творог и сметана, молоко. На свежем воздухе всё усваивалось отлично.
С Мариной на картошке
Вспоминаю поездку в Черноголовку к Карине. Там мне запомнилось самостоятельное вождение а/м её подруги (или отца подруги) по маленьким улочкам посёлка. В следующий раз я побываю там через год, в феврале, уже на свадьбе Карины и её мужа Миши Фредгейма. Но это ещё впереди.
Новый 1983-й год Карина пригласила меня встретить с её тогдашними друзьями на Поварской или где-то поблизости. Помню, что это был старинный одноэтажный особняк с двойными дверьми, но где он расположен и сохранился ли, я не знаю.
Сама же Карина с мужем и дочкою осенью 1992 г. уехала в Австралию к дяде, зав. каф. в местном университете. Последний раз я видела её в квартире, которую они снимали рядом с м. "Щербаковская". С осени 1995 г. я буду часто ездить сюда какое-то время.
С кем я общалась первые два года в университете? Помню одногруппницу Ирину, москвичку, ушедшую после первого семестра dots Всего москвичей было треть группы, такое же количество составляли и девушки. Так было примерно для всего курса. Какое-то время я дружила с Надей Чупахиной, очень способной и честолюбивой студенткой, родом из Кисловодска, с очень непростым характером. (На старших курсах она перешла или поступила в ИНЯЗ и стала переводчиком.) Благодаря ей мы побывали зимой в бассейне "Москва". Довольно необычное ощущение! Также я много бывала и даже готовилась к экзаменам в общежитии ФДС-6.
Но уже на втором курсе, слушая лекции на общем потоке, познакомилась и вскоре подружилась с Мариной Ивановой (начав учиться с ней в одной группе после разделения по кафедрам). Третий курс был довольно насыщенным в учебном плане, к началу каникул я очень устала после сдачи пяти экзаменов. А предстоял (единственный в моей жизни!) поход в горы на Западный Кавказ! Несмотря на то, что в походе было много необычных впечатлений: долина рододендронов на закате дня, куда мы спустились в полном тумане, источающих неземной запах; катание на настоящей лошади в серебряной сбруе, обученной своим хозяином подгибать передние ноги для удобства посадки, в Карачаево-Черкессии в конце дня, когда я просто свалилась без сил от непомерной усталости и постоянной боли в спине (видимо, ныло сердце от нагрузки), в целом, такой активный отдых оказался мне не под силу. Когда мы вернулись домой и интенсивной нагрузки уже не было, через неделю у меня страшно отекли ноги, хотя никакой боли я не чувствовала. Пришедший к маме врач сказал, что это не выдерживает сердце, поэтому лучше мне в походы не ходить.
 |
 |
| С Мариной в Подольском карьере. Подготовка к походу | На лошади |
Примерно через 2-3 недели в августе я снова поехала в то место, где закончился наш поход: в лагерь "Солнечный" от МГУ, расположенный недалеко от Пицунды, во втором ущелье. В поезде мы ехали вместе с Киликовской (а м.б., уже Колосовой) Катей, моей однокурсницей, с которой познакомились ещё в небольшом подмосковном походе в начале первого курса, устроенном для знакомства студентов. Затем мы вновь увиделись в турклубе, поскольку поначалу она также собиралась принять участие в горном походе. В лагере я познакомилась и с однокурсницей Наташей Гринберг, очень необычным человеком, участницей международной олимпиады.
Годы учения подходили к концу. Для меня было очевидно, что надо зарабатывать (об аспирантуре поэтому я и не думала - мама явно жаловалась на нехватку денег). Знакомый мамы Саша Андроников звал к себе в РТИ - как и во многих других закрытых институтах, там предполагалось большое количество командировок, мне этого не очень хотелось, поэтому в день встречи с представителями различных НИИ я воспользовалась тем, что в определённой аудитории был человек не из РТИ, а из ЦНИИ "Комета", куда я впоследствии и поступила на работу. Пребывание там, несмотря на некоторый, может быть, и полезный опыт, было крайне тягостным, таким, что я даже (не только из-за этого, но, безусловно, в первую очередь) провела в институте не 3 положенных по распределению года, а четыре с лишним, не имея никаких моральных и физических сил искать чего-то другого.
В первый год работы в "Комете" ежедневные приходы на место службы мне так надоели, что по прошествии 11 месяцев я написала заявление на отпуск с 1 сентября 1987 года и по "горящей" курсовке уехала на 24 дня в Палангу. Летом 1988 г. я съездила на 2 недели в Геленджик. В Геленджике мне не очень понравилось, в отличие от Прибалтики, но там мне удалось применить некие способности. Дело в том, что один из членов нашей компании опоздал на самолёт и прилетел позже. Мы не стали его ждать, занявшись поисками жилья. Как его встретить - было непонятно. Конечно, можно было оставить объявление на остановке, но его могли снять или оно не бросилось бы в глаза. Сидеть и ждать на автостанции было утомительно. Отдохнув после дороги, я вышла немного прогуляться, но с полуосознанным (нарочно, чтобы сознание не мешало) намерением "притянуть" оставшегося члена группы. И так, медитативно шагая по почти пустынным улицам города, я наконец-то увидела Игоря. Не могу сказать, чтобы это не отняло у меня сил. Все же я пыталась на него настроиться, чтобы встретить. Впоследствии я замечала, что или заранее знала, что кого-то увижу в этот день, или, если хотела увидеть, то могла встретиться, например, в таком большом здании, как МГУ. Но в тот вечер это было достаточно удивительным для меня, и я почувствовала, что эта встреча не была случайной. Как будто кто-то привёл меня.
Перестройка не особенно задела меня, хотя 1987-88 учебный год по приглашению Марины я посещала домашние уроки французского Насти Тюриной, нашей однокурсницы. Летом Марина вышла замуж, Настя чуть позже. Наша семья получила квартиру в том же доме, и часть времени я проводила там. Летом 1988 года в последний день занятий французским, который проходил у Лены Красильщик на "Рязанском проспекте", я осталась у неё ночевать, поскольку моя работа находилась недалеко на "Пролетарской". Сама Лена собиралась вскоре уехать в Израиль и заняться юридической деятельностью. Рассматривая на полках книги и какие-то листы, выбрав наугад ворох бумаг, спросила, что это? Оказалось, записи лекций по астрологии её знакомой Татьяны Романовой. С марта 1989 г. я начала слушать её лекции.
Летом того же года я съездила на несколько дней в Тверскую область, где снимали или купили дом родители Светы Перепёлкиной (знакомой Леонида Костюкова, оказавшего на меня значительное литературное влияние. Он был центром компании, небольшое участие в которой я принимала на старших курсах и позднее.) Места эти, действительно, заповедные. Деревня, кажется, называлась Узмень. Поездом я доехала до ст. Боровичи, где меня встречал на своём "Запорожце" Володя Борисенко. Дом находился где-то на окраине деревни, да и деревня представляла собой несколько домов, м. б., и брошенных. Рядом в малиннике мы обнаружили следы медведя. Практически мы жили в глухом лесу совершенно одни. Мне это напомнило "Зеркало" Тарковского. Полное уединение от всего цивилизованного мира.
Осенью я продолжила занятия астрологией, у меня появился новый круг общения. Где-то с 1987-88 гг. я стала выписывать много журналов и слишком много читать. Думаю, в основном, это послужило причиной сильного переутомления, поскольку, как я планировала ранее, искать новую работу у меня не было никаких сил. Вернее, не совсем так. Кое-что по случаю мне было предложено, но это показалось мне не слишком подходящим. Летом того же 1989 г. я по совету однокурсника и, как оказалось, сотрудника по институту (работавшему, правда, в другом отделе, НИО-47, а я - в НИО-35), принимала некоторое время по выходным участие в восстановлении храма Сергия Радонежского в Конькове. (Удивительно, но как я недавно узнала, в этих работах участвовал и мой теперешний сотрудник по институту, видимо, позднее.) Там я познакомилась с группой (вернее, групп и группировок там было немало), если и не национал-патриотов, то что-то в этом роде. Время было бурным, во всю шла перестройка. Помню, как я впервые увидела листки "Хроники текущих событий", бойко распространяли на Арбате какие-то материалы: о сионистах, царской семье, неизвестные факты времён революции. Позднее я побывала на одном мероприятии, где, в частности, выступал Шафаревич со своими идеями, изложенными в его "Русофобии". Разумеется, огромное количество людей, поддерживающих, скажем, достаточно спорные вещи, где-то в глубине души меня поразило. В глубине души - поскольку обдумывать происходящие события, переваривать и осмысливать каждодневную информацию было совершенно некогда. Постоянно что-то происходило, на работе обсуждали появляющиеся статьи в журналах, газетах, передачи по ТВ. Все бурлило и пенилось. Некоторые фигуры, казавшиеся одиозными, могли спокойно пройти мимо тебя, как во сне. Хорошо помню одетого в шинель сторонника или противника Васильева известного национал-патриота N, показавшегося мне каким-то Хлудовым из "Бега". Что там лекции по уфологии Ажажи в "Комете"! Открывались тайники КГБ! Казалось, что живёшь на другой планете. Но все же политика никогда меня к себе особенно не притягивала. И, по большому счёту, общественная жизнь в целом. Тем не менее, я помню концерт БГ, состоявшийся в нашем комплексе "Динамо", поразивший меня властностью известного рок-певца. Или знакомство с человеком, придумавшим классификацию эстетики наподобие химических элементов. Его книжку я брала в Ленинке.
Восстановление храма
80-е гг. незаметно подошли к концу. (Продолжение следует.)
(C) Черухина С. Е., 2009
)Рассмотрена задача о представлении счётчика чётности, т. е. булевской функции x1+ ...+ xn (mod 2) в виде формулы над множеством логических связок {И, ИЛИ, НЕ}. Показано, что при n = 6 в любой такой формуле должно быть не меньше 40 вхождений переменных, причём оценка 40 является точной. Тем самым, точные оценки известны при всех n <= 8. Доказательство основано на переборе таблиц Храпченко, который осуществлён на компьютере.
Задача состоит в том, чтобы найти наиболее короткое представление счётчика чётности n переменных в виде формулы над множеством логических связок {И, ИЛИ, НЕ}. Очевидно, что длина формулы тесно связана с числом двуместных связок (И, ИЛИ), входящих в формулу, а это число на единицу меньше числа вхождений переменных. Оказалось, что именно число вхождений переменных является наиболее естественной мерой длины формул (см. теорему Храпченко [4]), поэтому это число мы будем называть длиной формулы. Наименьшую длину формулы, представляющей счётчик чётности n переменных, обозначим через λn.
В качестве примера рассмотрим случай n = 2:
|
x ⊕ y = x y V x y. |
(1) |
В левой части формулы (1) записана функция ИСКЛЮЧАЮЩЕЕ ИЛИ, т. е. счётчик чётности двух переменных, а в правой - эквивалентная формула над множеством И, ИЛИ, НЕ , при этом операция И опущена (т. к. И есть умножение на множестве {0,1}, а умножение можно опускать), ИЛИ обозначена знаком V, а НЕ - чёрточкой над переменными. Длина формулы в правой части (1) равна 4, так как переменные x и y входят по два раза. Таким образом, λ2 <= 4. Несложно показать, что более короткой формулы не существует, т. е. λ2 = 4.
Итак, задача состоит в нахождении чисел λn. Эта задача является достаточно древней; впервые она изучалась ещё Шенноном в 30-х годах XX-го века. Исторический экскурс на этот счёт содержится в монографии [6]. Отметим, что для всех n задача не решена, имеются верхние и нижние оценки чисел λn, отличающиеся не более, чем в 9/8 раз.
Данной задаче была посвящена курсовая работа автора на 3-м курсе (1996-й год). Вновь обратиться к ней заставила работа [8], в которой утверждалось, что приводится полное решение задачи. Однако работа [8] содержит достаточно грубую ошибку (найденную автором), вследствие которой она не даёт никакого численного прогресса в данной задаче (автор работы [8] согласился с тем, что в работе есть ошибка и отказался от её публикации в журнале).
В настоящее время наиболее близкими являются следующие оценки для чисел λn. Верхняя оценка Яблонского [7]:
|
λn <= 3 n pn - 2 pn2, где pn = 2[log2 n]. |
(2) |
Для n = 1, ..., 8 верхние оценки суть 1, 4, 10, 16, 28, 40, 52, 64, для любого n в качестве следствия получается λn< 9/8n2.
Нижняя оценка Храпченко [3]:
|
λn >= n2. |
(3) |
Из (2) и (3) следует точная оценка в случае, если n - степень двойки: λn = n2.
Нижняя оценка Рычкова [1]:
|
λn >= n2 + 3 для нечётных n >= 5, λn >= n2 + 2 для чётных n != 2k. |
(4) |
В силу (2)-(4) (и достаточно простого равенства λ3 = 10) известны точные оценки при n = 1, 2, 3, 4, 5, 7, 8 и при других n вида 2k.
В данной работе заполняется первый пробел, а именно, при n=6 находится точная оценка λ6 = 40. Доказательство основано на компьютерном переборе конфигураций, названных автором таблицами Храпченко (см. далее) в честь автора работы [3], впервые рассматривавшего подобные объекты. Первоначальная конструкция Храпченко было прояснена Рычковым, улучшившим нижнюю оценку, а также Вегенером, давшим доказательство теоремы Храпченко по индукции [9]. Наш подход использует идеи вышеперечисленных авторов.
Пусть дана булева функция f от переменных (x1, ..., xn) и множества A ⊆ f -1(0) и B ⊆ f -1(1). Другими словами, A состоит из некоторых наборов, на которых функция f принимает значение 0, а B - из некоторых наборов, на которых f принимает значение 1. Рассмотрим таблицу, в которой строки соответствуют множеству A, а столбцы - множеству B. Каждой клетке этой таблицы соответствует два набора - набор α из A, соответствующий строке, в которой находится клетка, и набор β из B, соответствующий столбцу. Если наборы α и β отличаются ровно в одной координате, например, в i-й, то в клетку запишем литерал xiσ, т. е. или переменную xi, или её отрицание xi. А именно, если на i-м месте набора α стоит 0, то запишем xi, иначе - xi. Построенную таблицу назовём предтаблицей Храпченко для функции f.
Для примера рассмотрим функцию f = x ⊕ y ⊕ z (счётчик чётности трёх переменных), множества A = f -1(0) и B = f -1(1) и приведём соответствующую предтаблицу Храпченко (рис. 1).
Рис. 1
Клетки, в которых записан литерал xiσ, назовём базовыми клетками этого литерала. Несложно показать, что никакие две базовые клетки одного и того же литерала не лежат в одном столбце или в одной строке. Пусть имеется множество, состоящее из k базовых клеток литерала xiσ. Тогда эти клетки лежат в k разных строках и k разных столбцах. Рассмотрим все k2 клеток, лежащих на пересечении указанных k строк и k столбцов. Это множество из k2 клеток назовём квадратом, натянутым на данное множество базовых клеток. Будем также говорить, что литерал xiσ является базовым для данного квадрата.
Несложно показать, что квадрат не содержит базовых клеток других литералов. Если в качестве исходного множества взять все базовые клетки данного литерала, то квадрат, натянутый на это множество, назовём it полным квадратом данного литерала. Очевидно, каждый квадрат, соответствующий данному литералу, является подмножеством его полного квадрата. Таблицей Храпченко для функции f назовём предтаблицу Храпченко, в которой выделены несколько попарно непересекающихся квадратов, причём каждая базовая клетка принадлежит некоторому квадрату (одному литералу могут соответствовать несколько квадратов).
Пример таблицы Храпченко для функции x ⊕ y ⊕ z приведён на рис. 2. Квадраты, соответствующие одному и тому же литералу, закрашены в один цвет, например, литералу x соответствует синий цвет. В этом примере каждая клетка принадлежит какому-нибудь квадрату, однако в общем случае могут быть клетки, не принадлежащие квадратам.
Рис. 2
Применение таблиц Храпченко к оцениванию длины формул основано на следующей лемме, которая извлекается из работ [3, 4, 1, 9]. Заметим, что используя законы де Моргана, отрицания в формуле можно опустить на переменные. Поэтому можно считать, что формула построена из литералов (переменных или их отрицаний) с помощью связок И и ИЛИ.
Лемма. Пусть булева функция f представлена формулой F. Тогда для функции f и любых множеств A, B можно построить такую таблицу Храпченко, что существует соответствие между её квадратами и литералами, входящими в формулу F. А именно, каждому квадрату можно поставить в соответствие некоторое вхождение в формулу F базового литерала этого квадрата, причём разным квадратам соответствуют разные вхождения.
Доказательство. Докажем индукцией по построению формулы F, считая, что все промежуточные формулы зависят (возможно, фиктивно) от одного и того же набора переменных (x1, ..., xn).
Базис индукции: F состоит из одного литерала, F = xiσ. В этом случае множество A состоит из некоторых наборов, имеющих на i-м месте значение σ (т. е. 0, если F = xi и 1, если F = xi), B состоит из некоторых наборов, на i-м месте которых стоит σ. Таким образом, каждый набор α ∈ A отличается от набора β ∈ B хотя бы в i-й координате. Значит, если α и β отличаются ровно в одной координате, то эта координата имеет номер i, причём в наборе α на i-м месте стоит σ. Следовательно, в предтаблице Храпченко для функции xiσ присутствуют базовые клетки только для литерала xiσ. Возьмём все эти базовые клетки и натянем на них квадрат, который поставим в соответствие единственному литералу формулы F. Получили требуемую таблицу.
Индуктивный переход: F = G H или F = G V H. Рассмотрим первый из них (второй аналогичен). На каждом наборе из множества B формула F равна 1, следовательно, и формулы G, H равны 1. В то же время, на каждом наборе из A или формула G, или формула H равна 0. Пусть AG - множество тех наборов из A, на которых формула G равна 0. Положим AH = A \ AG. Тогда на каждом наборе из AH формула H равна 0.
Применим к формуле G и множествам AG, B предположение индукции. Получим таблицу Храпченко для формулы G. Аналогично получим таблицу для формулы H. Наконец, объединим эти таблицы, т. е. таблицу для H поместим под таблицей для G. Полученная таблица будет искомой для формулы F.
В качестве примера применения леммы докажем, что λ3 >= 10. Рассмотрим предтаблицу Храпченко для функции x ⊕ y ⊕ z (рис. 1). Каждый из 6 литералов представлен двумя базовыми клетками. Кроме того, есть 4 пустых клетки. Очевидно, квадраты могут быть размера 1 x 1 или 2 x 2, но квадратов 2 x 2 может быть не более двух (так как в каждом из них две клетки пусты). Отбросив два квадрата 2 x 2, получим, что ещё 8 базовых клеток не покрыто квадратами, значит, они должны быть покрыты квадратами 1 x 1.
Итак, в любой таблице Храпченко, соответствующей данной предтаблице, должно быть не меньше 10 квадратов. Значит, в любой формуле F для функции x ⊕ y ⊕ z должно быть не меньше 10 вхождений литералов (так как каждый квадрат соответствует литералу). Окончательно, длина формулы F не меньше 10, т. е. λ3 >= 10. Оценка 10 точна, так как имеется следующая формула:
|
x ⊕ y ⊕ z = x (y z V y z) V x (y z V y z). |
(5) |
Заметим, что формуле (5) соответствует таблица Храпченко на рис. 2.
Из леммы выводится нижняя оценка Храпченко (3). А именно, известно общее число клеток в таблице, которое должно быть не меньше суммы площадей всех квадратов, так как квадраты не пересекаются. Кроме того, известна сумма сторон всех квадратов, равная общему числу базовых клеток в таблице. Тогда, используя неравенство Коши-Буняковского, можно оценить снизу число квадратов, которое не меньше длины формулы.
Для того, чтобы получить нижнюю оценку Рычкова, нужно дополнительно учесть следующий факт, который мы будем называть it эффектом Рычкова. В таблице Храпченко для счётчика чётности рассмотрим полные квадраты, соответствующие противоположным литералам x и x. Эти квадраты не пересекаются. Далее нужно заметить, что каждый квадрат, относящийся к любому другому литералу, отсекает от этих полных квадратов одну и ту же площадь (это можно увидеть на рис. 1-3). Поэтому в данных полных квадратах не заняты другими литералами равные площади.
Тогда, если сумма площадей квадратов для литерала x не равна аналогичной сумме для литерала x, то в таблице Храпченко неизбежно появятся пустоты (т. е. клетки, не входящие в квадраты), площадь которых также можно учесть. А именно, вместо неравенства "сумма площадей всех квадратов не больше числа клеток в таблице Храпченко", используемого при выводе нижней оценки Храпченко, можно использовать более сильное, а именно, в указанной сумме части, относящиеся к литералам x и x, можно заменить удвоенным максимумом из этих двух частей. Отметим, что это можно сделать только для одной из пар литералов.
Наконец, применим лемму для доказательства того, что λ6 >= 40. Для этого понизим размерность задачи на 1 и сведём её к некоторой задаче для n = 5 (аналогичные рассуждения действуют и для больших n).
Утверждение. Если в каждую формулу длины 28, вычисляющую счётчик чётности 5 переменных, хотя бы одна из переменных входит не меньше 8 раз, то λ6 >= 40.
Доказательство. Рассмотрим формулу длины λ6 для счётчика чётности 6 переменных. Выберем в ней переменную, входящую наибольшее число раз. Пусть это число равно k. В силу оценки Рычкова, λ6 >= 38. Поэтому k >= ⌈38/6⌉ = 7. Используя метод "забивания переменных" Субботовской цит Субботовская, подставим вместо этой переменной такую константу, что длина формулы уменьшится как минимум на k + ⌈k/2⌉. При этом получится формула для счётчика чётности 5 переменных или для его отрицания (в последнем случае навесим на формулу отрицание и спустим его на переменные). Имеем:
|
λ6 - (k + ⌈k/2⌉) >= λ5 = 28. |
(6) |
Если k >= 8, то из (6) следует λ6 >= 40. Если же k = 7, то из (6) следует λ6 >= 39. При этом, если допустить, что λ6 = 39, то после подстановки константы получится формула длины 28, в которую каждая переменная входит <= k = 7 раз, что противоречит нашему предположению. Таким образом, λ6 >= 40.
В силу утверждения, нам достаточно доказать, что для функции x ⊕ y ⊕ z ⊕ u ⊕ v не существует формулы длины 28, в которую каждая переменная входит <= 7 раз. Для этого, в силу леммы, достаточно показать, что не существует таблицы Храпченко для этой функции, в которой число квадратов <= 28 и каждой паре противоположных литералов xi, xi соответствует <= 7 квадратов. Предположим противное: такая таблица существует. Всего имеется 10 литералов, следовательно, хотя бы одному из них соответствует не больше 2-х квадратов. В силу симметрии можно считать, что этот литерал - x (отметим, что мы можем переставлять переменные, а также менять местами переменную и её отрицание).
Назовём литерал плохим, если ему соответствует >= 4 квадратов. Пусть имеется p плохих литералов. Отметим, что плохие литералы относятся к разным переменным (в противном случае мы бы имели пару противоположных литералов, которой соответствует >= 4 + 4 = 8 квадратов). Вначале рассмотрим случай p >= 3. Точнее, рассмотрим критический вариант этого случая, а именно: число квадратов равно 28, имеется ровно 3 плохих литерала, каждому из которых соответствует 4 квадрата, а остальным литералам соответствует по два или по три квадрата. Тогда ровно 5-ти литералам соответствует по два квадрата, а оставшимся двум - по три квадрата.
Подсчитаем минимальную сумму площадей квадратов. Каждому литералу соответствует 8 базовых клеток, поэтому если они разбиты на 2 квадрата, то сумма их площадей не меньше, чем 42 + 42 = 32. В случае трёх квадратов эта сумма не меньше, чем 32 + 32 + 22 = 22, для четырёх квадратов - не меньше, чем 4 x 22 = 16. Итого, общая сумма площадей не меньше
5 x 32 + 2 x 22 + 3 x 16 = 160 + 44 + 48 = 252.
Пока нет противоречия, так как всего в таблице Храпченко 16 x 16 = 256 клеток и ещё имеется люфт в 4 клетки. Однако противоречие появляется, если учесть эффект Рычкова (см. выше). А именно, есть пара противоположных литералов, один из которых плохой, а другой - нет. Поэтому при подсчёте суммы площадей квадратов мы можем взять тот из этих литералов, который даёт наибольший вклад в сумму, и учесть его вклад два раза (а противоположный литерал не учитывать). За счёт этого сумма увеличивается на 22 - 16 = 6 и мы получаем противоречие: 252 + 6 > 256.
Отметим, что в некритическом варианте случая p >= 3 сумма площадей будет ещё больше. Например, если вместо двух литералов по три квадрата в каждом взять один литерал с двумя квадратами и один с четырьмя, то минимальная сумма площадей увеличится с 2 x 22 = 44 до 16 + 32 = 48. Аналогичное произойдёт, если увеличить на 1 число квадратов у одного литерала и уменьшить на 1 у другого, при условии, что у первого литерала было не меньше квадратов, чем у второго. Кроме того, любой некритический вариант получается из критического с помощью таких операций (если число квадратов меньше 28, то можно считать, что недостающие квадраты имеют сторону 0).
Случай p <= 2, к сожалению, не поддаётся теоретическому анализу и был доказан с помощью вычисления на компьютере. В силу симметрии можно считать, что плохие литералы входят в множество {x, u} или в множество {u, v}. В любом случае, литералы y, z, u, v, y, z не являются плохими, а значит, этот случай вытекает из следующего результата вычислений.
Результат. Для функции x ⊕ y ⊕ z ⊕ u ⊕ v не существует таблицы Храпченко, в которой литералу x соответствует не больше двух квадратов, а каждому из литералов y, z, u, v, y, z - не больше трёх квадратов.
Вычисление проводилось по следующему алгоритму. Вначале для каждого литерала выписываются все разбиения базовых клеток этого литерала на соответствующее число квадратов. Например, для литерала x найдено 129 разбиений, для y и других - 1095. Затем для каждой пары литералов составляется таблица совместимости разбиений: два разбиения совместимы, если входящие в них квадраты не пересекаются. Например, для пары (x, y) найдено 10149 совместимых комбинаций из 129 x 1095 возможных, для пары (y, z) - 196047 из 10952.
Наконец, организуется цикл по всем наборам разбиений с отсечением несовместимых ветвей. А именно, просматриваются совместимые комбинации разбиений для литералов x и y. Для каждой из них перебираются все разбиения литерала z, совместимые с рассматриваемыми разбиениями для x и для y. Далее перебираются разбиения литерала u, затем v, y и, наконец, z. После рассмотрения трёх литералов осталось 79367 совместимых комбинаций, после рассмотрения четырёх - 13566, пяти - 312, шести - 12. Одна из этих 12-ти комбинаций приведена на рис. 3. Номера наборов даны в 16-ричной системе счисления. Как обычно, каждый цвет соответствует своему литералу.
В итоге (после рассмотрения всех 7 литералов) оказалось, что ни одна из комбинаций не удовлетворяет всем условиям совместимости. Расчёт длился несколько секунд на компьютере с тактовой частотой 2 GHz под управлением OS DuS [5]. При этом основное время было потрачено на составление таблиц совместимости пар литералов.
Рис. 3.
[1] Рычков К. Л. О нижних оценках сложности параллельно-последовательных контактных схем, реализующих линейные булевы функции // Сибирский журнал исследования операций. - 1994. - Т. 1, № 4. - C. 33-52.
[2] Субботовская Б. А. О реализации линейных функций формулами в базисе lor, &, - // ДАН СССР. - 1961. - Т. 136, № 3. - C. 784-787.
[3] Храпченко В. М. О сложности реализации линейной функции в классе П-схем // Матем. заметки. - 1971. - Т. 9, № 1. - C. 35-40.
[4] Храпченко В. М. Об одном методе получения нижних оценок сложности П-схем // Матем. заметки. - 1972. - Т. 10, № 1. - C. 83-92.
[5] Черухин Д. Ю. Операционная система DuS // Неформальная наука. - 2007. - № 2. - С. 13-24.
[6] Черухин Д. Ю. Сравнение булевых базисов. Конспект лекций спецкурса. М.: График Без Границ, 2008.
[7] Яблонский С. В. Реализация линейной функции в классе П-схем // ДАН СССР. - 1954. - Т. 94, № 5. - С. 805-806.
[8] Lee T. A new rank technique for formula size lower bounds // Lecture Notes in Computer Science. V. 4393 (2007). P. 145-156.
[9] Wegener I. The Complexity of Boolean Functions. Teubner, Wiley, 1987. - http://www.eccc.uni-trier.de/eccc-local/ECCC-Books/wegener_book_readme.html
(C) Черухин Д. Ю., 2009
)Когда играет шторм, круша и пенясь,
не посылайте к небесам хулы.
То ницшеанский учится младенец:
он изучает правила игры.Когда он видит ваш кромешный глянец,
бессмысленный и беспощадный быт,
он низвергает свой протуберанец,
и потому доселе не забыт.Его рисуют мудрым грозным старцем,
громящим очумелые пиры,
а он в нас с неба просто тычет пальцем.
Он изучает правила игры.Ведь если он признает нашу скуку
основой созидания миров,
то он, как все, главкому вскинет руку
и психиатру скажет: "Я здоров".И опустеют чёрные могилы,
спадут кресты, и нас разделит суд,
и в мир огромной, новой, лютой силы
лишь избранные полчища пройдут.Не оттого ль мы в этой жизни гости,
что свет ещё мерцает до поры,
пока Всевышний не играет в кости,
а изучает правила игры.
Стихотворение написано под влиянием сайта Стихи.ру [1].
[1] http://www.stihi.ru/poems/2008/05/24/3786.html
(C) Черухин Д. Ю., 2009
)1) Человек приходит в мир, где существуют уже какие-то правила. Хорошо, когда он смотрит на эти правила со стороны: "Ах, вот как все у вас! Понятно..." Хорошо, когда у человека за душой ничего своего нет, никаких представлений о том, что должно быть правильно, а что нет, что хорошо, а что - не очень. М. б., таких людей большинство, я не знаю. Мне доводилось слышать такие слова: "Ну, жизнь так устроена, чего же ты хочешь!"
Во всяком случае, часть людей приспосабливается к такому положению и начинает жить с двойной бухгалтерией внутри, понимая, как надо на самом деле, но делая совсем по-другому. Как говаривал дьякон А. Кураев: "Я со своей совестью всегда договорюсь!" Удобно иметь такую совесть, но такое счастье дано не всем.
Гораздо хуже тем, кто никак не может приспособиться к существующему порядку вещей, все время получается не в ногу. Хорошо, если есть тяга к юродству, к позёрству. А если нет? Даже забиться в свою норку нет никакой возможности, все равно приходится время от времени вылезать и контактировать с внешним миром. Да, я забыла о ещё одной возможности: о создании своего круга, своей общины, по существу, отдельной сектантской группы, сообщества, экологической ниши. Возможно, это единственное разумное решение, но, тем не менее, оно мне не близко. Своя диаспора, по каким бы признакам она не объединялась, нет, увольте!
2) ...и всё же игра! Почему? Что приходит мне на ум сейчас? Пожалуй, "Игра в бисер" Гессе. Это как раз описание мира, в котором Бог уже действует (играет) по хорошо известным правилам со случайными компонентами, только в отличие от главного героя романа, который играл с абстрактными элементами искусства, в стихотворении идёт речь о предстоящей игре с живыми душами, в которой случайность кажется чудовищной, а сами правила страшными в своей неизбежности и бесчеловечности. Возможно ли иное? То, о чем мечтали древние? Божественная Лила - игра человека с Богом, полная радости и взаимного сотрудничества? Оставим эти вопросы автору в надежде на новые стихи, полные глубокого смысла и совершенной формы.
3) И, наконец, третья возможная интерпретация. Бог ещё только родился, мир свеж и нов для него, Он лишь пробует его на "зуб", примеряясь силами. Настоящая игра не началась! Всё только впереди...
(C) Черухина С. Е., 2009