Ключевое слово
27 | 03 | 2017
Новости Библиотеки

Шахматы онлайн

Чессбомб

Welcome, Guest
Username: Password: Remember me

TOPIC: Математика для чайников №3

Математика для чайников №3 18 Янв 2017 09:33 #601

  • самоед-3
  • самоед-3's Avatar
  • OFFLINE
  • Окольничий
  • Posts: 856
  • Thank you received: 15
  • Karma: 4
Vladimirovich wrote:
Вот тут это все написано ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80...8C%D0%BA%D0%BE%D0%BC

Нет, указанный мною метод - это не метод пузырька. Например, последовательность 3, 2, 1 метод пузырька упорядочивает двумя проходами за три перестановки:

2, 3, 1; 2, 1, 3;
1, 2, 3;

а не сразу всего за одну: 1, 2, 3.
Last Edit: 18 Янв 2017 09:34 by самоед-3.

Математика для чайников №3 18 Янв 2017 10:10 #602

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 62406
  • Thank you received: 540
  • Karma: 65
Да все едино... Румын, болгарин :)
Зато бегать по всему массиву каждый раз не надо

O(n2) и там и там
Каждому - своё.
Last Edit: 18 Янв 2017 10:12 by Vladimirovich.

Математика для чайников №3 19 Янв 2017 03:50 #603

  • самородок
  • самородок's Avatar
самоед-3 wrote:
самоед-3 wrote:
Хочу упорядочить конечную последовательность чисел за минимальное число шагов, просто меняя местами два числа на каждом шаге. Как это сделать?

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

Доказать это строго я не могу, я проверил это статистически. Небольшое сомнение лишь в том, что последовательности у меня не совсем случайные, вдруг на совсем уж случайных это не так.
Аригинальный алгоритм - вычисляет сперва порядок, не переставляя ничего (!), а потом уже переставляет число, на заранее подготовленные позиции. :idea:

Математика для чайников №3 19 Янв 2017 05:23 #604

  • самоед-3
  • самоед-3's Avatar
  • OFFLINE
  • Окольничий
  • Posts: 856
  • Thank you received: 15
  • Karma: 4
самородок wrote:
Аригинальный алгоритм - вычисляет сперва порядок, не переставляя ничего (!), а потом уже переставляет число, на заранее подготовленные позиции. :idea:

Это не алгоритм сортировки. Это алгоритм подсчета нужного числа перестановок. Более того, при его реализации сначала создается упорядоченная (!) копия исходной последовательности - упорядоченная все равно каким способом, которая и используется для подсчета.

Математика для чайников №3 19 Янв 2017 05:44 #605

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Посадник
  • Posts: 28198
  • Thank you received: 36
  • Karma: 3
всё это давно пропахано, найдено лучших/эффективнейших способов и ухнуто в программные пакеты для компов :flag:
Last Edit: 19 Янв 2017 05:45 by Хайдук.

Математика для чайников №3 19 Янв 2017 05:48 #606

  • самоед-3
  • самоед-3's Avatar
  • OFFLINE
  • Окольничий
  • Posts: 856
  • Thank you received: 15
  • Karma: 4
Да, конечно. Даже у меня по этому делу две книжки Вирта в книжном шкафу стоят. ))

Математика для чайников №3 19 Янв 2017 08:38 #607

  • infoliokrat
  • infoliokrat's Avatar
  • OFFLINE
  • Окольничий
  • Posts: 896
  • Karma: 2
Vladimirovich wrote:
Да все едино... Румын, болгарин :)
Зато бегать по всему массиву каждый раз не надо

O(n2) и там и там

А что, наверное, несмотря на
всё это давно пропахано, найдено лучших/эффективнейших способов и ухнуто в программные пакеты для компов :flag:
там не осталось места для очередных оптимизаций? НЕ ВЕРЮ: ибо тогда бесконечности всякие если хоть где-то хоть как-то теряюют смысл, то по всеобщей аналогии ОНИ (бесконечности) везде не нужны (на мой примитивный инфолиовзгляд). Например:
1.если вопрос только в том, чтобы "работал однопроходной алгоритм", то наверняка есть решение, заключающееся, в частности в том, что создается - примитивно столько массивов, сколько элементов и "работа проводится только с индексами"... Правда там сама КОМАНДА может быть сложнее "пузырьковых"...
2.А вообще-то если где-то кто-то (алгоритм ли) получал какой-то массив, то уже тогда он мог считать=индексировать элементы массива сразу в требуемом порядке .
3. В перспективе будет так: Как начальник скажет- так и придется сортировать... И это будет правильно! (Пример такой:
Warning: Spoiler! [ Click to expand ]

Математика для чайников №3 19 Янв 2017 08:48 #608

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 62406
  • Thank you received: 540
  • Karma: 65
infoliokrat wrote:
там не осталось места для очередных оптимизаций? НЕ ВЕРЮ

В общем случае минимальная скорость алгоритма сортировки O(n*log(n))
Такая скорость достигнута, а значит верить или не верить бессмысленно.
Для специальных случаев скорость может быть еще улучшена, да.
Каждому - своё.
Last Edit: 19 Янв 2017 08:49 by Vladimirovich.

Математика для чайников №3 19 Янв 2017 09:26 #609

  • infoliokrat
  • infoliokrat's Avatar
  • OFFLINE
  • Окольничий
  • Posts: 896
  • Karma: 2
Vladimirovich wrote:
infoliokrat wrote:
там не осталось места для очередных оптимизаций? НЕ ВЕРЮ

В общем случае минимальная скорость алгоритма сортировки O(n*log(n))
Такая скорость достигнута, а значит верить или не верить бессмысленно.
Для специальных случаев скорость может быть еще улучшена, да.
О, спасибо за оперативный и точный ответ! Значит ученым (не мне) еще остается не паханое поле по всем трем направлениям:
1. Целочисленные вычисления оптимизаций (где иррациональным и трансцендентным нет места);
2. При создании массивов;
3. и при субъективном их применении Уверен, что большая часть :) всего, что
давно пропахано, найдено лучших/эффективнейших способов и ухнуто в программные пакеты для компов
сделано было удовольствия ДЛЯ и РАДИ оптимизации (и внутренней красоты) применения ПРОШЛЫХ мощностей СВТ... (типа процессора ОДНОразрядного ЭВМ ЕС). А сейчас, например, долго уговаривал коллегу-пенсионера, что ему ПО БАРАБАНУ отсутствие у него флэшки ТЕРРАБИТНОЙ... Ну не успею, как пенсионер, не только с пользой ее заполнить, а даже просмотреть все то, что там может быть, что целесообразно записать , а тем более потом прочитать, посмотреть, изучить, осознать, применить удовольствия ДЛЯ и истины РАДИ, при имеющемся самолюбии себя и окружающих. З павагай, паклонам

Математика для чайников №3 26 Янв 2017 19:39 #610

  • самоед-3
  • самоед-3's Avatar
  • OFFLINE
  • Окольничий
  • Posts: 856
  • Thank you received: 15
  • Karma: 4
Есть две числовые последовательности одинаковой длины. Каждый член 1-й последовательности - это одно из 4 чисел, а каждый член 2-й последовательности - это одно из 7 чисел. Попарная сумма этих последовательностей, однако, принимает не 4х7 = 28 значений, а только 3 значения. Можно ли считать отсюда, что данные последовательности сильно связаны, при том что их коэфф. корреляции равен всего -0,173?
Last Edit: 26 Янв 2017 19:54 by самоед-3.

Математика для чайников №3 28 Янв 2017 07:01 #611

  • самоед-3
  • самоед-3's Avatar
  • OFFLINE
  • Окольничий
  • Posts: 856
  • Thank you received: 15
  • Karma: 4
самоед-3 wrote:
Есть две числовые последовательности одинаковой длины. Каждый член 1-й последовательности - это одно из 4 чисел, а каждый член 2-й последовательности - это одно из 7 чисел. Попарная сумма этих последовательностей, однако, принимает не 4х7 = 28 значений, а только 3 значения. Можно ли считать отсюда, что данные последовательности сильно связаны, при том что их коэфф. корреляции равен всего -0,173?

Пришлось поэкспериментировать. Взял - 1 000 000 раз - две чисто случайные последовательности той же длины (255). Члены первой последовательности принимали те же 4 значения (1, 2, 3, 4), но случайным образом, а члены второй - те же 7 значений (4, 5, 6, 7, 8, 9, 10), но тоже случайным образом. В итоге получилось, что их попарная, почленная сумма почти всегда принимает любое значение от минимального (1 + 4 = 5) до максимального (4 + 10 = 14) включительно и лишь изредка, в одном случае из 5000, она не принимает или минимального, или максимального значения.

Т.е. эта случайная сумма почти всегда принимает 10 значений и лишь изредка 9 значений. В исходной же задаче сумма принимает только 3 значения (8, 10, 12). Спрашивается, значимо ли это?
Last Edit: 28 Янв 2017 10:03 by самоед-3.

Математика для чайников №3 30 Янв 2017 10:44 #612

  • самоед-3
  • самоед-3's Avatar
  • OFFLINE
  • Окольничий
  • Posts: 856
  • Thank you received: 15
  • Karma: 4
Подсчитал еще коэффициент Фехнера. Оказался тоже маленьким: 0.114.

Википедия wrote:
Коэффициент корреляции знаков Фехнера

Подсчитывается количество совпадений и несовпадений знаков отклонений значений показателей от их среднего значения.

i = (C − H)/(C + H)

C — число пар, у которых знаки отклонений значений от их средних совпадают.

H — число пар, у которых знаки отклонений значений от их средних не совпадают.

Математика для чайников №3 30 Янв 2017 13:12 #613

  • инфолиократ
  • инфолиократ's Avatar
Т.е. эта случайная сумма почти всегда принимает 10 значений и лишь изредка 9 значений. В исходной же задаче сумма принимает только 3 значения (8, 10, 12). Спрашивается, значимо ли это?
Ничего пока не считал, но т.н. случайность - это непознанная закономерность позволяет утверждать что цитируемое
и) значимо (наверняка в некоторой другой системе счисления, или при вычислении корреляции самих коэффициентов корреляции в 7-ричной или "натуральной" системе счисления) результат будет еще более впечатляющий...
к) значимо не информационно-абстрактно, а классически (вычисления выполнены, если ошибки нет, то даже "отсутствие ожидаемого результата" - тоже результат).
с) субъективно значимо.
Warning: Spoiler! [ Click to expand ]
так надо!

З павагай да неабыякавых КФ

Математика для чайников №3 06 Фев 2017 13:42 #614

  • самоед-3
  • самоед-3's Avatar
  • OFFLINE
  • Окольничий
  • Posts: 856
  • Thank you received: 15
  • Karma: 4
самоед-3 wrote:
самоед-3 wrote:
Есть две числовые последовательности одинаковой длины. Каждый член 1-й последовательности - это одно из 4 чисел, а каждый член 2-й последовательности - это одно из 7 чисел. Попарная сумма этих последовательностей, однако, принимает не 4х7 = 28 значений, а только 3 значения. Можно ли считать отсюда, что данные последовательности сильно связаны, при том что их коэфф. корреляции равен всего -0,173?

Пришлось поэкспериментировать. Взял - 1 000 000 раз - две чисто случайные последовательности той же длины (255). Члены первой последовательности принимали те же 4 значения (1, 2, 3, 4), но случайным образом, а члены второй - те же 7 значений (4, 5, 6, 7, 8, 9, 10), но тоже случайным образом. В итоге получилось, что их попарная, почленная сумма почти всегда принимает любое значение от минимального (1 + 4 = 5) до максимального (4 + 10 = 14) включительно и лишь изредка, в одном случае из 5000, она не принимает или минимального, или максимального значения.

Т.е. эта случайная сумма почти всегда принимает 10 значений и лишь изредка 9 значений. В исходной же задаче сумма принимает только 3 значения (8, 10, 12). Спрашивается, значимо ли это?

Я все-таки дожал эту задачу. Правда, пришлось более адекватно определить 1-ю последовательность, чтобы ее члены принимали еще и значение 0. Обозначим ее член через g, а член с тем же номером 2-й последовательности - через h. И тогда областью значений отношения (h - g)/(h + g) будет не что-нибудь, а ряд Фарея F5, всего 11 дробей.

Вот так и связаны исходные последовательности. Фишка не в том, что встречаются именно эти 11 дробей (они возникают и для случайных последовательностей), а в том, что никакие другие дроби не встречаются!
Last Edit: 06 Фев 2017 13:47 by самоед-3.

Математика для чайников №3 14 Фев 2017 15:57 #615

  • самоед-3
  • самоед-3's Avatar
  • OFFLINE
  • Окольничий
  • Posts: 856
  • Thank you received: 15
  • Karma: 4
Вот какую звездную модель я придумал. Возьмем конечное множество точек, абстрактных звезд, и сделаем следующее.

1. Определим расстояние между точками, т.е. введем метрику в их пространстве (неравенство треугольника при этом не очень обязательно).

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

3. Определим максимальные интервалы - это те интервалы, которые не являются подынтервалами других интервалов (чтобы интервалов было поменьше, а то их может быть чересчур много).

4. Определим спектр звезды - совокупность всех максимальных интервалов, содержащих данную звезду.

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

Я рассмотрел имеющееся у меня множество из 255 пятимерных точек, звезд, в трех метриках:

- в манхеттенской метрике, и тогда имеется 5 потухших звезд;
- в чебышёвской метрике, и тогда имеется 4 потухшие звезды, в т.ч. 2 звезды из 1-го пункта;
- в метрике Хемминга, и тогда имеется 72 потухшие звезды, в т.ч. все из 1-го пункта и все, кроме одной, из 2-го.

Пока такая вот предварительная картина, звездная модель.
Last Edit: 14 Фев 2017 17:54 by самоед-3.

Математика для чайников №3 17 Март 2017 18:35 #616

  • onedrey
  • onedrey's Avatar
  • OFFLINE
  • Наместник
  • Posts: 19195
  • Thank you received: 556
  • Karma: -10
Дело было сто лет назад и не в моем универе, поэтому какие-то детали могли быть и другими, но все равно нет дыма без огня.

Лектор -- большой математик -- рассказывал студентам про так называемый гармонический ряд. Если кто забыл, это бесконечная сумма следующего вида : 1 + 1/2 + 1/3 + 1/4 + 1/5 .... и так далее. Профессор доказал на лекции, что этот ряд расходится, то есть, хотя каждое следующее слагаемое все меньше и меньше, сумма их рано или поздно превзойдет любое мыслимое число. Так вот, доказал он теорему, а потом мечтательно улыбнулся и говорит:

-- Представьте себе Байкал, из которого никакая Ангара не вытекает, и никакой Баргузин в него не впадает. Просто гигантское озеро с фиксированным объемом воды. А на берегу сидит Конфуций и пытается вычерпать Байкал наперстком. Причем не просто черпает каждый раз по наперстку, а уменьшает дозу: сначала целый наперсток, потом половинка, потом третья часть, потом четвертая... Так представляете -- рано или поздно он ведь его полностью вычерпает! Именно это мы с вами сейчас доказали.

А вид у него был мечтательный, повторю
Воронеж - це Європа!

Математика для чайников №3 17 Март 2017 18:44 #617

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Посадник
  • Posts: 28198
  • Thank you received: 36
  • Karma: 3
ув. инфолиократ вычерпанию Байкала не поверит :lol:
Last Edit: 17 Март 2017 18:44 by Хайдук.

Математика для чайников №3 17 Март 2017 19:09 #618

  • onedrey
  • onedrey's Avatar
  • OFFLINE
  • Наместник
  • Posts: 19195
  • Thank you received: 556
  • Karma: -10
Он просто не видел Конфуция
Воронеж - це Європа!

Математика для чайников №3 20 Март 2017 11:29 #619

  • ))
  • ))'s Avatar
Так представляете -- рано или поздно он ведь его полностью вычерпает! Именно это мы с вами сейчас доказали.

Ну так сколько "рано или поздно" ему понадобится? Конкретно.

Математика для чайников №3 20 Март 2017 11:34 #620

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Посадник
  • Posts: 28198
  • Thank you received: 36
  • Karma: 3
очень поздно.

Математика для чайников №3 20 Март 2017 12:02 #621

  • ))
  • ))'s Avatar
Я в свое время задавался этим вопросом для Ангары, вытекающей из Байкала.

Пусть современный сток (в истоке) Ангары 1850 м3/с постоянен, а объем Байкала 24 000 км3 не пополняется и вытекает до капли. Тогда для исчерпания потребуется

24000 х 109 / 1850 секунд ~ 400 лет.

А для Конфуция с гармонически убывающим наперстком сколько?

Математика для чайников №3 20 Март 2017 13:28 #622

  • самоед-3
  • самоед-3's Avatar
  • OFFLINE
  • Окольничий
  • Posts: 856
  • Thank you received: 15
  • Karma: 4
Не, Конфуцию никакого времени не хватит. Если считать, что объем наперстка, пусть первоначально равный 1 см3, гармонически убывает каждую секунду, а Конфуций работает со скорость 1 наперсток в секунду, то вычерпать 24 000 км3 воды ему потребуется примерно

е в степени (24000 х 1015), т.е. больше 1010 000 000 000 000 000 000, секунд,

тогда как возраст Вселенной для сравнения меньше 1018 секунд.
Last Edit: 20 Март 2017 13:31 by самоед-3.

Математика для чайников №3 20 Март 2017 14:38 #623

  • ))
  • ))'s Avatar
Помните, конечно, в горбачевское время был проект переброски части стока северных рек в Каспийское море, поскольку его уровень катастрофически снизился. Но "общественность" этот проект успешно зарубила. Я тогда же задался вопросом: насколько повысится уровень Каспийского моря, если всю тогдашнюю общественность - максимум 290 млн человек - целиком утопить в этом самом море? Оцените, вы удивитесь.

Математика для чайников №3 20 Март 2017 19:18 #624

  • инфолиократ
  • инфолиократ's Avatar
)) wrote:
Помните, конечно, в горбачевское время был проект переброски части стока северных рек в Каспийское море, поскольку его уровень катастрофически снизился. Но "общественность" этот проект успешно зарубила. Я тогда же задался вопросом: насколько повысится уровень Каспийского моря, если всю тогдашнюю общественность - максимум 290 млн человек - целиком утопить в этом самом море? Оцените, вы удивитесь.
До ВОСР в арифметических задачах "героями" были купцы, аршины и т.п.
Во времена СССР - пионеры, субботники и т.п.
После 2014 года стали основными героями НЕсогласные = "общественность" - здорово прилумали.

А все потому, что проигнорировали вселенсконатуральное....

Математика для чайников №3 20 Март 2017 19:30 #625

  • инфолиократ
  • инфолиократ's Avatar
+ Учителю бывшего учителя, ЗА
ВТОРОЙ пример игнорирования вселенсконатурального:
-- Представьте себе Байкал, из которого никакая Ангара не вытекает, и никакой Баргузин в него не впадает. Просто гигантское озеро с фиксированным объемом воды. А на берегу сидит Конфуций и пытается вычерпать Байкал наперстком. Причем не просто черпает каждый раз по наперстку, а уменьшает дозу: сначала целый наперсток, потом половинка, потом третья часть, потом четвертая... Так представляете -- рано или поздно он ведь его полностью вычерпает! Именно это мы с вами сейчас доказали.

А вид у него был мечтательный, повторю

Quote Selected
Воронеж - це Європа!
...
Хайдук's Avatar

ув. инфолиократ вычерпанию Байкала не поверит :lol:

Last Edit: 17 Март 2017 18:44 by Хайдук.

onedrey's Avatar

Он просто не видел Конфуция

Этта математика хороша для проведения народных референдумов. Арифметика жизни предполагает, что Вселенсконатуральное это такое число, которое предполагает расположение ВСЕХ
абстрактных
объективных
субъективных
дискретных (с точностью до 10 в минус 50й степени) единиц в одну прямую линию....

Короче, "посоветовавшись с Конфуцием- благодаря ГИ есть такая отдельная тема на КФ", отвечу вопросом на вопрос:
1.Разве Конфуций вычерпывал бы последню молекулу воды ДОЛЬШЕ, чем све озеро Байкал?
2.Разве Конфуций считал бы ВОДУ в количестве меньше молекулы ВОДОЙ?
3. кнс= каждый напишет свое(с), ув. самоед может легко подсчитать количество молекул воды...

З павагай к реалистам

Математика для чайников №3 20 Март 2017 19:45 #626

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 62406
  • Thank you received: 540
  • Karma: 65
Дорогой инфолиократ, эта тема Математика для чайников, а не сумбурные мысли по поводу.
Каждому - своё.

Математика для чайников №3 21 Март 2017 04:20 #627

  • самоед-3
  • самоед-3's Avatar
  • OFFLINE
  • Окольничий
  • Posts: 856
  • Thank you received: 15
  • Karma: 4
Да, насчет молекул воды справедливое замечание. Тот "лектор - большой математик" считал, что вода непрерывна, а не дискретна, и не предусмотрел, что еще до исчерпания Байкала наперсток может уменьшиться настолько, что молекула воды просто в него не влезет и тогда Конфуций, работая впустую, не закончит свою работу НИКОГДА! Либо начальный наперсток должен быть достаточно объемным и, может быть, даже неподъемным для Конфуция. Надо бы проверить.
Last Edit: 21 Март 2017 04:21 by самоед-3.

Математика для чайников №3 21 Март 2017 12:55 #628

  • самоед-3
  • самоед-3's Avatar
  • OFFLINE
  • Окольничий
  • Posts: 856
  • Thank you received: 15
  • Karma: 4
Один моль воды имеет объем 18 мл и содержит 6 на 1023 молекул воды. Значит, объем молекулы воды = 3 на 10-23 мл. Отсюда наперсток начальным объемом 1 мл уменьшится до объема молекулы воды за t = 1023/3 секунд, если Конфуций будет работать со скоростью 1 наперсток в секунду. И за это время он вычерпает ~ ln t мл воды, т.е. ~ 50 мл, смех.

Математика для чайников №3 21 Март 2017 14:06 #629

  • самоед-3
  • самоед-3's Avatar
  • OFFLINE
  • Окольничий
  • Posts: 856
  • Thank you received: 15
  • Karma: 4
Вот полезный совет, я сам им все время пользуюсь. При оценке чего-то по порядку величины удобно считать, что "год", все равно какой, 365 или 366 дней, довольно точно составляет 107.5 и даже 107.50 секунд.

Математика для чайников №3 22 Март 2017 03:30 #630

  • Grigoriy
  • Grigoriy's Avatar
  • NOW ONLINE
  • Боярин
  • Posts: 10779
  • Thank you received: 238
  • Karma: 11
Вспомнился этот разговор:
quantoforum.ru/mathematics/131-matematik...-2?start=1350#317575 #362

Задал яндексу

Перельман Стендаль яйцо алгебра

и сразу получил
mathemlib.ru/books/item/f00/s00/z0000003/st080.shtml
Рейтинг@Mail.ru Яндекс цитирования