Category: история

Category was added automatically. Read all entries about "история".

тигр

о невычислимых функциях

Данный пост является "общепросветительским", поэтому он открыт для всех. На эту тему я уже писал https://falcao.livejournal.com/26513.html когда-то давно. Открывать эту ссылку вовсе не обязательно. Я постараюсь изложить всё как бы почти "с нуля".

Что такое невычислимая функция? Это такая функция, которую нельзя вычислить при помощи алгоритма, то есть невозможно написать программу для её вычисления. Хотя достаточно легко доказать, что невычислимые функции существуют, не так просто предъявить конкретный пример, а тем более интересный пример. В посте по ссылке такой пример был приведён, но описанная там функция Busy Beaver слишком уж быстро растёт. Мы её слабо себе представляем, зная только то, что её значения -- какие-то огромные числа. Здесь я хочу привести другой пример невычислимой функции, которая растёт очень медленно, и поведение которой мы можем себе представить намного лучше. Дополнительным соображением, побудившим меня написать этот текст, является связь с известными логическими парадоксами, а этой проблематики я в прошлом частенько касался.

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

Итак, пусть нам дано число, и надо написать программу, которая его распечатывает, останавливаясь при этом. Будем считать, что для печати у нас есть команда print. Тогда, чтобы распечатать число, скажем, 2021, достаточно написать команду print(2021). Программа будет готова.

Ясно, что бывают числа, распечатывать которые таким способом нежелательно. Допустим, вместо 2021 у нас есть очень большое число типа 100...0 с миллионом нулей на конце. Мы не хотим составлять программу из миллиона символов. Тогда можно распечатать нули в цикле. Примерно так:

print(1);
for i:=1 to 1000000 do print(0)

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

Обозначим то число, которое мы хотим напечатать, через n. Самый простой способ написания программы требует порядка lg n + C символов, где C -- небольшая константа. В тех случаях, когда число является "случайным", то есть состоит из случайно выбираемых цифр, скорее всего, нет принципиально другого способа распечатать число кроме как указать его явно. Однако зачастую оказывается возможным поступить как-то более хитро. Один такой пример мы привели. Другие примеры могут возникнуть на следующей основе.
Collapse )
pequim1

13,7%

ТигрИнформАгентство сообщает, что комментарии из этого поста раскрыты для ознакомления.

Сама по себе вероятностная задача, которая там рассматривалась, решается стандартными способами, и ответ в ней составляет 15*74/86. Это примерно 0,137, то есть свыше 13 с половиной процентов. Причиной того, что я устроил этот опрос, является то, что этот ответ, в правильности которого никогда не было сомнений, мне даже сейчас кажется удивительным. В смысле, "почему так много?" Интуитивно кажется, что вероятность намного меньше. Я сам без вычислений назвал бы, наверное, процентов 5 от силы.

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

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

А для любителей "бразилейры" -- вот такая видеозапись, где Мария Рита (дочь Элиш Режины) поёт песню 70-х годов вместе с Фагнером (одним из авторов этой песни).

  • Current Music
    Fagner e Maria Rita -- Mucuripe
тигр

перекладывание карт

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

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

У игрока на руках имеется 13 карт одной масти, расположенных в порядке от туза до двойки. За один ход разрешается извлечь несколько карт, идущих подряд (можно всего одну), и вставить эти карты в таком же порядке в другое место (то есть между какими-то двумя картами, или в самое начало, или в самый конец). Требуется за минимальное число ходов расположить карты в противоположном порядке, то есть от двойки до туза.

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

Т К Д В 10 9 8 7 6 5 4 3 2

Т К 10 9 8 7 6 Д В 5 4 3 2

В таких задачах обычно надо сделать две вещи. Во-первых, предъявить сам способ перекладывания, приводящий к нужному ответу. Сразу хочется отметить, что таких способов может быть очень много, и они вовсе не обязаны совпадать в разных решениях. Во-вторых, и это здесь наиболее трудно -- надо доказать, что за меньшее число ходов справиться с той же задачей нельзя, подтвердив тем самым, что предложенный способ в самом деле приводит к минимально возможному числу ходов.

Понятно, например, что в данной задаче очень легко справиться за 12 ходов, перекладывая карты по одной: на первом ходу двойку переносим в самое начало, на втором -- вставляем вслед за ней тройку, затем ставим на нужное место четвёрку, и так вплоть до переноса короля. Однако это количество ходов слишком велико, и хватает гораздо меньшего числа операций.

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

Collapse )
  • Current Music
    Eliane Elias -- Crystal and Lace
тигры

итоги и победители

Наконец-то закрыт опрос, проводившийся здесь. Можно подвести окончательные итоги.

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

Вот какие слова оказались "рекордными" (жирным шрифтом написано задание; справа -- наиболее часто встречавшийся ответ, с указанием количества упоминаний):

01. автопробег бездорожье 27
02. бельё грязное 9
03. вокзал поезд 18
04. гримаса лицо 14
05. дурак Иван 19
06. забава детская 9
07. краска кисть 15
08. лев царь 21
09. монастырь женский 9
10. облако небо 16
11. паспорт документ 11
12. подозрительный тип 29
13. постель мятая 7
14. станция метро 9
15. тюрьма сума 10
16. физика химия 16
17. хороший плохой 24
18. царь Горох 7
19. член партии 16
20. ягода малина 35

Единоличной победительницей стала прекрасная merengue! Ура!!! (Бурные аплодисменты, переходящие в овацию; все встают! :)) Набрала она 11 очков! Это очень хороший результат -- особенно с учётом того, что по многим из оставшихся заданий она назвала слова, близкие к "рекордным".

Я от души поздравляю нашу победительницу!!!

Вторыми оказались два участника: all_x и an_ger, с 10 очками у каждого, что тоже весьма неплохо. Далее идут семь участников с 9 очками, потом восемь участников с 8 очками, десять -- с 7 очками, и так далее. Я бы также вручил хотя бы "мысленный" спецприз самому "оригинально мыслящему" участнику, набравшего 1 очко :)

Все ответы участников теперь "расскринены", свои результаты можно посмотреть здесь. Вопросы, апелляции и прочее (в вежливой форме :)) -- "принимаюццо"!

Кое-какую дополнительную статистику я могу при необходимости отразить в комментах. Всем игравшим -- ещё раз спасибо!
  • Current Music
    Sueli Costa -- Vamos Dançar
тигр

об одной математической проблеме

Я давно уже не писал постов популярно-математического характера. Сейчас возникло желание это сделать. Цель данного поста вот какая. Есть одна знаменитая проблема в области теории групп (это раздел алгебры), которой я очень давно интересуюсь. Мне всегда казалось, что сформулировать её в более или менее элементарных терминах, не вводя каких-либо специальных понятий, почти невозможно. Однако на днях я придумал такую переформулировку, которая является совершенно строгой, точно отражает суть дела, и при этом может быть понята неспециалистом. В каком-то смысле можно сказать, что задача получилась похожей на "олимпиадную".

Основной текст идёт под "катом" -- я думаю, что математическая проблематика интересует далеко не всех. Эту запись нет смысла помещать в режиме "френдс-онли", поэтому я делаю её открытой. Collapse )

Комментарии к данному посту отключены, а обсуждение проводится здесь. Я при этом прошу воздержаться от "сакраментальных" вопросов типа "а зачем это нужно" или "а где это можно применить". Если кто-то вник в содержание, и предмет рассмотрения показался интересным, то это уже даёт ответ на оба вопроса, ну а если нет, то вопросы излишни :)
vinho verde

к "решению" (3x+1)-проблемы

Этот пост я размещал, будучи в полной уверенности, что делаю это в сообществе ru_math. Только сейчас обнаружил, что поместил его у себя в дневнике. Прошу прощения у читателей моего журнала :)

Удалять не буду, так как тут есть комменты, но убираю под кат.Collapse )
тигр

истуар де пиар :)

Встретил во френд-ленте хохму о предложении заменить "чужеземное" слово "пиар" на слово "полуокружность" в свете того, что её длина равна "пи-эр" :)

Шутки шутками, но слово-то, оказывается, исконно русское!

В 1705 году Феофан Прокопович по заказу Петра I написал пьесу "Владимир" о крещении Руси. Пьеса носила явно пропагандистский характер; прогрессивному Владимиру противостояли там реакционные "язычнеги", имена которых: Жеривол, Курояд и Пиар :)

Как мне пояснил kirillankudinov, от которого я впервые усышал эту историю, имя происходит от слова "пить".

Ирония судьбы ещё и в том, что это была ПЕРВАЯ отечественная пьеса, и она представляла собой самый откровенный пиар в современном смысле слова. После успеха постановки, Пётр выписал себе Прокоповича из Киева в северную столицу.

Подробности можно найти здесь: http://www.gumer.info/bibliotek_Buks/Culture/Ysp/15.php
тигры

кинофильмы

Воплощаю в жизнь давно созревшее желание: составить свой список кинофильмов. Идея заимствована у lev_semerkin; см. его записи здесь, здесь и здесь. Сразу хочу оговорить, что сюда вошли только "старые" фильмы. Современное кино я не смотрю вообще. Многие удивляются: почему? Collapse )
  • Current Music
    Lucero -- La Duda
  • Tags
vinho verde

О Короткевиче

Речь пойдёт о замечательном белорусском писателе Владимире Семёновиче Короткевиче (1930 - 1984).

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

На Короткевича я вышел сравнительно недавно, хотя слышал о нём с давних пор -- ещё со времён фильма Валерия Рубинчика "Дикая охота короля Стаха". Когда я решил ознакомиться с самой повестью, по которой снят фильм, то быстро вошёл во вкус и прочитал друг за другом несколько повестей и романов. Надо сказать, всё прочитанное на меня произвело очень большое впечатление во всех, так сказать, "номинациях". То есть, во-первых, это просто интересно, это увлекает. (Я считаю это одним из самых важных критериев.) Во-вторых, у писателя очень оригинальный язык. Он не только не пишет в чьём-то узнаваемом стиле, но у него вообще нет "самоповторов" -- все его произведения совершенно разные и по сюжету, и по времени действия, и по многим другим признакам. Например, очень интересна в этом смысле повесть "Оружие" (1981), где действие происходит в Москве 1862 года. Это почти что детектив, и он по своей атмосфере мне сильно напомнил романы Акунина, которые я читал раньше. Я так и не знаю, случайно ли это совпадение, то есть в какой мере Короткевич мог повлиять на Акунина (точнее, именно эта повесть).

Я нашёл в Интернете очень хороший сайт, где есть подробная биография (на белорусском языке), почти все основные вещи в оригинале и очень многое в русском переводе. (Выбор намного больше, чем в библиотеке Мошкова.)

http://www.uladzimir-karatkevich.com

А совсем недавно мне сказали, что в последнем номере журнала "Наш современник" за прошлый год есть заметка о Короткевиче, написанная Анатолием Заболоцким (который был оператором многих известных фильмов). Меня это несколько удивило, так как Короткевич вроде бы не принадлежал к тому кругу лиц, о котором в этом журнале принято писать.

http://nashsovr.aihs.net/p.php?y=2005&n=12&id=9

В заметке есть ряд моментов, которые можно назвать "скользкими", но в целом она интересная.
vinho verde

Хомут свободы

Решил всё-таки использовать оставшиеся бесплатные полчаса в Интернете и разместить то, что давно уже собирался. Тут в нескольких дискуссиях всплывала тема свободы (надо думать, в связи с текущими политическими событиями). Мне захотелось привести одну из моих любимых цитат. Она принадлежит Михаилу Пришвину, которого я считаю наиболее значительным мыслителем первой половины XX века. О нём я хочу написать отдельно. А вот его высказывание на тему того, что такое свобода.

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

Меня это высказывание совершенно восхищает своей точностью и дерзким соединением казалось бы противоположных вещей. Интересно, всем ли такая мысль по душе?