Ну так что же всё-таки такое эта ваша компутер сайенс? Из примеров непонятно.
Наука о компухтерах же. Как их использовать с точки зрения разработчика(анализ алгоритмов и структур данных - к примеру). Дискретка близко стоит т.к. комухтер оперирует дискретными структурами(в т.ч. числами с конечной точностью). Потеоретичнее - вычислительные модели, их эквивалентность, сводимость известных алгоритмов к ним.
>вычислительные модели, их эквивалентность, сводимость известных алгоритмов к ним.
Уже интереснее. Примеры?
Уже интереснее. Примеры?
О, годный тренд!
> почему локальные переменные во всех(или почти всех) известных языках хранятся на стеке?
Осмелюсь предположить, что основная причина - удобство использования значений переменных при различных вычислениях. К примеру, при сложении двух чисел их сначала помещают в стек, потом достают, складывают, а результат помещают обратно в стек (как в RPN).
Машина Тьюринга, нормальные алгоритмы Маркова, конечные автоматы, лямбда-исчисление. Тьюринг-полнота языков программирования/других вычислительных моделей.
https://ru.wikipedia.org/wiki/Модель_вычислений
Еще до кучи различные модели параллельных вычислений, алгоритмов и структур данных
https://ru.wikipedia.org/wiki/Параллельные_вычисления
Какое в CS определение натурального числа?
Этим математика занимается. CS использует математику, а не придумавает новую.
у вас свой загон есть, оставайтесь и не вытекайте
Нахуй иди, нубло. Я тут пытаюсь кластеризацию изображений оптимизировать, а он мне какие-то детские задачки пихает. Видно студентику начали курс читать.
Я "детские" задачки вкинул для привлечения внимания, если что - мой уровень повыше гораздо будет.
А у тебя видимо там совсем всё горит, раз так рвёшься. Оптимизатор мамкин негодует.
Спасибо, ОП. Буду дома, поддержу тред.
Спрашивайте пока за криптографию, сложность алгоритмов, теорию чисел, вот это вот все. Приду - отвечу. Может даже за квантовые вычисления поясню.
тот самый анон из маттреда
Забыл добавить - как правило именно такие зазнавшиеся снобы порой не могут простейших задач на соображение/понимание фундаментальных вещей решить.
Сука в голос
Ну раз уж на то пошло, то натуральное число - это массив 32х-битных целых(ну или байтов), при условии неограниченности памяти машины.
unsigned int.
Неверно. unsigned int может быть нулем.
никто не мешает не использовать 0, либо интерпретировать его как 1 путём прибавления ;)
Мне видится основной проблемой то, что примитивные типы имеют границы диапазона значений, тогда как натуральное число может быть сколь угодно большим.
0 - натуральное число.
Пошла толстота. Ну хоть 14 постов продержались.
Что не так?
Почему 0 по твоему мнению не натурально число?
По определению. Хотя если определить по-твоему, то будет натуральное число. Короче, делай что хочешь, определяй натуральные числа как хочешь, хоть усрись.
Потому что 1 не следует ни за каким натуральным числом.
Мне кажется, 0 - не натуральное число:
1. По историческим соображениям.
2. Это число нейтральный элемент относительно +, это его основное свойство, мы же арифметику пока не вводили.
А вообще, давайте разговаривать по теме треда(попробуйте ответить на ОП-вопросики, например) а не очередной N-срач разводить в совершенно неподходящем для этого месте(я конечно понимаю, это всё забавно, но таки...)
Что интересно, сам Пеано не считал нуль натуральным числом.
https://archive.org/details/arithmeticespri00peangoog
Заебали, съебите в свой загон.
Будут внятные попытки ответа на ОП-вопросы? Это сорт оф тест на CS-грамотность обосцая.
Видимо ты не понял вопроса. Локальные переменные служат не для "вычислений", сколько являются моделью хранения временных(имеющих "фиксированный" срок жизни и ограниченную область видимости) значений. Так всё-таки почему локальные переменные хранятся на стеке, а не в другой структуре данных - например, векторе или связном списке?
Видимо ты не понял вопроса. Локальные переменные служат не для "вычислений", сколько являются моделью хранения временных(имеющих "фиксированный" срок жизни и ограниченную область видимости) значений. Так всё-таки почему локальные переменные хранятся на стеке, а не в другой структуре данных - например, векторе или связном списке?
Потому что на стеке быстрее будет работать (промежуточные вычисления становятся мусором сразу же после вычисления нужной штуки, в стек они складываются по порядку, и с этого же конца удаляются -> минимум операций, а поскольку это самый низкий уровень, то выигрыш будет значительный) и на стеке проще реализовывать (взять хотя бы пример выше - кидай в стек, забирай из стека, проще не придумаешь, не надо ни запоминать ничего, ни перемещать). Короче, для дженерик компутера это самая эффективная структура (для какой-нибудь экзотики может и нет).
В принципе ты прав. Дополню - при использовании стека адреса локальных переменных фиксированы относительно верхушки стека. А это очень большой профит - обращаться к переменной по фиксированному адресу, без всяких промежуточных идентификаторов, указателей и.т.д. Т.к. делаем мы это часто(читаем/пишем в переменную) выигрыш существенный. В связи со стековой моделью - блоки кода должны быть "правильными", нельзя закрыть произвольный блок кода - мы закрываем их всегда в обратном(LIFO) порядке. В том же порядке извлекаются/удаляются локальные переменные, теряющие "область видимости".
Мне не очень понятно, что означает слово "информатика"? Складывается ощущение, что это просто всё то, что "интересно чувакам угарающим по компам", начиная от P=NP и прочей глубокой комбинаторики, и заканчивая менеджментом и дизайном пользовательских интерфейсов.
>информатика
Ну или СS, тот же вопрос.
Ну или СS, тот же вопрос.
Тащемта так оно и есть. Информатика - очень размытое в нашей стране понятие, в то время как Computer Science подразумевает вполне конкретную и осязаемую вещь. Правда, там много чего "из смежных областей", той же дискретки. А вот что-то вроде
>заканчивая менеджментом и дизайном пользовательских интерфейсов.
непосредственно относится к разработке ПО, это чисто прикладной аспект - что-то вроде "ремесла". Хотя в той или иной степени программирование опирается на "науку", кодить(как и оперировать, судя по поговорке впрочем) можно научить и обезьяну.
>Вопрос ньюфагам на понимание - почему локальные переменные во всех(или почти всех) известных языках хранятся на стеке?
Потому что деревья удобно обрабатывать рекурсией, а без стека рекурсию можно получить только напердолив стек вручную. Стека нет в фортране, например, за что его любят там, где хотят знать точный размер занимаемой программой памяти заранее. В сишке то же самое эмулируется использованием ключевого слова static.
Потому что деревья удобно обрабатывать рекурсией, а без стека рекурсию можно получить только напердолив стек вручную. Стека нет в фортране, например, за что его любят там, где хотят знать точный размер занимаемой программой памяти заранее. В сишке то же самое эмулируется использованием ключевого слова static.
Причем надо сказать, что это используется при программировании на тайплевеле.
>Потому что деревья удобно обрабатывать рекурсией
Я имел в виду локальные переменные в отрыве от передачи параметров и рекурсивного вызова функций. И стек как раз ограничен по размеру - даже в C, обычно его размер фиксируется в compile-time(есть даже параметр компилятора вроде, задающий верхнюю границу размера стека, также зачастую можно прикинуть максимальный возможный размер по коду программы(максимальное значение если пройтись по всем возможным разветвлениям кода - рекурсия является исключением), поэтому он может переполниться. Сомневаюсь, что в фортране нет стека - впрочем с фортраном я не знаком.
>Я имел в виду локальные переменные в отрыве от передачи параметров и рекурсивного вызова функций.
Без рекурсии стек не нужен.
Так тогда на чём хранятся локальные переменные по твоему? В сферической программе в вакууме, имеющей только единственную функцию main(), и допустим определенное количество вычислений и ветвлений(if/switch).
Смотря в каком языке. В языке, поддерживающем рекурсию, на стеке - просто на всякий случай. В фортране - в статической памяти, т.е. по сути они являются глобальными переменными, но видимыми только из конкретной функции. Вот тебе пример функции, которой стек не нужен: http://ideone.com/bPkswF
В статической памяти - под этим как правило понимается стековая структура именно для локальных переменных, а не глобальных. Стек выбран по причинам приведенным выше(эффективность и простота). Именно поэтому существует понятие "блока кода"(LIFO порядок "уничтожения" локальных переменных). Даже в ASMе есть push и pop для переменных(как и в выхлопе компиляторов). Есть конечно еще регистры процессора - но их как правило мало (хотя бы на той же x86 архитектуре), все переменные в них не сохранишь.
Т.е. никто не пишет специальный проверяльщик, который детектирует, что в программе нет рекурсии и все переменные могут быть статическими. Потому что в общем случае это невозможно. Например, ты отправляешь в dll, исходного кода которой у тебя нет, указатель на функцию, а этот указатель на функцию опять вызывает нужную dll. Т.е. рекурсия появилась сама и компилятор о ней не знает. Поэтому стек используется везде. Но В ПРИНЦИПЕ дело только в рекурсии. Нет рекурсии - не нужен стек. Есть рекурсия - нужен.
В твоем примере добавить бы десяток-другой переменных - куда ты их денешь, кроме как в стек? Еще можно добавить блоки кода, для демонстрации "удаления" локальных переменных из стека. Уверяю тебя, что на выходе будут ASM-инструкции push и pop(по крайней мере на x86).
>В статической памяти - под этим как правило понимается стековая структура именно для локальных переменных, а не глобальных.
This is simply a lie. В модели памяти С есть 3 типа памяти, статическая (существующая до начала работы программы), автоматическая (стек) и динамическая (malloc/free). Никакой стековой структуры под статической память не подразумевается, вообще нет, НЕТ. Стек реализован в железе (на уровне push/pop и регистра esp) потому что рекурсия - важная штука.
Тогда выскажи свою версию того, в какой структуре/формате хранятся локальные переменные, если их больше, чем регистров в каком-либо блоке кода.
static int i в моем примере хранится в статической памяти, т.е. по сути является глобальной переменной, у которой область видимости ограничена.
Обрати внимание, что stack overflow не возникает:
http://ideone.com/uI2uCM
Потому что stack тут собственно не используется.
Но на подобном рекурсию уже не построишь, так как локальные переменные шарятся между вызовами.
Ты прав насчёт того, что локальные переменные можно хранить как глобальные("в статическом хранилище") - они будут жить пока работает программа. Стек же позволяет держать в памяти только локальные переменные, обозримые в данный момент(точке исполнения).
http://ideone.com/siaY9V
Аналогично. Ты думаешь, что стек даден нам свыше, а первых языках его не было, это ответ именно на возможность рекурсии.
Да, пожалуй ты прав - может в древности стек не юзался а память распределялась под все локальные переменные, независимо от "блоков кода" и видимости(scope). Но это же приводит к выделению избыточного количества памяти.
Зато память заранее размечена и ты знаешь, что твой спутник не упадет со stack overflow. Вот тут написнао лучше, чем я могу сказать http://users.ece.cmu.edu/~koopman/stack_computers/sec1_4.html
Да, теперь я понял, что не был в курсе истории и спроецировал старый добрый C+x86 на всё и вся. Спасибо за ликбез. Век живи - век учись.
Надо сказать, что на современных спутниковых приборах юзают сишку или асм с локальными переменными на стеке и прибор упасть со stack overflow может. Но лет 5 назад мне какой-то аутист в /c/ доказывал, что это неебовое преимущество фортрана.
Если нет рекурсий и прочей еботни можно же просчитать максимальную глубину стека - просто обойдя все возможные ветки кода. А про преимущество фортрана - ничто не мешает скомпилировать C "без стека" или с огромным стеком заведомо непереполнимым. Опять же если нет рекурсий/больших аллокаций на стеке. Глубина рекурсии тоже должна иметь максимальную границу - исходя из возможных/допустимых вариантов входных данных. Хотя наверное "без стека" обойтись таки мешает сам стандарт языка с рекурсией и прочими плюшками :)
Вот на этом невысказанном предположении и держится весь хрупкий механизм нашего молодого народовластия.
Третий раз на саентаче вижу этот пелевенизм, при этом сейчас он совершенно не в кассу. Либо он становится моднявым, либо тут какой-то поехавший, пихающий его к месту и не
Да полно таких невысказаных предположений на самом деле. Программа же может повалиться и при нехватке динамической памяти, при некорректных данных, не учтённых спецификацией и.т.д. Недаром же Дейкстра предлагал перекатываться в доказательное программирование. Но на практике это уж слишком, даже для ядрёных реакторов имхо.
Даже Тьюринг со своей проблемой остановки мягко намекнул - спутники будут падать, а ядрёны реакторы взрываться т.к. нет универсального автоматического способа удостовериться в корректности программы. Человек же - главный источник ошибок - как в случае создания программ, так и их тестирования/отладки.
Определить глубину рекурсии в общем случае проблема, эквивалентная проблеме остановки. Т.е. "Глубина рекурсии тоже должна иметь максимальную границу" - невысказанное предположение.
Для этого в CS начали искать языки, которые не Тьюринг-полные, но при этом достаточно мощные. В таких языках рекурсия разрешена только тогда, когда точно известно, что она завершится. Это - всяческие пруф-ассистанты. На таких языках формальные свойства алгоритмов доказываются просто, а программы можно писать достаточно мощные, чтобы АЭС работала. Подробнее тебе расскажут https://2ch.hk/pr/res/483770.html тут.
Предчувствую какое-то очень сильное колдунство, в котором мне только предстоит разобраться.
Кстати, поясните за квантовые вычисления. В них "квантовое" ускорение достигается за счёт связанности состояний кубитов или чего-то другого? Возможно ли построить что-то аналогичное без квантов?
Раз уж тут такой тред - спрошу. Где можно почитать про программирование Машин ТЬюринга в 4-ках? Ну чтобы кратко и понятно , с примерами программ.
И, если не трудно, подскажите алгоритм перевода из 2-ой системы счисления в восьмеричную, на МТ, конечно. Я пока придумал считать триадами, но это дохуя геморно, надо же каждый случай прописать + не все же числа будут иметь по 3,6 цифр. Это моя лаба кстати.
И, если не трудно, подскажите алгоритм перевода из 2-ой системы счисления в восьмеричную, на МТ, конечно. Я пока придумал считать триадами, но это дохуя геморно, надо же каждый случай прописать + не все же числа будут иметь по 3,6 цифр. Это моя лаба кстати.
Алсо, надо чтобы это работало с логарифмической сложностью.
Квантовые вычисления умеют считать то же, что и обычные (никаких сверхтьюринговых вычислений), но за счет квантовых эффектов параллельно позволяют запустить алгоритм для всех возможных входных значений. Построить можно, только будет мэдлэнно.
Как можно перевести число в другую систему счисления с логарифмической сложность? Тебе нужно считать все разряды входного числа, что уже линейная.
Ну вот задание такое, воот.
Мне кажется - также как и отсортировать массив за логарифм. Impossibru.jpg в общем случае(имхо и без пруфов, рад заблуждаться). Можно оптимизнуть что-то в оригинальном алгоритме(например - распараллелить, считать блоками через lookup table), - но скорость будет ~ линейной, разница будет только в константе. Либо заточить как-то(хз как) под специальный вид входных чисел.
я вот тоже не понял вопроса. сколько листинги не читал выглядит так что в стек их помещают на уровне ассемблера. все эти пуш-пуш-пуш кал попопоп. из лекций по устройству машин я помню что стек нужен только за тем что бы переключать контексты при многозадачности и виртуальной памяти. тоесть указатель и стек дампаются пока снова не понадобятся. а потом прост копируют сохраненный указатель и он дальше инкрементирует. так что осмелюсь предположить так как точно не помню и не знаю что локальные переменные если помешаются идут в кеш проца так как дергать их из оперативки раз в сто медленнее.
регистров овердохуя между прочим. вот для арифметики их всего четыре вроде. но ведь есть еще и асики на кристале. тоесть все эти ссе и прочие навороты.
статическая переменная во всех си образных языках указатель на область памяти в которой гарантированно присутствует искомая дата на всем протяжении выполнения программы. в отличии от инстансируемых обьектов которые сейчас существуют а через пару тиков их уже нет а на их месте что то ещё.
Бред пишешь, мелкобуквенный.
в смысле? сначала сделали процы. тогда же договорились использовать стек. теперь какие то фантазеры ищут глубинный смысл в этом всем. можно хоть графы использовать на самом деле. только вот разработка и проектирование в копеечку влетят. может в миллион человеко часов а может в миллиард.
алсо всегда раздражало когда вижу вот такие вспездывания.
>бред пишешь, ссу на ебальник (смех).
кому вы все это пишете ебланы?
если соберешься говорить по существу послушаю/почитаю твою версию того что хранится в кеше процессора.
А почему ты мелкобуквенный? Глаза вытекают, тебя неудобно читать. Если тебе нужна подсказка, то выясни, в каком году у процессоров появился стек, а в каком - MMU.
>языки, которые не Тьюринг-полные, но при этом достаточно мощные. В таких языках рекурсия разрешена только тогда, когда точно известно, что она завершится.
Ээ, падажжи-ка. Я тут немного посмотрел за языки с зависимыми типами, идрис этот ваш, Coq, хачкель из этой жи оперы?, я правильно понял, что на них можно писать нечто абсолютно надежное и на 146% безглючное? Это разве не новая эра в программном обеспечении - идеальный код, от ОС до прикладного софта?
Формальная верификация даст тебе 100% соответствие спецификации, но кто тебе сказал, что в спецификации у тебя не было ошибок? АЭС лучше проектировать так, чтобы любая ошибка в софте не вызывала больших проблем, а не надеяться на то, что в софте нет ошибок.
>кто тебе сказал, что в спецификации у тебя не было ошибок?
Но ведь любую спецификацию можно свести к исчислению предикатов на основе аксиом ZFC, что тоже легко проверяется теми же пруф ассинтантами, не?
>Но ведь любую спецификацию можно свести к исчислению предикатов на основе аксиом ZFC
Бурбаки пытался - у него в точном определении числа 1 получилось 2 409 875 496 393 137 472 149 767 527 877 436 912 979 508 338 752 092 897 знаков.
Здесь получается бесконечная цепочка: чтобы найти ошибки в модели, нужна спецификация, чтобы найти ошибки в спецификации, нужна спецификация спецификации и т. д. и т. д. Так или иначе, конечную спецификацию составляет человек, который... подвержен ошибкам. Приплыли.
>А почему ты мелкобуквенный?
сам не знаю уже лет пять мелкобуквенный. наверное я просто презираю некоторые сорта людей. правила созданы людьми для людей. для удобства а не для поклонения.
>Глаза вытекают, тебя неудобно читать.
чего еще ждать от людей воспитанных в тоталитарной параше. спасибо что баб без паранжи не закидываете камнями. хотя стойте, нет. травите ведь любую более менее шлюху.
>Если тебе нужна подсказка,
и под конец опять же с изрядным количеством желчи разгорор по существу. посмотрел. и все понял. спасибо.
пРавИлА созДАнЫ дЛя уДоБстВа
Есть удобство печатающего, есть удобство читающего. Ты считаешь, что твое удобство важнее моего, потому что являешься хуежопым мудаком, пытающимся выделиться. То, что ты за пять лет не поумнел - это твоя проблема. Рекомендую еще писать без пробелов, и удивляться, почему тебя нахуй шлют "с изрядным количеством желчи".
Есть удобство печатающего, есть удобство читающего. Ты считаешь, что твое удобство важнее моего, потому что являешься хуежопым мудаком, пытающимся выделиться. То, что ты за пять лет не поумнел - это твоя проблема.
еслибыятаксчиталтыбычиталэто
Школьник воннаби-программист вкатился.
Где в айти нужны не быдлокодеры, а люди, знающие математику и умеющие думать? Чтобы работать там, в какой из вузов (московских) стоит поступать, на кого и почему?
Посоветуй литературы по криптографии.
Где в айти нужны не быдлокодеры, а люди, знающие математику и умеющие думать? Чтобы работать там, в какой из вузов (московских) стоит поступать, на кого и почему?
Посоветуй литературы по криптографии.
computer vision, signal processing, machine learning. Поступай в любой ненапряжный вуз и занимайся самообразованием.
В криптографии рабочих мест нет, ты же не собираешься алгоритмы разрабатывать.
финансовый софт, но тут тонкий момент: алгоритмы там обычно фигачат ребята со степенями, а код пишут быдлокодеры с улицы, разделение обязанностей ёпта
Не забудь еще про то что нужны единицы ребят со степенями и тысячи крудошлепов. Рыночек порешал, да.
Там мозгов не очень много нужно.
Антуаны, посоветуйте, пожалуйста. Мне нужно выбрать магистратуру. Я угораю по двум направлениям: математическая физика и CS (ИИ+робототехника). С одной стороны очевидно, что матфизик- это работа исключительно научного сотрудника с соответствующими вытекающими в виде низкой з/п, публикаций и необходимости преподавания в университете, но с голубой мечтой защитить PhD, обобщать и познавать реальный мир. С другой стороны лежит развитие в Computer Science с тем же набором опций, но которая располагает к прикладному программированию, мобильности и зп выше среднего.
По уровню моего развития: в программировании уже есть научные наработки в computer vision, а в физике только сданный курс и чтение Сивухина на пару с Ландау.
Сам же иногда ловлю себя на мысли, что живу в черезчур идеализированом мирке, верю в светлое будущее разумных роботов, искусственного интеллекта и сингулярности. Возможно ли, что я просто зеленый юнец и эта пелена скоро спадет, а я сниму розовые очки среднестатистическим среднепрограммистом?
>>>301796 (OP)
Ещё и здесь наложил.
То, что тебе стала интересна физика- не значит, что ты сможешь ей заниматься. Ты точно осознаешь, что это такое? Добро пожаловать в конец пищевой цепочки- физики провели эксперимент, принесли тебе результаты или ещё лучше сам его нашёл в интернете, т.е. тебя никто об этом не просил, а ты его обосновываешь в мат терминах.
Смотрел в глаза ученых математиков физиков? Как ты умаешь, почему у них глаза как будто мертвые, стекляные, а говорят так меееееееедленно, с паузами? Они же сумасшедшие. Да и то, что он несут- это же пиздец, никому ненужное бесперспективное дерьмо. Если ты задаёшь такой вопрос и сомневаешься в выборе научной карьеры- забудь. Реально забудь об этом, это для остервенелых шизиков ноулайферов онли.
Ещё и здесь наложил.
То, что тебе стала интересна физика- не значит, что ты сможешь ей заниматься. Ты точно осознаешь, что это такое? Добро пожаловать в конец пищевой цепочки- физики провели эксперимент, принесли тебе результаты или ещё лучше сам его нашёл в интернете, т.е. тебя никто об этом не просил, а ты его обосновываешь в мат терминах.
Смотрел в глаза ученых математиков физиков? Как ты умаешь, почему у них глаза как будто мертвые, стекляные, а говорят так меееееееедленно, с паузами? Они же сумасшедшие. Да и то, что он несут- это же пиздец, никому ненужное бесперспективное дерьмо. Если ты задаёшь такой вопрос и сомневаешься в выборе научной карьеры- забудь. Реально забудь об этом, это для остервенелых шизиков ноулайферов онли.
=>>
оставь это лучше своим хобби
Ну пиздец теперь, стек им для обхода деревьев и удобства адресации.
Будто bfs/pfs шибко менее востребованы, нежели dfs.
Будто относительная адресация удобнее абсолютной.
Static им для экономии памяти, вообще охуеть, что несут?(foo() {static char buf[100500];} bar() {static char buf[100500];})
Привыкли к RAM, историю знать не хотят, хотя всё железо пропитано рудиментарным легаси-идиотизмом. Даже абстрактная машина .NET использует стековую модель памяти исключительно в силу соображений упрощения трансляции (благо в аппликативных вычислениях теория хорошо проработана).
А почему стек один, только для данных? Почему операции - в очереди? Про Форт ещё что-нибудь рассказывают на вашем первом курсе?
Блоки кода, порядок уничтожения... сука, крестоблядство конструкторов-деструкторов уже абсолютизируют до уровня всеобщности. Ни сопрограмм, ни замыканий не знают.
Идите в пизду /pr/. Пожалуйста.
И этот ваш Computer Science: "... first of all its not a science. ... Its not really much about computer" (c)Harold Abelson
Будто bfs/pfs шибко менее востребованы, нежели dfs.
Будто относительная адресация удобнее абсолютной.
Static им для экономии памяти, вообще охуеть, что несут?(foo() {static char buf[100500];} bar() {static char buf[100500];})
Привыкли к RAM, историю знать не хотят, хотя всё железо пропитано рудиментарным легаси-идиотизмом. Даже абстрактная машина .NET использует стековую модель памяти исключительно в силу соображений упрощения трансляции (благо в аппликативных вычислениях теория хорошо проработана).
А почему стек один, только для данных? Почему операции - в очереди? Про Форт ещё что-нибудь рассказывают на вашем первом курсе?
Блоки кода, порядок уничтожения... сука, крестоблядство конструкторов-деструкторов уже абсолютизируют до уровня всеобщности. Ни сопрограмм, ни замыканий не знают.
Идите в пизду /pr/. Пожалуйста.
И этот ваш Computer Science: "... first of all its not a science. ... Its not really much about computer" (c)Harold Abelson
Кажется, знаток программирования протёк. Уносите - его уже не починить, нужен новый.
В ключевом он прав
>Идите в пизду /pr/.
Нет, не прав. В /pr в основном макаки, не имеющие представления о Computer Science. Тут же можно обсудить вопросы CS, не относящиеся к прикладной разработке ПО. К примеру, кто что знает о связи проблемы останова машины Тьюринга и теоремы Гёделя?
Аутист, ты выдумал какой-то манямирок утверждений, которых ИТТ не было, и начал их опровергать. Проследуй сам нахуй.
>кто что знает о связи проблемы останова машины Тьюринга и теоремы Гёделя?
будда.jpg
Тут уже говорилось, что CS нихуя не наука?
Говорилось. Но чем же CS хуже, чем любая инженерная/техническая наука?
Тащемта CS - раздел математики, а математика - не наука.
Это не раздел математики, а разнообразные применения математики в определенной тематике. Назвать это чем-то целостным, типа раздела нельзя.
Лол. Курица - не птица, математика - не наука, ппц.
А чем та же электротехника, теплотехника, сопромат и прочие инженерные науки лучше? У CS таки есть целостность имхо - даже если перечислить разделы, их что-то объединяет. А именно то, что их относит к computer. Сорри за тавтологию.
Всегда нужно эмигрировать на запад. И да, ты понятия не имеешь, что такое матфизика,так что пиздуй в своё гомокс
>К примеру, кто что знает о связи проблемы останова машины Тьюринга и теоремы Гёделя?
Таки эти проблемы связаны. Я просто в одной книжке встречал немножко об этом, и чё-то вспомнил. Еще связанная проблема - проверка формальных(математических) доказательств. Можно ли построить систему, проверяющую - верно поданное в формализованном виде доказательство математической теоремы или нет, если нет - то где ошибка. На хабре целый срач на эту тему был. Проблема довольно актуальная т.к. последние важные "теоремки" могут иметь порядка 1к страниц доказательства, которые проверять очень затруднительно.
>А чем та же электротехника, теплотехника, сопромат и прочие инженерные науки лучше?
Тем, что там эксперимент на первом плане. А в CS экспериментов нету, а есть умозрительные построения из машин с бесконечной памятью.
>Можно ли построить систему, проверяющую - верно поданное в формализованном виде доказательство математической теоремы или нет, если нет - то где ошибка.
Как два пальца обоссать.
Ты перепутал задачу проверки доказательства с задачей самого автоматического доказательства.
Наверни уже Смаллиана, Принцесса или тигр, часть четвертая.
Кончайте хуйню нести. CS изучает две вещи и все с ними связанное: 1) вычисление 2) информацию. Капмутер сайенсом она называется простопотомучто.
Под теоремой я понимаю не теорему исчисления предикатов, а произвольную математическую теорему, формулируемую в терминах определенного раздела математики. Также просто? Имхо, тут нет явной эквивалентности, потому что мы спускаемся на уровень термов и отношений между ними.
Бумп годному треду.
По криптографии читай то, что понравится. Всякие фольклорные основы типа RSA, AES и прочих Диффи-Хеллманов есть везде. А дальше сам поймешь, что тебе интереснее - более глубокая криптологическая экзотика типа электронного голосования, CS-ный анализ сложности алгоритмов или математика со всякими решетками и гиперэллиптическими кривыми. По памяти могу посоветовать Stinson - Cryptography: Theory and practice
>или математика со всякими решетками и гиперэллиптическими кривыми
Лал тупые сосачеры такое не осилят.
мимо математик
Но ведь... ты тоже сосачер, хоть и математик. Тоже ниасилил?
И всё таки Computer Science это очень широко. Очень.
image-processing сноб
image-processing сноб
Компьютер - тоже штука очень "широкая", сложная и универсальная. Жиза.
А где же data-analysis хипстеры? Поднимите руку
Давайте устроим цирк как в маттреде и попытаемся дать определение понятию информации. А то что-то изучаем, а что - не знаем.
Сначала надо формализировать и перевести в удобоваримый вид слова "понятие" и "определение".
>А где же data-analysis хипстеры? Поднимите руку
Анализ данных это не только главные компоненты. Но и много алгоритмов, которые местные дурачки по одним им ведомым причинам относят к "нейросетям". Стоит только упомянуть что-то такое, что они могут отнести к нейросетям и начинается. Завоют так, глаза закатят и начинают визгливо кукарекать. Плавали, знаем.
Это если бы мы были в /ph. А так нам просто нужно определение, худо-бедно формализующее те риал-лайф случаи, когда мы этим понятием пользуемся. Например, когда мы говорим, что такое-то высказывание не даёт нам никакой информации - что мы имеем в виду?
Есть определение информации в рамках теории информации. Но оно не совсем то - оно завязано на вероятностную модель источников/каналов.
Вообще информация мне представляется неопределяемым понятием, но которое можно пояснить разными способами.
Например, информация - это смысл чего-то(способ интерпретации последовательности битов, к примеру) или знание о чём-то. Но это скорее пояснение, а не определение.
Каждый первый в /sci/ делит публику на 2 множества:
1. Я, любимый.
2. Местные дурачки (тупые сосачеры и т. п.)
Каждое из которых в свою очередь может подразделяться на подмножества.
Таким образом каждый сосачер естественным образом задаёт топологию на множестве сосачеров. Какую математическую структуру представляет собой сосач?
Может за структуры данных побазарим? Я вот одно время интересовался структурами данных во внешней памяти(на жёстком диске н-р) т.к. хотел написать программу с хранением сущностей и оперированием с ними по типу реляционных БД, но без БД(схема была довольно простой).
Вот, к примеру - как хранить в файле строки переменных размеров(максимальный и минимальный размер строки известен) с id, чтобы CRUD с ними был достаточно эффективен(будем рассматривать асимптотическую оценку сложности)?
Вот, к примеру - как хранить в файле строки переменных размеров(максимальный и минимальный размер строки известен) с id, чтобы CRUD с ними был достаточно эффективен(будем рассматривать асимптотическую оценку сложности)?
>программу с хранением сущностей и оперированием с ними по типу реляционных БД, но без БД(схема была довольно простой).
Ты изобрел nosql, в частности - key-value хранилище типа tokyo cabinet (не redis, потому что redis хранит данные в памяти и только скидывает их на диск). http://fallabs.com/tokyocabinet/spex-en.html
Т.е. там три способа перечислены: хэш-таблица, btree (классика), и простая fixed-length таблича.
>как хранить в файле строки переменных размеров(максимальный и минимальный размер строки известен) с id, чтобы CRUD с ними был достаточно эффективен(будем рассматривать асимптотическую оценку сложности)?
Это одна из главных задач любой файловой системы. Вот про них и почитай, от FAT до extfs.
А вот и неправильно. Файл - всего лишь логически непрерывный кусок байтов на диске. Как ты организуешь структуру хранения данных в нём - совсем другое дело. Иначе понятия БД не существовало бы. Те же строки переменной длины можно хранить по-разному:
самый наивный способ - последовательно положить строки(аналогия с одномерным массивом), но тогда удаление строки требует переписать O(N) символов, N - длина файла. Добавлять можно в конец, увеличить длину строки на несколько символов - нужно опять-таки перепиливать весь файл.
Можно попробовать запилить в начале хедер с индексами строчек, далее непрерывный кусок для строк и распределять память на нём по аналогии с распределением памяти на куче, либо запилить что-то вроде дерева.
А вот и неправильно. Блочное устройство - всего лишь логически непрерывный кусок байтов на диске. Как ты организуешь структуру хранения данных в нём - совсем другое дело. Иначе понятия ФС не существовало бы. Те же файлы переменной длины можно хранить по-разному:
Файлы - это тоже абстракция, я не утверждал, что ФС не нужна. Но файлы не покрывают автоматически все проблемы со хранением структурированных данных для программиста, недаром же существует целые тематики "сериализация/десериализация", "базы данных и их внутреннее устройство" и так далее.
Блочное устройство - лишняя сущность. Любой логически непрерывный кусок байтов является файлом. /dev/sda гарантирует.
> покрывают автоматически все проблемы со хранением структурированных данных
Естественно нет.
Но
> хранить в файле строки переменных размеров
очень даже да.
Задача хранить множество изменяющихся, логически непрерывных кусков байт с переменными длинами, в другом логически непрерывном куске. Очень похожа на (и включает в себя) задачу хранить множество строк в файле.
Поэтому многие методы и решения из области файловых систем, могут быть успешно к ней применены и было бы неплохо с ними ознакомится.
Хранить строки в виде отдельных файлов в файловой системе, тоже вариант и нередко используется.
>Очень похожа на (и включает в себя) задачу хранить множество строк в файле.
Тут ты прав, в целом согласен, но есть отличия в задачах. В ФС много завязок на специфические особенности "абстрактного" жёсткого диска(например выбор размером блока именно 4К) и требований к ФС(безопасность/согласованность, журналируемость, максимально возможные размеры файлов).
Строки же у меня могут быть разными, я могу например иметь априорную информацию о распределении длин строк, минимальной/максимальной длине строки - как мне использовать её, чтобы повысить эффективность?
Если спроецировать задачу на ФС - хранить строки длиной, допустим, 30-512 байт(типичная чат/IRC мессага) с оверхедом блока ФС ~ 3.5К - это оверкилл. Поэтому задача всё-таки отлична.
Все - файл. ФС - один из типов БД. БД - не обязательно ФС.
Некоторые БД тоже учитывают особенности носителей данных. А некоторые ФС живут только в оперативке\сети или просто виртуальные.
Смотреть в первую очередь, естественно, лучше то, что подходит под конкретную задачу.
Данные о длине строк можно использовать для вычисления оптимального размера блока, как заранее, так и на ходу (динамический размер блока).
Проблему эффективного хранения множества маленьких файлов, как раз решали в ReiserFS. Блочное перераспределение, упаковка хвостов, хранение коротких файлов вместе с метаданными в дереве, вот это всё.
Подгоню примеров из жизни - хранение системных настроек в Windows - структурированная БД в виде реестра, хранимая в файле(или нескольких файлах) реестра. В Linux - разрозненные конфигурационные файлы в текстовом формате на базе ФС.
Имхо в винде более основательно подошли к этому вопросу, но linux в свою очередь был привязан к unix legacy.
Имхо в винде более основательно подошли к этому вопросу, но linux в свою очередь был привязан к unix legacy.
Я бы на твоем месте послушал:
И хранил бы по 1й строке в файле.
Что за псевдоязык, на котором пишут алгоритмы, где про него почитать?
В аппендиксе книжки не описания? Если хочешь также, гугли latex pseudocode, пакет типа algpseudocode.
>Таким образом каждый сосачер естественным образом задаёт топологию на множестве сосачеров. Какую математическую структуру представляет собой сосач?
Совершенно упорядоченное множество долбаебов?
Это, пожалуй, самое простое в плане реализации решение.
Представляю себе - лежит программка а рядом с ней файлы 1.txt, 2.txt, ... 9000.txt,...
Оверхеды, оверхедишки - особенно если строка сравнима или гораздо меньше блока файловой системы+оверхед на сам файл(имя и ненужные атрибуты).
забыл добавить - и строк достаточно много
Самое простое - взять tokyo cabinet и не выебываться. Самое нормальное - взять sqlite, ибо key-value имеет свойство превращаться в нечто большее.
А если я хочу разобраться, как устроен этот твой tokyo cabinet? И почему именно он, а не Berkley DB к примеру?
Кстати про B-деревья читал когда-то, но не понял почему там запись может быть переменной длины(вроде фиксированной длины она должна быть).
Да возьми что нравится. Но по tokyo я дал тебе ссылку, где в introduction описывается многое. Наверняка есть и книги о том как работают СУБД, да исходный код есть, наконец. По-моему анон тебе больше ничего не разжует.
Указываешь размер ноды внутри самой ноды и все, не ошибешься. Хотя вряд ли так делают, скорее переменные данные хранятся отдельно с доступом по указателю (т.е. по смещению в файле).
Так что таки хранится в B-дереве? Указатели(в терминах смещения от начала файла) на строки в отдельном сегменте, или сами строки?
Из вики:
>Структура B-дерева применяется для организации индексов во многих современных СУБД.
Везде речь о ключах, а не о "записях переменной длины".
Как хочешь, можно и то и то. Ты бы спросил, что эффективнее, а я бы тебе сказал идти почитать исходники и их описание. Потому что мне точно похуй, я свою СУБД писать точно не буду.
Ладно, спасибо. А чисто любопытствующего интереса нет к этому? Устройство БД, ФС? И вообще есть интерес ко всяким экзотическим/специализированным структурам данных?
Мне вот одно время хотелось разобраться в структурах для хранения геометрических данных, т.к. это связано с геймдевом - но так и забил, только поверхностно прошёлся.
Еще всплывал вопрос, о том, как хранить решётчатый граф, не храня связи между вершинами(например граф задающий гексагональную сетку и обобщения с n-связной решеткой)
Ну у меня общее представление есть (btree индексы, record pointer'ы, blob'ы), а частности лезть - зачем... Лучше почитать best practises о mysql, как там что оптимизировать. А, учитывая, что сейчас оперативка очень дешевая, то key-value средств языка плюс сериализация/десериализация - может быть достаточно.
Со структурами данных - здесь как в /wm/, задачи либо есть, либо нет. Нужно определиться, какое o(...) тебе нужно по скорости, какое - по памяти, и плюс железные вопросы типа cache friendly и т. п. 99% задач будет покрывать самое тупое, что можно придумать.
>например граф задающий гексагональную сетку и обобщения с n-связной решеткой
Да у тебя немного выбора, вроде. Равносторонними многоугольниками можно покрыть с n=3,4,6.
Прямоугольная сетка легко адресуется в памяти (т.е. одномерном массиве) с помощью простой арифметики: (i-1)line+j, (i+1)line+j, iline+(j-1, iline+(j+1).
В треугольной сетке добавится по 2 диагональных соседа (i-1)line+(j-1), (i+1)line+(j+1).
В шестиугольной - для четных и нечетных вершин будут разные формулы, лень писать. Тут вроде есть: http://stackoverflow.com/questions/5040295/data-structure-for-settlers-of-catan-map
>Да у тебя немного выбора, вроде. Равносторонними многоугольниками можно покрыть с n=3,4,6.
Я имел в виду не замощения плоскости, а "графовые" обобщения без геометрии - графы у которых количество соседних вершин у каждой вершины вершины = n, за исключением "краев" и "углов". Такие же существуют?
Еще вопрос - какие перспективы у nosql и нереляционных БД? Можно ли и существуют ли, к примеру нереляционные БД, у которой запросы будут в SQL/другом языке кодосгенерированы/скомпилены, без их "ручной" реализации или интерпретации(как в обычной БД, правда хранимые процедуры - это исключение, зависящее от реализации)?
Ну вообще да, соединительные линии не должны быть прямыми и равными, но для n=5 я сходу не могу представить. Можешь нарисовать?
Nosql любим хипстерами, которые не хотят разбираться в sql СУБД. Хотя любую sql-субд можно настроить так, чтобы она работала быстро (отключить лишние проверки, перенести таблицу в память и т. д. и т. п.), поэтому особого смысла их нет. В основе sql лежит математика - реляционная алгебра, в основе nosql лежит нихуя.
По поводу кодогенерации запросов не понял. Ты про ORM что ли?
Ну типа я хочу, чтобы SQL-запрос не интерпретировался(т.к. он известен в compile-time, разные там только подстановочные параметры), а скомпилился в машинный код на стороне сервера(возможно через хранимые процедуры это и сделано).
Суть nosql как я понимаю - производительность и то, что на них лучше ложатся некоторые модели данных(графовые данные к примеру - графовые БД), SciDB - для научных данных и.т.д.
Попробую - может попозже, не очень удобно в paint.net графы рисовать, в векторные редакторы не умею - но может выйдет что-нибудь.
Предварительно скомпилировать запрос можно везде.
>Суть nosql как я понимаю - производительность и то, что на них лучше ложатся некоторые модели данных
Суть nosql в том, что это кульное ничего не значащее слово. Лучше рассматривать конкретно. Графовые дб - это одно, key-value - другое.
Вопрос только - откомпилится запрос в байт-код или машинный? В машинный-то посложнее будет запилить, с точки зрения разработчика БД. Зато выигрыш в скорости будет.
Чем сложнее? Код и есть код.
Код и есть код, но компилятор компилятору рознь.
Мне кажется, определять информацию надо в терминах логики высказываний. Вообще информация, по моему субъективному представлению, может быть только у чего-то по отношению к чему-то, ведь один и тот же факт (высказывание) может нести полезную информацию по отношению к одному утверждению, и не нести никакой информации по отношению к другому. Колмогоровский подход через сложность объекта мне кажется неидеальным: да, чем сложнее объект, тем больше информации в нем можно разместить, но ведь она может быть не такой ценной, как в более простом объекте. К тому же такой подход не охватывает такую вещь как дезинформация, да и вообще описывает только количественные характеристики.
Короче, суть моей идеи такова: информация в высказывании A о высказывании B - это то, насколько упрощается вывод (доказательство) хотя бы одного из высказываний {B, не B}, если добавить высказывание A к системе аксиом. Соответственно условная информация - когда к системе аксиом уже было добавлено что-то.
Естественно, вывод утверждения может быть не один, и может быть более длинный, но более просто конструируемый на практике вывод, т.е. не одна лишь длина вывода может определять его простоту. В общем, надо обойти все подводные камни, чтобы сформировать годное определение.
>определять информацию надо в терминах логики высказываний
Логика высказываний - формальная логика, она не рассматривает смысл(семантику) высказываний, поэтому я думаю, эта попытка обречена на провал. Ведь по сути, информация, которую несёт высказывание - это её смысл. Ты же говоришь о том, как отразить связи/зависимости между высказываниями(какое-то высказывание может быть более общим, чем другое, либо быть связанным с ним) - на формальном уровне это отчасти отражается через "выводимость", на более глубоком уровне - необходимо спуститься до формулировки высказывания на языке термов(например, "Пошёл дождь", "На улице сыро" - это будут всего лишь A и B в терминах формальной логики, но если рассмотреть смысл - получим факт A|-B)
Можно попробовать доопределить её понятием "смысл высказывания", но мне, например, вообще непонятно как это сделать - вопрос как отразить смысловые структуры равноценен вопросу - как мы мыслим, что такое мышление.
>Можно попробовать доопределить её понятием "смысл высказывания", но мне, например, вообще непонятно как это сделать - вопрос как отразить смысловые структуры равноценен вопросу - как мы мыслим, что такое мышление.
Смысл - это функция. Функциональный график отображения наблюдаемого в речь (например, в знакосочетания письменной речи или в фонемы устной).
Мышление - тоже функция/набор функций. Что дальше будем делать? Понятно, что любое информативное высказывание должно обладать каким-то смыслом. Но что такое смысл по сути, как он получается и с чем его едят? Тут уже сложнее, потому что смысл определён в рамках "человеческой" логики, а не формальной.
>необходимо спуститься до формулировки высказывания на языке термов(например, "Пошёл дождь", "На улице сыро" - это будут всего лишь A и B в терминах формальной логики, но если рассмотреть смысл - получим факт A|-B)
Утверждение "если пошёл дождь, то на улице сыро" в данном случае заведомо истинно, мы можем считать его включенным в систему аксиом. Да, совершенно очевидно, что в зависимости от того, что уже известно, информация может быть как полезна, так и бесполезна.
Смысл будет неявно использоваться в определении - неподходящее по смыслу утверждение не уменьшит длину вывода.
Я акцентировал на то, что смысл и взаимосвязи между суждениями устанавливает человек, а не формальная теория - а ты говоришь о выводимости суждений относительно других суждений(т.е. если что-то выводится из другого - то оно не несёт дополнительной информации, что в принципе правильно, но недостаточно для определения информации).
Бамп годному треду.
Ну, антуаны, что ж вы так компухтер саенс лаской обделяете? Нет такой науки?
Не наука. Это агломерат различных сугубо инженерных тем и некоторых областей математики. Ни то ни другое наукой не является.
>Ни то ни другое наукой не является.
Проиграл. Ты только что опроверг существование термина "инженерные науки", ну и Гаусса в придачу с его "королевой наук".
> существование термина "инженерные науки"
Ну у нас и "исторические науки" есть, не говоря о том, что теология уже научная специальность.
>Гаусса
Мало ли, что считал, пусть и очень талантливый человек, умерший более 150 лет (скорее ближе к 170, но лень проверять) назад и более того даже не занимавшийся вопросами демаркации науки сколь-нибудь профессионально.
Ладно, докажи что "инженерные науки" и математика - не науки. Может, я сильно отстал от жизни и чего-то сам не знаю.
Не хочу расписываться стеной текста. Поэтому сформулирую кратко и доступно (и с неизбежными неточностями, разумеется).
Инженерная деятельность - это ответ на вопросы "как нам решить эту практическую задачу?". Научная - это ответ на вопрос "как это устроено?". Или иными словами, "что сделать, чтобы это заработало?" vs "как это работает?". Не понимаю как можно это смешивать.
Математику же отделяет от науки её чисто априорный характер, т.е. математика в норме не использует эксперименты и даже если они случаются, то они имеют совершенно вспомогательный характер.
>математика в норме не использует эксперименты
Если бы я хотел потроллить - то сказал бы "Теорема о четырёх красках". Ну да ладно.
>Не понимаю как можно это смешивать.
Прикладные/фундаментальные науки, сэр. Взять хотя бы сопромат(не читал, и не осуждаю, ногами не пинать, лол) - он же всё-таки изучает законы природы, а не "как нам решить эту практическую задачу?". Это таки не инженерия в чистом виде, но имеет к ней непосредственное отношение.
Да, конечно, все на самом деле сложнее чем я расписал и границы размыты, есть области которые сложно куда-то отнести.
Но возвращаясь к конкретике темы этого треда. Я настаиваю, что ни деятельности в духе поиска эвристик, скажем, для более эффективных алгоритмов выборки информации из баз данных, ни исследования высоких степеней рекурсии наукой не являются и, кстати говоря, имеют очень мало общего между собой.
>Инженерная деятельность - это ответ на вопросы "как нам решить эту практическую задачу?". Научная - это ответ на вопрос "как это устроено?". Или иными словами, "что сделать, чтобы это заработало?" vs "как это работает?". Не понимаю как можно это смешивать.
Если не понимаешь, попробуй рассказать, как можно решить практическую задачу без понимания "как это устроено". От балды - хороший подход, но в случае сколько-нибудь серьезных задач не работает.
Это не книжка, такую шнягу я вижу в каждой англ статье про алгоритмы.
>От балды - хороший подход, но в случае сколько-нибудь серьезных задач не работает
Есть правдивый анекдот:
Физику, математику и инженеру дали задание найти объём красного мячика.
Физик погрузил мяч в стакан с водой и измерилл объём вытесненной жидкости.
Математик измерил диаметр мяча и рассчитал тройной интеграл.
Инженер достал из стола свою "Таблицу объёмов красных резиновых мячиков" и нашёл нужное значение.
В инженерных науках обычно тонны эмпирических данных, которые намерены в эксперименте, а так как в реальности все может быть хуже (прораб цемент спиздил), еще везде накручены коэффициенты запаса.
Эти науки - не такие, те - не этакие, только физика теперь Ъ? Может, следует пересмотреть критерии науки?
Че-то я сразу вспомнил анекдот "предположим, что банка открыта, предположим, что открыта..".
Че-т начал гулить твой анекдот и нашел http://prikolov.net/prikol/anekdotynauka . Есть смешные.
11, 12, 17 зачетные.
>т.е. математика в норме не использует эксперименты и даже если они случаются, то они имеют совершенно вспомогательный характер
Нет. В некоторых областях (например, теория чисел) эксперименты носят первостепенный характер, т.к. позволяют формулировать теории ака гипотезы. Без них сформулировать можно, но дойти до такого трудно - впрочем, и в физике можно сформулировать теорию относительности, не наблюдая скорости фотонов, так что это не аргумент. Примеры: гипотеза Римана, гипотеза Коллатца, да в принципе практически любая гипотеза, по крайней мере из теории чисел. можешь, кстати, зайти в маттред и написать, что из всех областей математики наукой является только теория чисел - ядерный баттхерт не заставит себя ждать
Внешне математика так отличается от других наук по двум взаимосвязанным причинам:
2) В математике меньше принципиально недоказуемых вопросов - т.е., например, никак не удастся доказать, что верна именно теория эволюции, а не боженька все так подстроил (если только не построить машину времени и не посмотреть как дело было), или не какая-то обобщающая ее теория
2) В математике набор принципиально недоказуемых предположений (аксиом) гораздо меньше и вся остальная математика является их логическим следствием.
Только поэтому в математике эксперимент реже ставится - потому что есть более надежный инструмент проверки: формальное доказательство. За счет этих самых доказательств теории редко отвергаются и переделываются заново, поскольку это означает, что нестыковка с реальностью происходит на уровне исходных предположений и аксиом (но такое тоже бывает - гугли парадоксы наивной теории множеств).
Науки изучают объективную реальность и строят модели, описывающие аспекты этой реальности. В случае математики объективной реальности нет, ты строишь модель хуй пойми чего и изучаешь её свойства. Пока в этой модели (хуй пойми чего) нет противоречий - всё пучком.
Даже среди того, что ты написал. Особенность математики в том, например, что эксперимент не является способом подтверждения гипотезы. Никому не придёт в голову сказать, что гипотеза Коллатца верна потому что ты честно провёл эксперимент и не смог её опровергнуть.
>Науки изучают объективную реальность и строят модели, описывающие аспекты этой реальности. В случае математики объективной реальности нет, ты строишь модель хуй пойми чего и изучаешь её свойства. Пока в этой модели (хуй пойми чего) нет противоречий - всё пучком.
Ты несешь такую хуйню потому, что не понимаешь, что изучает математика.
>Матема́тика — наука о структурах, порядке и отношениях
Будучи математиком, ты в любой системе выделяешь множество взаимосвязей между объектами (структуру), и описываешь ее свойства, изучая ее. Сама система тебе при этом не нужна, если ты правильно выделил структуру - так же как и физику для того, чтобы рассчитать силу, не нужен будет сам предмет, если он уже выявил, что зависимость имеется только от массы и ускорения объекта. Да, структуру можно выделить неточно - также как можно неточно померить сумму скоростей и из-за этого не обнаружить теорию относительности. Про то, что достаточно только отсутствия противоречий - это везде так, просто в математике это заслуга того, что список не доказанных (т.е. проверяемых) утверждений в математике мал и они уже обкатаны временем, и потому с гораздо большей вероятностью верны, по сравнению с физикой, например, где постоянно ставились эксперименты, выносящие мозг исследователям и заставляющие, выкидывая все имеющееся к хуям, выдумывать новые лютейше сложные и запутанные теории, хотя бы просто чтобы все описать. Ну не повезло пацанам, не смогли они выделить такой узкий список постулатов, который сразу бы заработал.
>Особенность математики в том, например, что эксперимент не является способом подтверждения гипотезы. Никому не придёт в голову сказать, что гипотеза Коллатца верна потому что ты честно провёл эксперимент и не смог её опровергнуть.
Потому что есть более сильный метод - формальное доказательство. Экспериментом нельзя проверить утверждение сразу для бесконечного числа элементов, а доказать - можно. За счет того, что этот метод дает 99% результатов, математики избаловались, и по-хорошему принимают только теоремы (доказанное), а не гипотезы, насколько бы верными они не казались и сколько бы экспериментов их не подтверждало. Тем не менее, все равно есть несколько гипотез, которые не доказаны, но проверены, и повсеместно считаются верными, т.е. опираясь на них что-то доказывают - та же гипотеза Римана, P!=NP, и прочие такие вещи. Если эти гипотезы принимают как верные в своих работах, и никто авторов этих работ не шпуняет за это - значит, можно считать, что эти гипотезы сообщество приняло.
Ну и там, где экспериментом можно строго проверить всю гипотезу - так и делают: тут уже упоминали проблему четырех красок.
Не, чувак, у тебя какая-то своя особая математика получается.
> список не доказанных (т.е. проверяемых) утверждений в математике мал и они уже обкатаны временем, и потому с гораздо большей вероятностью верны
Да нет в математике понятия верности или неверности аксиомы. Составляя теорию, ты либо берёшь что-то за аксиому, либо нет, стараясь, чтобы не было противоречий. Вот та же аксиома выбора. С какой вероятностью она верна? Какие эксперименты ставят под сомнение её верность?
> математики избаловались, и по-хорошему принимают только теоремы (доказанное), а не гипотезы, насколько бы верными они не казались и сколько бы экспериментов их не подтверждало
Не избаловались, а в этом суть математики. Наивная теория множеств до Рассела тоже была всем очевидна.
> есть несколько гипотез, которые не доказаны, но проверены, и повсеместно считаются верными, т.е. опираясь на них что-то доказывают
Ты ебанутый? Что доказывают опираясь на гипотезу Коллатца или P!=NP? Отвечу за тебя. Во-первых, ничего не доказывают. А во-вторых, из одного лишь предположения верности этих гипотез ничего интересного не следует. Ну, допустим, есть полиномиальный алгоритм для 3SAT. И что? Сформулировать его сможешь?
> Ну и там, где экспериментом можно строго проверить всю гипотезу - так и делают: тут уже упоминали проблему четырех красок.
Это не эксперимент, а формальное доказательство.
>Составляя теорию, ты либо берёшь что-то за аксиому, либо нет, стараясь, чтобы не было противоречий.
Ну все правильно, если будут противоречия - значит не будет соответствовать действительности.
>Вот та же аксиома выбора. С какой вероятностью она верна? Какие эксперименты ставят под сомнение её верность?
В пользу нее экспериментальные факты: дохера семейств множеств обладают функцией выбора, причем зачастую она явно предъявляется. Какие эксперименты ставят под сомнение? Если б такие были, то хрен бы кто этой аксиомой пользовался. Аксиома - это то, в чем не сомневаются. Да, в качестве аксиомы можно брать что угодно - но это уже уровень метаматематики, т.е. где рассматривается структура уже самой математики. Там можно и нужно абстрагироваться от того, как и зачем в математике берутся аксиомы. Там, но не в математике.
Поставить такой эксперимент, который опроверг бы аксиому выбора, можно - например, предъявить семейство множеств, в котором нет функции выбора. А еще лучше потом доказать, что там этой функции выбора нет. Так что все научно.
>Не избаловались, а в этом суть математики. Наивная теория множеств до Рассела тоже была всем очевидна.
До Эйнштейна наивное сложение скоростей тоже было всем очевидно. А до квантовой механики вообще дохера че было очевидно: что частицы ведут себя либо всегда как волны, либо всегда как корпускулы; что все параметры частицы (координаты, скорость) потенциально можно померить с любой точностью, нет принципиальных ограничений; что поведение частицы не зависит от того, наблюдают за ней или нет. Давай я тоже теперь скажу, что в этом суть физики.
>Ты ебанутый? Что доказывают опираясь на гипотезу Коллатца или P!=NP? Отвечу за тебя. Во-первых, ничего не доказывают. А во-вторых, из одного лишь предположения верности этих гипотез ничего интересного не следует. Ну, допустим, есть полиномиальный алгоритм для 3SAT. И что? Сформулировать его сможешь?
Ну допустим, если предположить верной гипотезу Римана, то есть полиномиальный алгоритм проверки числа на простоту. Он и так есть, но без гипотезы Римана непонятно, полиномиален он или нет. То есть непонятно, искать дальше полиномиальный или уже все. Оценки всякие теоретико-числовые улучшаются. Много чего интересного происходит. Понятно, что просто из предположения о том, что гипотеза верна, ничего интересного, как ты говоришь, найти не получится - потому что если это интересное уже найдено (скажем, алгоритм какой-нибудь, ранее не известный - не его оценки сложности, а вообще сам алгоритм), то уже похер, верна или не верна гипотеза, а значит от нее изначально ниче не зависело.
Доказывают много всего на самом деле. Вся криптография на гипотезах висит, например, в том числе на P!=NP.
>Это не эксперимент, а формальное доказательство.
Это доказательство перебором всех случаев. То есть это серия экспериментов, оформленных в доказательство. Эксперименты это потому, что рассмотрели такую-то покраску (т.е. таким-то образом устроенную структуру), убедились, что для нее верно, рассмотрели следующую. И да, если бы в других науках можно было бы поставить ряд экспериментов и на основании этого ряда сделать вывод, что все вот именно вот так, и никак иначе, и всегда будет это выполняться, без всяких предположений о полноте описывающей теории, то они бы тоже очень скоро стали выглядеть как математика.
>Вот та же аксиома выбора. С какой вероятностью она верна? Какие эксперименты ставят под сомнение её верность?
Если окажется, что она противоречива другим аксиомам, она будет неверной.
>Ты ебанутый? Что доказывают опираясь на гипотезу Коллатца или P!=NP?
Да та же теорема Ферма в итоге свелась к доказательству довольно левой по отношению к теме гипотезы. Постоянно так делают. По теме треда - выводы из всяких сверхтьюринговых вычислителей, которые не понятно, как работают, но если они работают, то мы ща вам такое распишем.
теперь это математики тред?
лучше посоветуйте хорошую книжку по самым основам алгоритмам и структурам данных. я не даун и мне нужно коротко, но по возможности максимально строго. ну и желательно чтобы не было привязки к ебнутым языкам (типа оберона)
лучше посоветуйте хорошую книжку по самым основам алгоритмам и структурам данных. я не даун и мне нужно коротко, но по возможности максимально строго. ну и желательно чтобы не было привязки к ебнутым языкам (типа оберона)
Если нужно коротко, то Вирт - таки лучший выбор. А на язык похуй, там все равно ничего специфичного нет. А так - Кормен, но там длинно.
>Если окажется, что она противоречива другим аксиомам, она будет неверной.
Доказано, что аксиома выбора не противоречит остальным аксиомам теории множеств, и не может быть выведена из них. Поэтому если в ZF нет противоречий, то и в ZFC их нет.
Пикрелейтед лучшая книга по данной тематике.
мимо окончил ВМК МГУ
>теперь это математики тред?
Прикладной.
А как же ядрочеловек?
Кто-нибудь пробовал?
https://leanprover.github.io/about/
Что скажете?
Мои мысли -
1) тупое название - хер загуглишь
2) написано на плюсах - так что любимый вопрос обывателей о формальной верификации - как доказать сам доказыватель, как никогда актуален
3) интересно как этот проект соотносится с fstar? Значит ли это что fstar все?
https://leanprover.github.io/about/
Что скажете?
Мои мысли -
1) тупое название - хер загуглишь
2) написано на плюсах - так что любимый вопрос обывателей о формальной верификации - как доказать сам доказыватель, как никогда актуален
3) интересно как этот проект соотносится с fstar? Значит ли это что fstar все?
>почему локальные переменные во всех(или почти всех) известных языках хранятся на стеке?
В стандарте языка си например ничего подобного не сказанно, это личное дело компилятора, т.е. теоретически никто не мешает создать компилятор мыделяющий локальные переменные в куче, просто это будет накладно.
> дохера семейств множеств обладают функцией выбора
> Аксиома - это то, в чем не сомневаются.
А некоторые не обладают. И математики, представь себе, работают над теориями без аксиомы выбора, над конструктивной математикой (в частности, без закона исключения третьего) и прочими неочевидными вещами.
А бывает ещё круче: математика допускает существование теорий, прямо противоречащих друг другу (геометрии Евклида и Лобачевского, например).
> Давай я тоже теперь скажу, что в этом суть физики.
В физике у тебя есть эксперимент, поставленный в определённых условиях и есть модель, которая должна быть адекватна. В математике понятие адекватности можели теряется: любая модель достойна рассмотрения.
> есть полиномиальный алгоритм проверки числа на простоту
Ты что-то не то сейчас сказал. Проверить число на простоту тривиально можно за линейное время.
> Оценки всякие теоретико-числовые
улучшаются.
А то. Несколько классов сложности соединяются в один. Но это неконструктивно: без конкретного полиномиального алгоритма (заместо NP) ничего интересного не происходит.
> Вся криптография на гипотезах висит, например, в том числе на P!=NP.
Она висит на утверждении, что некоторые задачи сложно решить, но легко проверить. Традиционно считается, полиномиально это легко, а NP - это перебор в экспоненциальном (а то и хуже) пространстве решений, поэтому "сложно". Но на практике всё оказывается интереснее. Решение 3SAT лежит в основе верификации железа и программ - и никто не жалуется. Потому что реальные задачи имеют особую структуру, под которую оптимизируются алгоритмы перебора. Или, например, в линейном программировании симплекс-метод в худшем случае экспоненциален, а на практике сходится за полиномиальное время - и ничего 40 лет пользовались, пока не нашли полиномиальный алгоритм (через 40 лет, напоминаю). Это уже не говоря о том, что некоторые серьёзные люди (Кнут) сомневаются в P \neq NP.
> То есть это серия экспериментов, оформленных в доказательство.
Ты хоть раз был на лабе по физике? Серию замеров делал, вычислял доверительный интервал? Чувствуешь разницу с перебором в математике?
> написано на плюсах - так что любимый вопрос обывателей о формальной верификации - как доказать сам доказыватель, как никогда актуален
А никак. И в Z3 (который пилится в том числе де Мурой) багов был найден вагон и маленькая тележка. И в Coq false доказывали.
Да он вообще хуйню сказал. Переменные и в регистрах хранятся, и заменяются оптимизатором на константы, и на куче оказываются, если есть мутабельные замыкания.
Это ты хуйню говоришь, а он правильный вопрос задал.
Нахуй сходи. В языках обычно вообще нет понятия стека, анон, которому я ответил, правильно заметил. Стек - это способ реализации подпрограмм в ряде процессоров.
Ты сделал унылое замечание по форме вопроса, но на вопрос не ответил. ПОЧЕМУ стек - это способ реализации подпрограмм?
>робототехника
Не CS.
>А некоторые не обладают.
Пример?
>А бывает ещё круче: математика допускает существование теорий, прямо противоречащих друг другу (геометрии Евклида и Лобачевского, например).
В науке, изучающей структуры, нашли две разные структуры? Охуеть парадокс.
В чем противоречие заключается? Ответь на этот вопрос и обнаружишь свою ошибку.
>В физике у тебя есть эксперимент, поставленный в определённых условиях и есть модель, которая должна быть адекватна. В математике понятие адекватности можели теряется: любая модель достойна рассмотрения.
Во-первых, ты сейчас говоришь не о том, о чем шла речь в процитированном тобой. Пытаешься съехать с темы?
Во-вторых, я не понимаю твоего жонглирования словами. Что ты имеешь в виду под "достойна рассмотрения"? Можно рассматривать любую теорию, также как в физике? Да, можно. Нет предсказания, полученного из теории, которое эксперимент должен подтвердить или опровергнуть? Нет, это не так. Если ты находишь ноль дзета-функции вне критической прямой, то предсказываемый гипотезой Римана результат будет опровергнут, и сама гипотеза будет отвергнута. Экспериментом будет вычисление дзета-функции в точке. Подготовкой условий эксперимента - выбор этой точки.
>Ты что-то не то сейчас сказал. Проверить число на простоту тривиально можно за линейное время.
Охуительные блядь истории. Может, напишешь мне имена тех гениев алгоритмической ТЧ, которые переплюнули алгоритм AKS? Открой статью Primality test на вики и напиши туда свой тривиальный тест на простоту, а то пацаны-то не знают, что там все тривиально на самом деле.
Впрочем, по этому посту я уже вижу, что ты - мудак, который сам не знает, о чем говорит, но корчит из себя дохуя умного.
>А то. Несколько классов сложности соединяются в один. Но это неконструктивно: без конкретного полиномиального алгоритма (заместо NP) ничего интересного не происходит.
Это ты щас к чему спизданул? Какие еще в жопу классы сложности? Ты вообще знаешь что такое улучшить оценку?
>Но на практике всё оказывается интереснее. Решение 3SAT лежит в основе верификации железа и программ - и никто не жалуется. Потому что реальные задачи имеют особую структуру, под которую оптимизируются алгоритмы перебора.
Дальше че? Чем отличается задача 3SAT (та самая которая NP-полная) от задачи 3SAT для данной конкретной булевой формулы, не напомнишь? Почему эвристические алгоритмы, работающие в верификации программ, не работают в криптографии, сам догадаешься?
>Или, например, в линейном программировании симплекс-метод в худшем случае экспоненциален, а на практике сходится за полиномиальное время - и ничего 40 лет пользовались, пока не нашли полиномиальный алгоритм (через 40 лет, напоминаю).
Здорово, на практике алгоритм работает быстрее теоретических оценок, дальше что? Определение О-большого не напомнишь? Алсо,
>а на практике сходится за полиномиальное время
не научишь, как асимптотическое свойство полиномиальной сложности выводить из серии замеров на практике? Как на основании этих замеров отличать полиномиальный алгоритм, скажем, от квазиполиномиального, не расскажешь?
>Ты хоть раз был на лабе по физике? Серию замеров делал, вычислял доверительный интервал? Чувствуешь разницу с перебором в математике?
Нет, но чувствую разницу между тобой и собеседником, которому стоит что-то доказывать. Неси пример семейства множеств без функции выбора, неси алгоритм проверки на простоту, работающий линейное время, объясни, почему эвристические алгоритмы в криптографии отсасывают, и тогда посмотрим, а если нет - разговор окончен.
>в Coq false доказывали
Врети!
Во-первых, соси хуй. Можешь даже не читать то, что я ниже напишу. Просто соси хуй.
> Пример?
У некоторых математиков есть серьёзные сомнения насчёт множества действительных чисел. Потому что ты можешь предположить в виде аксиомы выбора, что функция выбора из действительных чисел есть, но дать её определение ты не сможешь. Неконструктивно выходит.
> Можно рассматривать любую теорию, также как в физике? Да, можно.
Нет, в физике не так. Была непротиворечивая эфирная модель света, но она была признана несостоятельной по результатам эксперимента над окружающим миром. Под экспериментом всегда понимается эксперимент над реальным миром. Изучение свойств математических объектов экспериментом не является.
> Открой статью Primality test
> O(log n ^ ...)
Если ты из тех петухов, которые размером входа считают количество бит в числе, то нам с тобой не по пути. Потому что это оторванный от реальности онанизм. И люди не мыслят в двоичных числах, и компьютеры выполняют операции над битами в представимых числах параллельно.
> Почему эвристические алгоритмы, работающие в верификации программ
А никто пока не может толком по-научному объяснить. С инженерной точки зрения всё довольно просто: люди решают те задачи, которые могут эффективно решать. С одной стороны, подбирают эвристики под те применения, которые одновременно интересны и не слишком сложны. С другой, пишут программы и разрабатывают железо так, чтобы они поддавались верификации. То же самое и в других околоприкладных областях (всякие оптимизации, численные методы и т.п.). Аналогом этого в криптографии, например, будет специальный подбор слабых "ключей". Соответственно, в криптографии, люди наоборот стараются придумать функцию, к которой сложно подобрать обратную. Инженерная задача, блеать.
Как всё это увязывается с теорией (почему RSA основан именно на факторизации, почему как люди пишут программы, поддающиеся верификации) - это, блядь, надо спросить у тех, кто серьёзно занимается теорией сложности. Но эти люди вместо того, чтобы заниматься чем-то полезным, начинают (как ты) кудахтать: "кококо простый числа" и наяривать свои пиструны на последовательности бит. Ну хуле, пусть дрочат. Но толку от их наяривания даже в криптографии ноль.
> не научишь, как асимптотическое свойство полиномиальной сложности выводить из серии замеров на практике
Это ты у нас экспериментатор хуев, вот ты и должен был мне это рассказать. Как Ньютон по замерам Тихо Браге свою гравитацию запилил? Взял, блядь, числа, построил график, почесал репу, прикинул вид зависимости и подобрал коэффициенты полинома. Угадал, блядь: "Это, мать её, квадратичная кривая" - и прав оказался.
Но, я смотрю, тебя не комплюктер саенс интересует, который есть прикладная наука, а бессмысленный дроч. Иди дрочи.
>Если ты из тех петухов, которые размером входа считают количество бит в числе, то нам с тобой не по пути.
Для чисел, для которых актуальна проверка на простоту (читай: криптографических ключей), никакой параллельности нет, там длинная арифметика.
https://github.com/clarus/falso
Твой вопрос в исходном виде некорректен. Корректный вопрос: "Почему в некоторых процессорах есть понятие подпрограммы, для реализации которого используется стек" -- имеет тривиальный ответ: "Люди так придумали". Менее тривиально было бы попытаться сначала понять, что появилось раньше: понятие подпрограммы в языке программирования или понятие стека в процессоре. Ты знаешь?
Но длина ключа ограничена. А операции над числами с ограниченным количеством бит - это O(1).
Кек, ты так любой алгоритм к О(1) сведешь. Предположим, что n - константа. Все, свели.
Я знаю. Мы это уже обсудили. Стек тебе нужен, потому что это самая тривиальная структура данных для хранения локальных переменных в языке с рекурсией. Нет рекурсии - стек тебе не нужен. И так и есть. В первых языках были подпрограммы, но не было стека. Это нужно понимать, особенно когда на сишке пилишь код, которому требуется быть надежным - static для локальных переменных твой друг.
Ну не совсем любой. В том же предположении Коллатца, ты не знаешь заранее предел разрядности (если предположить, что предположение верно) числе в последовательности, начинающейся с числа n. А в криптографии и прочих более практичных областях параллелизация действительно решает. В свете популярности биткоина выснлилось, что под конкретный алгоритм можно и специализированное железо запилить, и серверную ферму организовать -- были б деньги.
> Нет рекурсии - стек тебе не нужен.
Я где-то чую подвох. Компилятор будет использовать стек даже если в твоей программе 100% нет рекурсии. И что-то давно не видно императивных языков программирования, которые запрещали бы рекурсию (если нерекурсивные программы можно эффективно конпелировать без стека). Хотя не использовать рекурсию в императивном языке (где нет оптимизации хвостовых вызовов) это очень хороший тон. Глубина рекурсии часто зависит от входных данных, а стек не резиновый.
С другой стороны, сама концепция: прервать текущие вычисления, а потом возобносить - полезна для псевдопараллельного выполнения нескольких программ (или программы и ОС) на одном процессоре.
Параллелизация влияет только на константу, а не на o-сложность. Распралаллель np-полную задачу. Будет у тебя не 10 миллиардов лет, и миллиард. Ну, удачи.
>Я где-то чую подвох.
Да нет подвоха, ты спросил, что появилось раньше, я тебе ответил. Подпограммы придумала/открыла Ада Лавлейс, современница Пушкина, а стэк появился в конце 50-х, в лиспе и алголе. В коболе и фортране его не было, и рекурсии не было. Видишь, насколько это охуенный вопрос? То, что для тебя - как воздух, кто-то открыл и имплементировал. А ты какую-то чушь несешь про то, что компилятор по регистрам локальные переменные может распихивать. Вот чисто аутичная доебка.
>Хотя не использовать рекурсию в императивном языке (где нет оптимизации хвостовых вызовов) это очень хороший тон.
Дело не в оптимизации хвостовых вызовов, а в том, что рекурсия по читаемости находится где-то на уровне goto. Ее и в функциональных языках использовать не рекомендуется, а рекомендуется комбинировать комбинаторы.
>У некоторых математиков есть серьёзные сомнения насчёт множества действительных чисел. Потому что ты можешь предположить в виде аксиомы выбора, что функция выбора из действительных чисел есть, но дать её определение ты не сможешь. Неконструктивно выходит.
Где пример, балабол?
>Была непротиворечивая эфирная модель света, но она была признана несостоятельной по результатам эксперимента над окружающим миром.
Значит, она оказалась не непротиворечивой.
>Под экспериментом всегда понимается эксперимент над реальным миром.
Что такое реальный мир, не напомнишь?
>Изучение свойств математических объектов экспериментом не является.
Потому что ты так сказал?
>Если ты из тех петухов, которые размером входа считают количество бит в числе, то нам с тобой не по пути.
>Потому что это оторванный от реальности онанизм.
Да, нам с тобой не по пути, мудозвон. Поэтому съеби отсюда нахуй. Логарифм числа у него уже оторванный от реальности онанизм, охуеть вообще. Все конструктивисты такие пизданутые или ты один такой?
>А никто пока не может толком по-научному объяснить.
Я могу. В криптографии параметры выбираются случайно равновероятно, а во всяких верификациях - не равновероятно (из определенного узкого, структурированного класса). Любая эвристика выделяет определенную структуру в данных, и за счет этого работает быстрее. Во всяких там программах структура точно есть, но она слишком сложна для формального изучения. Поэтому формальный анализ не работает, а эвристики - работают. В случайно выбранных из всего пространства примерах структуры с подавляющей вероятностью нет, но они не так сложны для формального изучения (можно самому выделять какие угодно классы, в том числе простые). Поэтому если формальный анализ тут ничего не находит, то эвристики чаще всего - тем более. "Чаще всего" я говорю потому, что иногда атакующий алгоритм опирается на хорошо структурированные, но плохо изучаемые задачи (например, подбор соотношений между элементами для задачи дискретного логарифмирования). Вот там иногда взлетают эвристики. Но все равно, чтобы до использования таких эвристик дойти, нужно неслабо заморочиться и выделить такие структурированные подзадачи. И по сути эвристики там носят временный характер (недостаточно было проанализировано исследуемое эвристикой пространство, потому не получено соответствующих действительности оценок скорости работы эвристик).
>Но эти люди вместо того, чтобы заниматься чем-то полезным, начинают (как ты) кудахтать: "кококо простый числа" и наяривать свои пиструны на последовательности бит. Ну хуле, пусть дрочат. Но толку от их наяривания даже в криптографии ноль.
К чему была эта жопаболь, я вообще не понял.
>Это ты у нас экспериментатор хуев, вот ты и должен был мне это рассказать.
И я тебе скажу - никак. Никак ты асимптотическое свойство не выведешь по конечному числу замеров - ты сможешь только предположить, что имеет место полиномиальный рост, или еще какой. Поэтому никто не пишет "на практике сходится за полиномиальное время". Пишут "на практике наблюдается полиномиальный рост".
>Как Ньютон по замерам Тихо Браге свою гравитацию запилил? Взял, блядь, числа, построил график, почесал репу, прикинул вид зависимости и подобрал коэффициенты полинома. Угадал, блядь: "Это, мать её, квадратичная кривая" - и прав оказался.
Охуительные истории снова. Ньютон вывел закон всемирного тяготения из законов Кеплера. И именно поэтому там расстояние во 2-й степени, а не в 2,0001-й
>Другими словами, Ньютон обнаружил, что из третьего закона Кеплера, связывающего периоды обращения планет с расстоянием до Солнца, следует именно «формула обратных квадратов» для закона тяготения (в приближении круговых орбит). Окончательную формулировку закона тяготения, вошедшую в учебники, Ньютон выписал позднее, после того, как ему стали ясны законы механики.
Впрочем, кому я все это объясняю. Съеби уже. Хотя нет, не съебывай - пиши дальше свои смешные высеры тупорылого "практика", не знающего азов.
Аноны, как математически сравнивать гипотетические процессоры с различным набором инструкций (при прочих равных условиях, естественно)? Только по плотности кода, или есть еще какие-либо критерии?
Вот вам няша.
Вот вам няша.
Как сравнить хуй с пальцем?
Линейкой.
Ну вот линейкой микросхемы и меряй, ептить.
А какая у нее должна быть длина? А шаг шкалы? Требования по точности?
> Где пример, балабол?
Балабол здесь ты. А проблема вот в чём. Если ты имеешь аксиому выбора и разрешишь выбирать элемент из любого подмножества ℝ, то на ℝ (и вообще на любом множестве - это теорема Цермелло) существует вполнепорядок. Тем не менее, формулы у этого вполнепорядка нет. Некоторым припекает от такого расклада - что существуют объекты, которые человек не может описать, поэтому они отвергают аксиому выбора. Их право.
Алсо, раз ты топишь за эксперименты в математике, то вот над чем подумай. В современной науке ходит мнение, что "доказывать должен тот, кто утверждает существование" (чайник Рассела, ага), то есть, принимая аксиому выбора, ты должен подтвердить её экспериментом, предъявив вполнепорядок на ℝ.
> Значит, она оказалась не непротиворечивой.
Я в точности не помню, что у неё было с теоретической частью. Запомнил лишь, что эфир противоречил только эксперименту над реальным миром, но с математической точки зрения был состоятелен. И я не помнимаю, почему ты настаиваешь, что модель, поведение которой расходится с экспериментом, является противоречивой (то есть по сути абсурдным математическим объектом).
> Что такое реальный мир, не напомнишь?
Объективная реальность, которая существует вне твоего разума.
>Изучение свойств математических объектов экспериментом не является.
> Потому что ты так сказал?
Потому что принципиально разные вещи. В математике, приняв аксиому выбора, ты, как мы убедились, можешь рассуждать об объектах которые есть, но которые нельзя построить и наблюдать. А суть эксперимента в наблюдении над конкретными объектами, которые уже есть или которые ты можешь создать.
> Логарифм числа у него уже оторванный от реальности онанизм
В контексте то бывает, что так.
Во-первых, давай определимся. Ты путаешь два понятия. Есть проверка числа на простоту, есть проверка двоичной записи числа на принадлежность PRIMES. Это две разные задачи, т.к. число и его запись - не одно и то же. В частности, в криптографии у нас числа имеют ограниченную разрядность, поэтому неверно предполагать, что стоимость арифметических операций растёт линейно с величиной числа. Перенося результаты из PRIMES на числа ограниченой разрядности ты совершаешь логическую ошибку.
Алсо, ты меня наебал. То, что PRIMES полиномиален "... is not conditional on any subsidiary unproven hypothesis.", как сообщают интернеты. Почему мне приходится за тобой гуглить?
> В криптографии параметры выбираются случайно равновероятно
В этом утверждении мне видится подвох. Например, хеш-функции, использующиеся, в криптографии не являются случайно выбранными. Также вход хеш-функций часто не случаен (но обычно стараются примешиваеть случайное число). Это люди вибирают хеш функции таким образом, чтобы по выходу нельзя было понять вход. То есть в сравнении с верификацией, хеш-функцию (т.е. программу) выбирают так, чтобы её нельзя было анализировать имеющимися инструментами. Где в этом процессе случайные параметры, о которых ты говоришь - для меня загадка. Но не исключу, что для ассиметричного шифрования твоё предположение более правдоподобно.
> Никак ты асимптотическое свойство не выведешь по конечному числу замеров
А начали мы с твоего утверждения, что в математике свойство объектов можно изучать экспериментально. И теперь ты своё же утверждение опровергаешь. Я согласен, что в математике так делать не стоит. А вот в физике это нормально. Закон всемирного тяготения - это в некотором роде асимптотическое свойство. Он сформулирован для материальных точек, т.е. для объектов, собственными размерами которых можно пренебречь.
> никто не пишет "на практике сходится за полиномиальное время"
Для итеративных алгоритмов под "сходится" (converge) имеют в виду "завершается". Это не про асимптоты.
> Ньютон вывел закон всемирного тяготения из законов Кеплера.
Ну да, Кеплер там ещё был. Я что, буду всех их по именам помнить? Суть-то одна: один перец (Браге, насколько я помню), померил цифры, второй угадал, что они описывают эллипсы, третий угадал вид зависимости (в которой не только расстояние, влияние которого можно угадать из уравнения эллипса, но и массы).
Ах, да. Забыл тебя нахуй послать. Так вот. Иди нахуй.
> "доказывать должен тот, кто утверждает существование"
Но тогда получается должны доказывать противники аксиомы выбора, ведь это они утверждают что существуют такие непустые множества из которых нельзя выбрать элемент и добавить его в другое множество.
>существуют такие непустые множества из которых нельзя выбрать элемент и добавить его в другое множество.
У тебя кривая формулировка, но не важно. Вот собственно анон выше и предъявил проблемный случай - множество для которого нужна функция выбора для доказательства теоремы Цермело в случае R (множество всех непустных подмножеств R). Дальше уже дело сторонников AC объяснять, почему они считают, что для этого множества есть хоть одна функция выбора
>У тебя кривая формулировка
Чем она крива? Аксиома утверждает что если есть несколько непустых множеств, из них можно выбрать по одному элементу. Следовательно противники аксиомы должны показать существование непустого множетсва из которого невозможно выбрать элемент.
>Алсо, раз ты топишь за эксперименты в математике, то вот над чем подумай. В современной науке ходит мнение, что "доказывать должен тот, кто утверждает существование" (чайник Рассела, ага), то есть, принимая аксиому выбора, ты должен подтвердить её экспериментом, предъявив вполнепорядок на ℝ.
Конкретно я тебе доказывать ничего не буду, мне от этой аксиомы выбора ни жарко, ни холодно. Мы вообще говорили о том, что аксиома - это то, в чем не сомневаются, т.е. экспериментальных подтверждений достаточно, как с P!=NP. Кто сомневается - тот не берет это аксиомой (как Кнут). При этом никто никому ничего не доказывает, потому что никто не воспринимает эту аксиому как доказанный факт.
Но если ты утверждаешь (не предполагаешь, не приводишь доводы против, а именно утверждаешь), что аксиома неверна, то тогда ты обязан это доказать.
Я не говорил, что аксиома выбора - безоговорочно верный факт. Поэтому я тебе ничего не должен доказывать и не буду.
А вот ты сказал, что некоторые семейства множеств функцией выбора не обладают. Это было утверждение, четкое и ясное. В таком случае , как ты и сказал, бремя доказательства утверждения лежит на тебе. Так что потрудись привести пример такого семейства с доказательством отсутствия функции выбора на нем. И тоерема Цермело, которую ты привел, не переводит стрелки на меня, заставляя меня доказывать отсутствие вполнепорядка, а является для тебя вспомогательным инструментом: докажешь, что на R нет вполнепорядка - будет довод в пользу отсутствия на R функции выбора. Ну вот и вперед.
Про то, что формулы для такой функции много где нет, но как ты понимаешь, утверждать, что и функции в таком случае нет - беспруфный пиздеж. А брать аксиому выбора в качестве аксиомы или брать ее отрицание - это не возбраняется, так же как рассматривать эфир или не рассматривать.
>Я в точности не помню, что у неё было с теоретической частью. Запомнил лишь, что эфир противоречил только эксперименту над реальным миром, но с математической точки зрения был состоятелен. И я не помнимаю, почему ты настаиваешь, что модель, поведение которой расходится с экспериментом, является противоречивой (то есть по сути абсурдным математическим объектом).
Теория эфира, как любая физическая теория, опирается на один постулат: описываемое ей соответствует реальным физическим процессам. Без этого постулата это не физическая теория, а просто математические размышления. И именно этот постулат приводит к тому, что несоответствие экспериментам делает теорию противоречивой.
>Объективная реальность, которая существует вне твоего разума.
Набор слов. Докажи, что корень из двух не принадлежит "объективной реальности, которая существует вне чьего-либо разума."
>В математике, приняв аксиому выбора, ты, как мы убедились, можешь рассуждать об объектах которые есть, но которые нельзя построить и наблюдать. А суть эксперимента в наблюдении над конкретными объектами, которые уже есть или которые ты можешь создать.
В квантовой физике ты тоже можешь рассуждать об объектах, которые есть, но которые нельзя наблюдать (квантовая запутанность разрушается после любого наблюдения). Дальше что. Плюс, что ты имеешь в виду под "построить". Электрон тоже нельзя "построить".
>Ты путаешь два понятия. Есть проверка числа на простоту, есть проверка двоичной записи числа на принадлежность PRIMES. Это две разные задачи, т.к. число и его запись - не одно и то же.
Это пиздец..
>В частности, в криптографии у нас числа имеют ограниченную разрядность
Что ты несешь-то, блядь. Ну и чем они ограничены в таком случае? Давай, назови это число.
>Алсо, ты меня наебал. То, что PRIMES полиномиален "... is not conditional on any subsidiary unproven hypothesis.", как сообщают интернеты. Почему мне приходится за тобой гуглить?
Потому что сначала был детерминированный алгоритм с полиномиальной оценкой сложности, опиравшийся на обобщенную гипотезу Римана, а потом изобрели не опирающийся. А еще потому, что ты гуглить не умеешь.
>Similarly, under the generalized Riemann hypothesis, the Miller–Rabin test can be turned into a deterministic version (called Miller's test) with runtime Õ((log n)^4)
>Где в этом процессе случайные параметры, о которых ты говоришь - для меня загадка.
Там, где эти параметры есть. Не в хеш-функциях. Да, например в асимметричном шифровании (да и в симметричном - ключ выбирается случайно).
>А начали мы с твоего утверждения, что в математике свойство объектов можно изучать экспериментально.
Изучать и делать предположения - можно, но не доказывать. Наблюдение полиномиального роста у эвристики, решающей 3SAT, позволит полагать, что P=NP. Полагать, но не более того: неизвестно, для всех ли входов эвристика работает полиномиальное время, неизвестно, полиномиальный это рост или нет. Это никаки не противоречит моим словам: эксперименты помогают формулировать гипотезы и тестировать их на правдоподобность, но это далеко не всегда можно оформить в полное доказательство.
>Ну да, Кеплер там ещё был. Я что, буду всех их по именам помнить? Суть-то одна: один перец (Браге, насколько я помню), померил цифры, второй угадал, что они описывают эллипсы, третий угадал вид зависимости (в которой не только расстояние, влияние которого можно угадать из уравнения эллипса, но и массы).
Ну так вот в том и суть, что Ньютон не подбирал формулу методом "а не пиздануть ли мне тут двойку?", а предъявил вывод из законов Кеплера. И именно поэтому это смогло стать законом всемирного тяготения, а не гипотезой, оценкой или еще чем.
>Я настаиваю, что ни деятельности в духе поиска ..., ни исследования ....наукой не являются
Ясно, понятно
Таки нет - это дело противников AC доказать, что там нет ни одной функции, которую можно было бы сделать функцией выбора. Иначе это методология ультрафинитистов: вот ты говоришь, что 2^2^100 существует, тогда давай покажи, че, не можешь показать? ахаха, обосрался, лалка.
>Про то, что формулы для такой функции много где нет, я в курсе, но ...
фикс
>Чем она крива?
В этой формулировке некорректно буквально все. Неправильно говорить, о предъявление непустых множеств вместо предъявления множества непустых множеств т.к. не всякая совокупность является множеством, а аксиома выбора говорит только о множествах. Выбирать нужно по одному элементу из каждого можества, что не отражено в том, что ты написал, при этом, выбрать здесь означает существование функции, отображающей каждое множество из данного множества непустых множеств в некоторый его элемент. При чем здесь добавление в "другое множество" я вообще ума ни приложу.
Разумеется, когда говорят о математике почти всегда допускаются некоторые неточности, иногда бывают мелкие ошибки и в норме я бы не стал придираться, но здесь был совсем уж перебор с этим.
AC говорит, что для всех множеств непустых множеств существует функция выбора. Частным случаем здесь является существование функции выбора для множества непустых подмножеств R, руководствуясь "доказывать должен тот, кто утверждает существование", должен был бы быть готов доказать существование такой функции.
Я здесь всего лишь показывал, что принимая этот принцип
> "доказывать должен тот, кто утверждает существование"
, из чего и исходил , ну и существование настоящей вселенной множеств, нет причин принимать аксиому выбора (занимался интеллектуальной игрой).
По-большому счету, я считаю, что после изобретения метода форсинга позиция согласно которой есть одна настоящая вселенная множеств стала крайне безосновательной т.к. есть ряд вопросов, в частности проблема континуума, на которые нельзя ответить из стандартной аксиоматики и хуже того оба варианта ответа на них равноправны (это может быть уточнено).
> почему локальные переменные во всех(или почти всех) известных языках хранятся на стеке?
Потому что иначе надо как-то бороться с фрагментацией памяти, а это сложнее.
>Проверить число на простоту тривиально можно за линейное время.
Нет, нельзя.
>Если ты из тех петухов, которые размером входа считают количество бит в числе, то нам с тобой не по пути.
Нет, ну Тьюринг конечно был петухом. Но его тачка ездит на битах, и именно она была выбрана в качестве эталона для определения временной сложности алгоритмов.
>компьютеры выполняют операции над битами в представимых числах параллельно.
Удивительно! Как же им удаётся выполнять сложение, в котором надо учитывать перенос из младших разрядов? Или умножение?
>А операции над числами с ограниченным количеством бит - это O(1).
Ты хочешь сказать, что если у тебя будет процессор, умеющий делать операции {+, -, *, /} с числами длины n за такт, то ты сможешь определить простоту числа за число тактов меньшее полинома от n в худшем случае?
Ты цифры с потолка взял. Про десять миллиардов лет звучит хорошо, конечно. Но на практике ты можешь купить тысячи вычислителей и за несколько месяцев решить задачу, на которую теоретически требовались бы тысячи лет.
> Нет, нельзя
Тривиально за линейное от n. Впрочем, если вы тут все хором утверждаете (хотя доверия у меня к вам мало), что в криптографии вот именно длина двоичной записи числа - самая важная мера - не буду с вами спорить.
Однако продолжу утверждать, что длина входа в битах - в общем случае не подходит для оценки вычислительной сложности. Я как-то был на презентации алгоритма энергоэффективного планирования задач и слегка прихуел от того, что оценка сложности была дана в таком виде. Как использовать такую оценку (когда неясно, как влияет количество задач, как влияют их параметры) - непонятно. А потом будете удивляться, что йоба-теоретические наработки не используются в промышленности.
> Но его тачка ездит на битах
Его тачка ездит на символах. Биты вообще не в кассу.
> Как же им удаётся выполнять сложение, в котором надо учитывать перенос из младших разрядов?
Сумматор - это комбинаторная схема (максимальное количество последовательных элементов у неё скорее всего пропорционально логарифму от разрядности), соответственно для него нет понятия времени как числа инструкций или тактов. Ты подаёшь сигнал на вход и через какое-то время (в физическом смысле) на выходе стабилизируется результат. Современные АЛУ складивают за один такт по несколько чисел практически независимо от разрядности (больше влияет, где именно расположены операнды). Умножают чуть медленнее. Делят ещё чуть медленнее.
> с числами длины n
> ты сможешь определить простоту числа за число тактов меньшее полинома от n
Нет, не смогу. Проехали.
> Подпограммы придумала/открыла Ада Лавлейс, современница Пушкина
Такое утверждение надо с пруфами давать, потому как по некоторым данным Лавлейс, кроме сосания хуёв, мало что умела.
> а стэк появился в конце 50-х, в лиспе и алголе. В коболе и фортране его не было, и рекурсии не было.
> А ты какую-то чушь несешь про то, что компилятор по регистрам локальные переменные может распихивать. Вот чисто аутичная доебка.
Не доёбка, а поправка, которая, наконец, повела обсуждение в нужное русло. И Фортран, и Лисп были запилены для IBM 704. Программерский мануал для этого комплюктера свободно лежит в сети. И в этом мануале даётся пример работы с нерекурсивными (в том числе без косвенной рекурсии) подпрограммами. Если отбросить технические подробности, то для аргументов подпрограммы (эту идею можно распространить на вспомогательные данные) предлагается использовать ячейки данных, стоящие после инструкции вызова. И никакого стека не надо. Далее, если полистать ранние статьи по Лиспу (опять же, свободно доступные), то "public pushdown list" и вызовы save/unsave там используется для сохранения промежуточных данных вызывающей функции, а не для хранения данных, использующихся текущим вызовом. То есть более канонично говорить о том, что локальные переменные хранятся где угодно, а стек используется в первую очередь для сохранения контекста прерванной подпрограммы. Таким же образом стек используется прерываниями. То, что там же на стеке можно держать некоторые локальные переменные (да хоть массивы выделяй) - это бонус.
>Хотя не использовать рекурсию в императивном языке (где нет оптимизации хвостовых вызовов) это очень хороший тон.
Я о том, что современные ОС выделяют под стек весьма небольшой объём, по сравнению с возможным объёмом входных данных. Например, наивный рекурсивный поиск в глубину будет падать для графа с милионами вершин.
> Дело не в оптимизации хвостовых вызовов, а в том, что рекурсия по читаемости находится где-то на уровне goto.
Ну это слишком радикальное утверждение. Хороших понятных рекурсивных алгоритмов довльно много, начиная от поиска в глубину в графе (и всего, что на нём основано) и заканчивая квиксортом. Если переписать их на явное использование стека - читаемость только проиграет.
По некоторым данным ты, кроме сосания хуев, ничего не умеешь.
>Ты цифры с потолка взял. Про десять миллиардов лет звучит хорошо, конечно. Но на практике ты можешь купить тысячи вычислителей и за несколько месяцев решить задачу, на которую теоретически требовались бы тысячи лет.
И снова дебил, не могущий в теорию сложности вычислений, выходит на связь. Впрочем, после вскукарека о том, что в криптографии длина ключа ограничена и потому все O(1), я уже не удивлен.
Я увеличу длину входа на 1 бит (допишу 1 символ) - количество битовых операций, необходимых для решения задачи, увеличится вдвое. Еще на 1 бит больше - еще удваивается количество операций. Это называется экспоненциальная сложность, познакомься с ней. Теперь упражнение - если йоба-вычислитель решал экспоненциально сложную задачу с длиной входа N бит за 1 секунду, то сколько еще йоба-вычислителей потребуется, чтобы решить эту же задачу с длиной входа N+100 бит, скажем, за миллиард лет. Задание на дом - погуглить время жизни вселенной в секундах, посчитать, сколько бит нужно дописать, чтобы оценка необходимого времени для вычислений в предыдущей задаче перевалила за эту цифру, долго думать.
Что ж тебе так припекает?
>Ты подаёшь сигнал на вход и через какое-то время (в физическом смысле) на выходе стабилизируется результат.
И чем длиннее твоя арифметика, тем дольше тебе ждать этой стабилизации. От этого не убежишь.
В случае с умножением ещё и количество элементов в схеме растёт нелинейно от разрядности. От чего схема разбухает и замедляется, не говоря о цене.
>Однако продолжу утверждать, что длина входа в битах - в общем случае не подходит для оценки вычислительной сложности.
Верно, но это всё таки более универсальный подход чем рассматривать вход как число, потому что далеко не всякий однородный массив бинарных данных являет собой число. А складывать разнородные данные в одну кучу это свальный грех. Нет причин так делать.
>Современные АЛУ складивают за один такт по несколько чисел практически независимо от разрядности
За этим не стоит ничего фундаментального. При сложении байтов "на выходе стабилизируется результат" быстрее, чем при сложении лонгов, но длина такта для всех операций одинакова, причём взята с запасом. Это тебе подтвердит любой школьник с разогнаным процем. Так сделали потому что были причины.
Во-первых для определения стабилизации результата требуются дополнительные элементы схемы. Увеличить количество логических вентилей в 1.5 - 2 раза дорого.
Во-вторых равные такты это удобно когда процессору надо общаться с другими устройствами, прежде всего памятью.
В общем умные дядьки пользуются методологией DRY KISS.
Есть ли какой-нибудь общая учебная программа для CS?
Хотя бы примерно, чтобы можно было нагуглить по темам.
Скажите пожалуйста, хочу запастись книгами.
Хотя бы примерно, чтобы можно было нагуглить по темам.
Скажите пожалуйста, хочу запастись книгами.
Чето я нихуя не понял про философов. Лучше бы там была описана эта самая проблема ленточных чего-то там.
Просто блядь вилок всегда хватает только 2 - они едят, другие думают. В чем проблема? В чем задача то? Спагетти условно-бесконечные, что тут решать? Надо 1 раз заставить 2х есть или пускай сами начнут когда захотят. Они могут умереть с голода, а те что начали жрать типо жадные?
Почитав тред я че-то охуел, какая информация? Что несете блядь? Вы че нахуй удумали? Вы тут охуительные истории про информацию пишите, а теперь скажите мне чем она задается и как измерять ее?
Энтропией.
Че, наркоман совсем? Ладно давай так, единица в системе си какая?
Почему в системе СИ? Единица - бит.
Потому, что си использует фундаментальные константы реального мира которые можно зафиксировать и измерить. А твоя "информация" это хуй пойми какая абстракция которая у каждого своя в их манямирке. И даже в твоей ебанутой реальности, тебе нечем мерять твои ебучие биты.
бамп вопросу, плс.
Глянь оппик http://2ch.hk/pr/res/579625.html
Ты говоришь о физическом смысле информации?
За количественными характеристиками информации пиздуй в теорию информации и теорию колмогоровской сложности. С троллингом уровня "нету в физике - нету вообще нигде" пиздуй в /b.
То есть это все, что изучают на CS?
Я говорю о физической реальности. Обьективно наблюдаемой, сведенной к фундаментальным константам.
>С троллингом уровня "нету в физике - нету вообще нигде"
ЛОЛ. А давай ка ты пиздуй в ту вселенную где существует наблюдаемая реальность т.е. сама вселенная которую НЕ описывает физика. Сука тупое уебище блядь, откуда лезите такие хуесосы не понимающие вообще нихуя ни в чем, ни в физике, ни в математике. Я вот сам не силен в математике, но математик-кун тебя обыссыт. Хотя как я вижу выше уже обоссывал, но тебе под шконарем не сидится. Ты понимаешь что такое тождественность? Ты понимаешь чем симуляция отличается от того, что она симулирует?
Ты не ответил на мой вопрос.
> тебе нечем мерять
А как отмеряют сколько бит отсыпать на жесткий диск? Сколько дисков и флешек не покупал, там всегда было приблизительно тоже количество битов которое обещал продавец. Это же не может быть совпадением? Чем-то их отмеряли.
Я говорю не о "смысле" а об обьекте или взаимодействии которые наблюдаются в нашей вселенной. Блядь что тебе не понятно нахуй? Твой вопрос ответа не имеет, физический смысл это вообще какая-то конструкция которую ты сам сочинил и наделил какими-то охуительными свойствами. Я ответил на твой вопрос?
Не знаю, в физике например можно сказать что жесткий диск имеет определенное кол-во атомо из которых он состоит, мерять с горем пополам и некоторыми погрешностями можно. Я вот дам тебе конфету и скажу что она это знак титула "Король чуханов", а другому анону дам конфету и скажу, что он няша и вот ему конфета. Сколько унижения я отмерял тебе и сколько чаю другому анону? Ну примерно так почувствовать можешь? А я очень точно отсыпал.
Нет, я его переформулирую:
Ты считаешь, что информация является физической величиной?
Какая-то шизофазия бомбанувшего. Причинно-следственные связи существуют -> существует информация. Все. Наблюдаемая реальность, блядь, симуляция - че ты несешь вообще, феласаф хуев?
Это не имеет значения. Мое мнение, что я считаю, или не считаю не делают что либо физической величиной. Они существуют вне зависимости от моего мнения. Иформация - абстракция от логики людей, вымышленная форма. Атом - не абстракция, а кусок реальности. Меня нет - я не мыслю, не облекаю мысль в обстрактный термин и ее нет, а атом есть.
Так что нет, это не физическая величина, и не по моему мнению, а по факту.
Уебывай. Вырази информацию через другие физические константы или хуй простой.
Если информация не является физической величиной, то какое отношение она имеет к системе СИ?
Никакого, это само собой разумеется, по этому говорить о ней в рамках физической реальности - не верно.
А "физическая реальность" – то что выразимо при помощи физических величин?
Лол, это уже какой-то засмеялся-проиграл тред, а не CS-дискуссия.
мимо
Гравитация - это хуй пойми какая абстракция, которая у каждого своя в их манямирке. Вырази гравитацию через другие, негравитационные физические константы, или хуй простой.
Аналогия с сутью твоих доебок прямая.
Ты не можешь начать изучать предмет, пока не соберёшь все существующие публикации по нему?
Она есть. Звезды были до того как мы определение сформулировали.
Выведи из фундаментальных велечин переменную информации или константу или что там у тебя в твоей манявселенной.
>Атом - не абстракция, а кусок реальности
>Меня нет - я не мыслю, не облекаю мысль в обстрактный термин и ее нет, а атом есть.
Нету никакой реальности. Все есть флуктуации вакуума. Иные формы существования энергии. Подзалупный творожок мироздания.
Ты видишь не объект, а отраженные от него фотоны. Ты чувствуешь не объект, а деформацию частиц твоего тела, происходящую из-за отталкивания частиц твоего тела от частиц объекта за счет электрослабого взаимодействия. Сами эти частицы существуют лишь в относительном смысле - они переходят из одной в другую как хотят. Твой эмпирический опыт, на который ты так дрочишь, дает тебе всего лишь иллюзию наблюдения существования, ложную уверенность в объективности вещей, которые ты смог объективизировать, отделить друг от друга только потому, что они иногда пребывают в стабильном, неоднородном, объективируемом состоянии.
Столкнули твой якобы существующий атом с антиатомом - и все это превратится в фотоны, которые есть лишь сгустки энергии. Электрон поглотит фотон и просто перейдет в возбужденное состояние, ничего нового не появится, лишь поменяется пара его параметров, отвечающих за его поведение во времени. А потом этот электрон проаннигилирует с позитроном, все это превратится в фотоны, и так далее. Что из этого ты называешь реальным? Что называешь существующим?
Нет ничего реального, материального, существующего. Есть только энергия (число), причудливые структуры, которые она образует, и процессы, по которым она преобразуется. Вот и изучай структуры - математику. Вот и изучай процессы - информацию.
>Она есть.
Докажи. Всегда была? И в момент, когда вещество находилось в состоянии кварк-глюонной плазмы? И в момент, когда Вселенная находилась в состоянии сингулярности? Если нет, то когда появилась? Почему, и почему именно в таком виде, в котором ты утверждаешь?
Твое утверждение о существовании ты никак не докажешь, потому что само понятие существования - придуманный тобой неизучаемый высер, в который ты свято веруешь.
>"Король чуханов"
Это все очень хорошо, но ты так и не ответил каким образом мне в магазине на жесткий диск или флешку отсыпают практически столько же битов инфы, как на нем написано как правило обвешивают сучечки - тогда как ты уверждаешь что якобы иформацию "тебе нечем мерять". Просто совпадение?
>Иные формы существования энергии
Ака - масса*скорость, пока полет нормальный - вселенная существует не только в манямирке.
>Ты видишь не объект
Но я вижу обьект. Тысячи их, все из атомов. Сие есть факт. Глазпринимает отраженный от них свет, но блядь это НЕ ИМЕЕТ НИКАКОГО ЗНАЧЕНИЯ. Потому, что очевидно, что наличие обьекта не зависит от моего восприятия. Тут как бы вообще нехуй говорить, очевидно что звезды - обьекты физической реальности, очевидно что они появились раньше людей.
>Ты чувствуешь не объект, а деформацию частиц твоего тела
Т.е. по твоему частица или некоторое количество частиц меня не является частью обьекта меня? Че несешь то?
>из-за отталкивания частиц твоего тела от частиц объекта за счет электрослабого взаимодействия
НО ТЫ ПРОДОЛЖАЕШЬ ПАСТУЛИРОВАТЬ фундаментальные взаимодействия и тут же говоришь про ложность и блядь, дальше я просто не вижу смысла о чем-то говорить. Ты не понимаешь что несешь. Вот ты пизди сколько угодно, но постоянная Планка останется той же в нашей метрике. Что бы ты не пиздел, какие мантры не читал, скорость света в ваакуме не изменится. Если нас с тобой не будет как и всех человеков, константы не исчезнут и не изменяться. А у тебя всюду какая-то магия, всюду какие-то разумы выстраивают структуры смыслов-значений, и хуй с тобой если бы ты только это делал, но ты оставляешь фундаментальную величину и прилипляешь к ней еще одну из своего манямирка, в итоге у тебя
X=X+1
0=1
Ебал я с таким шизофреником общаться.
>Глазпринимает отраженный от них свет, но блядь это НЕ ИМЕЕТ НИКАКОГО ЗНАЧЕНИЯ.
Имеет. Отражать свет может любая другая хуйня, не только объект. Так с чего ты взял, что ты видишь именно объект?
Это не доказывает ничего, вот о чем я.
>Т.е. по твоему частица или некоторое количество частиц меня не является частью обьекта меня? Че несешь то?
Ты чувствуешь деформацию самого себя, а не объект. Объекта может и не быть, или он может быть не тем, чем ты думаешь. Ты чувствуешь, что объект твердый, поскольку ощущаешь деформацию как при соприкосновении с твердым телом. Однако если бы ты уебался мордой в силовое поле, то, наверное, тоже бы ощутил его как твердое, хотя оно нихуя не твердое - в нем нет вещества вообще. Более реалистичный пример - попытка разъединить два сильных магнита ощущается, как будто они были склеены, хотя там нет никакого клея (но физическое взаимодействие между частицами такое же, как и у склеенных вещей, отсюда и похожие ощущения). А попытка совместить два одинаковых полюса магнита ощущается как упругое взаимодействие (типа сжатия резинового мячика), хотя там тоже нет никакого упругого вещества между ними. В общем, твое чувство обманчиво, поэтому оно тоже ничего не доказывает.
>Вот ты пизди сколько угодно, но постоянная Планка останется той же в нашей метрике
А останется ли наша метрика? В разных частях вселенной она может быть разной, и это не я придумал. Более того, параллельно с нашим миром, в "том же самом" пространстве-времени могут находиться другие объекты: если они с нашими объектами физически не взаимодействуют, то мы их не в состоянии ощущать их, да и вообще обнаружить. Причем, как показывают некоторые статьи, для того, чтобы одни объекты никак не взаимодействовали с другими, достаточно немного других констант - той же постоянной Планка, например. То есть представь, что в твоем рту сейчас может находиться залупа немытого бомжа из параллельного мира с другой постоянной Планка. Тебе даже не нужно сидеть с открытым ртом для этого - член бомжа проходит сквозь твои губы, зубы, а ты (и бомж) этого не ощущаете потому, что атомы члена бомжа и атомы твоего рта физически не взаимодействуют. И этот пример снова поднимает вопрос: что существует, а что - нет? Не относительное ли это понятие, зависимое от наблюдателя?
Ну и чтобы совсем развеять твои сомнения, абсолютно физический мысленный эксперимент, который рассматривается физикой. Какую-нибудь частицу, скажем, электрон, затянуло в черную дыру. Существует она теперь или нет?
И да, всякие электрослабые взаимодействия, которые я ПАСТУЛИРУЮ, вполне могут быть всего лишь математическими выкладками, уравнениями, которым подчиняется энергия.
Давай такой мысленный эксперимент. Берем учебник физики, берем суперкомп (или даже просто человека поумнее - все равно человеческий мозг в этой деятельности суть вычислитель), моделируем все параметры всех частиц в нашей Вселенной, ну или хотя бы всех частиц проперженной квартиры какого-нибудь Васи, вместе с самим Васей, который в ней находится. Пользуясь уравнениями эволюции частиц, просчитываем поведение всей этой системы во времени. На наших глазах смоделированная на компьютере кучка частиц Вася сидит за компом, читает /sci, чешет жопу и говорит: "Информация, блять, понавыдумают себе хуйни, ептыбля. Где в си единица измерения информации? А? А, ептыбля? Вот, блядь, гравитация, вот фотон-электрон, ептыбля, они все существуют, я их вижу, я их ощущаю, а информация где, а, сука? Где информация, ептыбля? Шизофреники ебаные". Вычисления останавливают, и история Васи обрывается. Существовал Вася, или нет? Существовало ли то, что он видел, слышал, ощущал? Если нет, то почему он был так уверен, что существовало?
Теперь самое главное - а нужен ли вычислитель для этого? Уравнения и числовые параметры начинают существовать только тогда, когда их начинают вычислять, что ли? А как же волшебное математическое слово "рассмотрим"? Вот рассмотрим параметры как в квартитре Васи, и покажем, что тогда он обязан будет сидеть за компьютером и чесать жопу. Нужно ли для этого моделировать Васю на компьютере, чтобы он начал существовать, или он и так уже существует, раз такие параметры его формируют? И нужно ли вообще выводить математику, физику, все эти уравнения, если и так понятно, что эти уравнения с теми параметрами породят Васю? И нужно ли нам самим существовать, чтобы нам было понятно, что так можно породить Васю? Может быть, для существования Васи достаточно ИНФОРМАЦИИ о том, что все это способно породить Васю?
Блестяще. УМТ с такого ракурса мне ещё не показывали.
Вот бутылка с водкой, так называемый спиртуоз.
А рядом вы видите Николая Ивановича Серпухова.
Вот из бутылки поднимаются спиртуозные пары. Поглядите, как дышит носом Николай Иванович Серпухов. Видно, ему это очень приятно, и главным образом потому что спиртуоз.
Но обратите внимание на то, что за спиной Николая Ивановича нет ничего.
Не то чтобы там не стоял шкап или комод, или вообще что-нибудь такое, а совсем ничего нет, даже воздуха нет. Хотите верьте, хотите не верьте, но за спиной Николая Ивановича нет даже безвоздушного пространства, или, как
говорится, мирового эфира. Откровенно говоря, ничего нет.
Этого, конечно, и вообразить себе невозможно.
Но на это нам наплевать, нас интересует только спиртуоз и Николай Иванович Серпухов.
Вот Николай Иванович берет рукой бутылку со спиртуозом и подносит ее к своему носу. Николай Иванович нюхает и двигает ртом, как кролик.
Теперь пришло время сказать, что не только за спиной Николая Ивановича, но впереди, так сказать перед грудью и вообще кругом, нет ничего. Полное отсутствие всякого существования, или, как острили когда-то: отстутствие
всякого присутствия.
Однако давайте интересоваться только спиртуозом и Николаем Ивановичем.
Представьте себе, Николай Ивановия заглядывает во внутрь бутылки со спиртуозом, потом подносит ее к губам, запрокидывает бутылку донышком вверх и выпивает, представьте себе, весь спиртуоз.
Вот ловко! Николай Иванович выпил спиртуоз и похлопал глазами. Вот ловко! Как это он!
А мы теперь должны сказать вот что: собственно говоря, не только за спиной Николая Ивановича, или спереди и вокруг только, а также и внутри Николая Ивановича ничего не было, ничего не существовало.
Оно, конечно, могло быть так, как мы только что сказали, а сам Николай Иванович мог при этом восхитительно существовать.Это, конечно, верно. Но, откровенно говоря, вся штука в том, что Николай Иванович не существовал и не
существует. Вот в чем штука-то.
Вы спросите: «А как же бутылка со спиртуозом? Особенно, куда вот делся спиртуоз, если его выпил несуществующий Николай Иванович? Бутылка, скажем, осталась, а где же спиртуоз? Только что был, а вдруг его и нет. Ведь Николай
Иванович не существует, говорите вы. Вот как же это так?»
Тут мы и сами теряемся в догадках.
А впрочем, что же это мы говорим? Ведь мы сказали, что как внутри, так и снаружи Николая Ивановича ничего не существует. А раз ни внутри, ни снаружи ничего не существует, то значит, и бутылки не существует. Так ведь?
Но с другой стороны, обратите внимание на следующее: если мы говорим, что ничего не существует ни изнутри, ни снаружи, то является вопрос: изнутри и снаружи чего? Что-то, видно, все же существует? А может, и не существует.
Тогда для чего же мы говорим изнутри и снаружи?
Нет, тут явно тупик. И мы сами не знаем, что сказать.
До свидания.
Снимаю шляпу перед вашим изящным, полном и противоречивым доказательством.
Поскольку ты явно не уловил посыл, опишу суть максимально сжато и емко.
Все параметры, все поведение частиц в нашей вселенной описываются параметрами (числами), законами (уравнениями). Пусть некоторые вещи, некоторые параметры мы сами, части этой Вселенной, не можем измерить (принцип неопределенности), но они есть, и их достаточно для описания поведения этих вещей. Все наше взаимодействие с окружающим миром, все эмпирические свидетельства существования этого мира вокруг, описываются и объясняются все теми же законами, уравнениями, числами. У нас нет ни одной вещи, ни одного явления, которые мы не объяснялись бы числами и уравнениями. Тогда, пользуясь бритвой Оккама, мы должны заключить, что все вокруг - и есть числа, уравнения, и ничего больше. Философские вскудахи о материальности, существовании, реальности, объективной реальности, независимости от наблюдателя - все это не дает никаких новых знаний по сравнению с числами и уравнениями. Значит, они не нужны. Как бог. Как душа. Как прочие выдумки людей, которые всего этого не знали.
Меня откровенно заебало переливать из пустого в порожнее, но без нас тред скатывается в совсем лютый неадекват, поэтому давайте продолжать банкет потихоньку.
Ты просто не понимаешь, что такое NP. А это nondeterministic polynomial, то бишь тебе достаточно угадать решение задачи - а проверить догадку можно сравнительно просто. То, что у тебя может быть экспоненциальное количество потенциальных решений - не значит, что ты их будешь все перебирать. Динамическое программирование, ветви и границы, эвристики - значительно снижают количество необходимых вычислений. Поэтому многие NP-полные и даже NP-трудные (где нельзя быстро проверить решение) задачи вполне себе решаются. Например, 3SAT вполне себе заходит с миллионами переменных.
В криптографии же прекрасно подбираются пароли - по словарю или алгоритму генерации. Особенно если есть хеш, и особенно если он не солёный (сплошь и рядом такое, кстати). Думаешь, почему после кражи базы аролей всех юзеров предупреждают и иногда заставляют сменить пароль. Или почему replay-атаки в протоколах так опасны.
> И чем длиннее твоя арифметика, тем дольше тебе ждать этой стабилизации.
Для сложение и умножение скорее всего количество последовательных элементов пропорционально логарифму разрядности. Аналогично, "длинные" числа можно прекрасно и быстро складывать SIMD-командами или на FPGA.
> но длина такта для всех операций одинакова, причём взята с запасом.
У процессора есть накладные расходы на выполнение команды, которые выше, чем стоимости собственно операции сложения. При сложении тебе важнее, где именно лежат операнды (регистры, константа в инструкции, кэш), чем их разрядность.
> длина такта для всех операций одинакова, причём взята с запасом.
Длина такта взята не на основе стоимости операций в АЛУ, а на основе того, как работает цикл выполнения команд.
> Увеличить количество логических вентилей в 1.5 - 2 раза дорого
По закону Мура это происходит раз в два года. А хули делать.
Ты просто не понимаешь, что такое NP. А это nondeterministic polynomial, то бишь тебе достаточно угадать решение задачи - а проверить догадку можно сравнительно просто. То, что у тебя может быть экспоненциальное количество потенциальных решений - не значит, что ты их будешь все перебирать. Динамическое программирование, ветви и границы, эвристики - значительно снижают количество необходимых вычислений. Поэтому многие NP-полные и даже NP-трудные (где нельзя быстро проверить решение) задачи вполне себе решаются. Например, 3SAT вполне себе заходит с миллионами переменных.
В криптографии же прекрасно подбираются пароли - по словарю или алгоритму генерации. Особенно если есть хеш, и особенно если он не солёный (сплошь и рядом такое, кстати). Думаешь, почему после кражи базы аролей всех юзеров предупреждают и иногда заставляют сменить пароль. Или почему replay-атаки в протоколах так опасны.
> И чем длиннее твоя арифметика, тем дольше тебе ждать этой стабилизации.
Для сложение и умножение скорее всего количество последовательных элементов пропорционально логарифму разрядности. Аналогично, "длинные" числа можно прекрасно и быстро складывать SIMD-командами или на FPGA.
> но длина такта для всех операций одинакова, причём взята с запасом.
У процессора есть накладные расходы на выполнение команды, которые выше, чем стоимости собственно операции сложения. При сложении тебе важнее, где именно лежат операнды (регистры, константа в инструкции, кэш), чем их разрядность.
> длина такта для всех операций одинакова, причём взята с запасом.
Длина такта взята не на основе стоимости операций в АЛУ, а на основе того, как работает цикл выполнения команд.
> Увеличить количество логических вентилей в 1.5 - 2 раза дорого
По закону Мура это происходит раз в два года. А хули делать.
Про тебя я тоже помню, педрила.
Пароли в основной своей массе выбираются не равновероятно, иначе никаких словарей бы очевидно не было. Будут выбирать равновероятно (как и должны по требованиям) - соснут твои словари. И то же самое касается всех остальных эвристик.
Ещё раз тебе напоминаю, NP-полная задача - это не решить один конкретный инстанс, и не решать инстансы из какого-то меньшего подмножества входов. Это решать для любого входа. А то, что можно обосрать любую защиту, не следуя требованиям - об этом можешь мне не рассказывать.
В 1936 году советский ученый Владимир Лукьянов построил первую в мире водяную вычислительную машину, способную решать дифференциальные уравнения в частных производных. Вычисления производились с помощью соединенных между собой колб и трубок с водой.
Аналогичные «компьютеры» существовали в Советском Союзе с конца 1920-х годов. Вода в них располагалась в колбах на разных уровнях, каждый из которых означал определенное число или параметр. Напор потока между колбами служил для математических операций. Подобные устройства использовались в геологии, металлургии, теплофизике и ракетостроении для того, чтобы в лабораторных условиях воспроизводить явления, наблюдаемые на промышленных объектах.
«Гидравлический интегратор» Лукьянова появился с практической целью: требовалось исследовать влияние различных температур на бетон, а существующие методы вычисления оказались слишком медленными и давали приблизительные данные.
Процесс работы водяного компьютера Лукьянова выглядел примерно так: вода протекала по трубкам и колбам, а оператор мог увидеть (в прямом смысле), что произойдет, если изменить структуру бетона или увеличить его прочность. Откройте клапан или поверните один из рычагов – и уровень воды в разных колбах изменится, показывая, как изменятся физические свойства бетона, его температура или время затвердевания. Одновременно все изменения отмечались на миллиметровой бумаге.
Аналогичные «компьютеры» существовали в Советском Союзе с конца 1920-х годов. Вода в них располагалась в колбах на разных уровнях, каждый из которых означал определенное число или параметр. Напор потока между колбами служил для математических операций. Подобные устройства использовались в геологии, металлургии, теплофизике и ракетостроении для того, чтобы в лабораторных условиях воспроизводить явления, наблюдаемые на промышленных объектах.
«Гидравлический интегратор» Лукьянова появился с практической целью: требовалось исследовать влияние различных температур на бетон, а существующие методы вычисления оказались слишком медленными и давали приблизительные данные.
Процесс работы водяного компьютера Лукьянова выглядел примерно так: вода протекала по трубкам и колбам, а оператор мог увидеть (в прямом смысле), что произойдет, если изменить структуру бетона или увеличить его прочность. Откройте клапан или поверните один из рычагов – и уровень воды в разных колбах изменится, показывая, как изменятся физические свойства бетона, его температура или время затвердевания. Одновременно все изменения отмечались на миллиметровой бумаге.
Ого что тут у вас в наукаче есть. В програмаче нет треда про олимпиадное программирование можно у вас задачки обсуждать? Без привязки к конкретному ЯП конечно. Там же всё таки алгоритмы нужно составлять и всё такое.
Можно, неси, пообсуждаем.
Отлично. Когда будут приду к вам, а не программистам.
>мой уровень повыше гораздо будет
Расскажи.
>Как же им удаётся выполнять сложение, в котором надо учитывать перенос из младших разрядов
Система остаточных классов.
> при использовании стека адреса локальных переменных фиксированы относительно верхушки стек
Относительно базы фрейма они фиксированы, а не верхушки стека. Верхушка стека может ездить куда хочет, когда ты аргументы для printf туда складываешь. Но так как вызвать в C printf можно только с заранее известным числом аргументов, то в x86_64 ABI индексируют от RSP, а сам RSP отодвигают в начале функции так, чтобы поместились все аргументы. Но это скорее исключение, чем правило.
> почему локальные переменные во всех(или почти всех) известных языках хранятся на стеке?
Для re-entrancy. Если re-entrancy не нужна, то можно хранить вообще по фиксированному адресу, раньше вообще рядом с кодом функции прямо хранили, когда компиляторы были однопроходные.
Для re-entrancy. Если re-entrancy не нужна, то можно хранить вообще по фиксированному адресу, раньше вообще рядом с кодом функции прямо хранили, когда компиляторы были однопроходные.
>Система остаточных классов.
Хорошая штука, но это всё же не
>компьютеры выполняют операции над битами в представимых числах параллельно.
Где-то я видел пейперы по поводу устройств, которые могут складывать числа параллельно, используя непозиционные системы счисления.
В смысле параллельно для каждого бита.
Что такие устройства делают с числами, у которых битов больше, чем у устройства параллелей? Вылетают с ошибкой?
Да.
Ну и нафиг они нужны? В той же криптографии надо работать с 2048-битными числами. Есть там столько параллелей?
О, интересно.
Зачем в языках программирования константы? Они быстрее переменных работают?
mov [a], b быстрее, чем mov [a], или просто с ними удобнее?
mov [a], b быстрее, чем mov [a], или просто с ними удобнее?
Для того, чтобы искоренить ряд трудноуловимых ошибок, связанных с "даун-погромист нечаянно присвоил что-то куда-то не туда" еще на стадии компиляции.
>mov [a], b быстрее, чем mov [a], или просто с ними удобнее?
mov - операция перемещения данных, в наборе команд IA-32 (вряд ли тебя интересует какая-то другая архитектура) у нее не может быть одного операнда. Различий по скорости между mov r, r и mov r, i в современных процессорах нет.
Поясните за О большое. Я уже пятый раз из разных источников про него читаю и нихуя не понимаю. Дайте может статью где про это хорошо на русском поясняют.
Для функции f, O(f) - это класс всех функций g, таких, что предел при стремлении к плюс бесконечности функции g / f равен константе (т.е. существует). Таким же образом обозначается (какой-либо) представитель этого класса. То есть, равенство g = O(f) означает, что g равна некоторому представителю класса O(f), т.е. сама является представителем этого класса, т.е. lim g/f = C - const.
В теории сложности алгоритмов O-нотация часто используется для классификации функций по скорости их роста при стремлении к плюс бесконечности. Если функция g растет асипмтотически (т.е. при стремлении к плюс бесконечности) быстрее другой функции f, то можно найти такое значение X, что для всех x>X будет выполняться неравенство g(x) > f(x). Говоря простым языком, функция g рано или поздно (еще говорят "при достаточно больших x" или "на бесконечности") обгонит функцию f.
Основное применение этого аппарата в теории сложности такое. Пусть g(n) и f(n) отражают время работы алгоритмов G и F на входах n. Если мы теперь хотим узнать, какой из этих алгоритмов стоит выбрать для работы с данными, размер которых может неограниченно увеличиваться, то предпочтение стоит отдать тому из них, чья функция временной сложности будет асипмтотически медленнее, поскольку это означает, что другой алгоритм рано или поздно начнет работать медленнее его (тратить больше времени), причем вне зависимости, кто их них работает быстрее на маленьких данных и насколько быстрее.
Некоторые классы сложности (линейная, квадратичная, полиномиальная, экспоненциальная, и т д) можно посмотреть на википедии.
И да, самую соль упустил. g = o(f) означает, что функция g растет асимптотически медленнее функции f. g = O(f) означает, что функция g растет не быстрее функции f (т.е. либо медленнее, либо имеет такой же порядок роста).
ПОШЕЛ НАХУЙ СО СВОЕЙ ПСЕВДОНАУКОЙ
Ничего не понял. Можно пример?
Запросто. Можно легко доказать, что x = o(x^2) (линейный рост медленнее квадратичного). Теперь бери любую систему компьютерной алгебры, или язык программирования, и делай следующее:
1) Выбери любую функцию вида x + A, где A - некоторое тобою выбранное число
2) Выбери любую функцию вида x^2 + B x + C - некоторые тобою выбранные числа.
3) Построй графики этих функций
4) Убедись, что с какого-то момента график функции x^2 + ... будет всегда выше графика функции x + ...
5) Попытайся перевыбрать A, B и C так, чтобы квадратичная функция не обгоняла линейную ни с какого момента.
6) Пытайся до тех пор, пока не станет интуитивно понятно, что это невозможно
7) Это означает, что величины A, B и C не влияют на то, какая функция обгонит какую на бесконечности.
8) В вольфрам альфе посчитай предел отношения линейной функции к квадратичной (т.е. функции (x + A) / (x^2 + B x + C) ) при стремлении к плюс бесконечности для тех A, B и C, которые ты выбирал ранее
9) Убедись, что этот предел также не зависит от A, B и C и всегда равен 0.
10) Перечитай те мои посты, которые ты не понял
>5) Попытайся перевыбрать A, B и C так, чтобы не возникало такой ситуации, что квадратичная функция обгоняет линейную с какого-то x и во всех последующих x вплоть до бесконечности (т.е. чтобы графики "чередовались" - то один выше, то другой, и так сколько угодно раз)
поправил
А где умножение на константу про которые в первых постах говоришь? Те константы что в этом поте только перемещает функцию по графику никак её не изгибая.
Умножение на константу - это во сколько раз одна функция выше (быстрее) другой на бесконечности. Можешь проделать все то же самое для функций x^2 + ... и 2x^2 + ... . И убедиться, что для достаточно больших х график два-икс-квадрата лежит примерно вдвое выше икс-квадрата (и чем больше x, теб ближе это отношение к двойке). Для икс-квадрата и икса же, график икса (на совместной картинке) опускается все ниже и сливается с осью ox, что означает, что отношение их скоростей неограниченно возрастает.
>Для икс-квадрата и икса же, график икса (на совместной картинке) опускается все ниже и сливается с осью ox, что означает, что отношение их скоростей неограниченно возрастает.
>При этом можно брать не только x, но и 2x, 100x, 1000000x - все равно график икс-квадрата растет все быстрее, чем график константа-икса. То есть константа в этой ситуации не решает.
дополнил
Ну и из всего этого надо сделать вывод, что есть такие функции, которые растут в конечное число раз одна быстрее другой, а есть такие, которые растут в бесконечное число раз одна быстрее другой. Именно это и отражает О-нотация: о-малое означает, что функция бесконечно медленнее, О-большое означает, что функция в конечное число раз медленнее (или быстрее). Логично и интересно объединить функции, скорости которых отличаются в конечное число раз, в один класс, и выяснить, сколько таким образом возникает классов и как они соотносятся друг с другом (например, попытаться найти самые-самые быстрорастущие (или медленнорастущие) функций). Это и помогает сделать O-нотация.
Ну и для закрепления пара заданий:
1) Найти пару таких функций, что на бесконечности ни одна из них не быстрее другой: то одна выше, то другая. Придумать критерий такого взаимоотношения функций, используя предел их отношения.
1б) Найти пару таких функций из пункта 1). которые при этом неограниченно растут.
2) Придумать какой-нибудь класс функций, лежащий:
a) между O(x) и O(x^2)
б) между O(1) и O(x)
в) между O(1) и O(log x)
в) ниже O(1)
г) выше O(e^x)
д) выше O(x!)
e) между O(x^n) и O(e^x) для всех натуральных n
Огнетушитель в конце коридора.
ЕДИНСТВЕННОЕ "ДОСТИЖЕНИЕ" КОМПЬЮТЕР СЦАИНСА
ЕТО "ТЕОРИЯ СЛОЖНОСТИ АЛГОРИТМОВ"
КОТОРАЯ
1. ТРИВИАЛЬНА
2. ИМЕЕТ ОЧЕНЬ ОГРАНИЧЕННОЕ ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ
ВО ВСЕХ ОСТАЛЬНЫХ ОБЛАСТЯХ ОДНИ СПЛОШНЫЕ ОБОСРАМСЫ
ЕТО "ТЕОРИЯ СЛОЖНОСТИ АЛГОРИТМОВ"
КОТОРАЯ
1. ТРИВИАЛЬНА
2. ИМЕЕТ ОЧЕНЬ ОГРАНИЧЕННОЕ ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ
ВО ВСЕХ ОСТАЛЬНЫХ ОБЛАСТЯХ ОДНИ СПЛОШНЫЕ ОБОСРАМСЫ
ок
ИНЫМИ СЛОВАМ "КОМПЬЮТЕРНЫЕ УЧЕНЫЕ" ЕТО СЕКАТА БЕСПОЛЕЗНЫХ ПИЗДОБОЛОВ КОТОРЫЕ СОБРАЛИСЬ ВМЕТСЕ И ТУПЯТ КОЛЛЕТИВНА
ЧТОБЫ ЗАНИМАТСЯ МАТЕМАТИКОЙ ИЛИ ИНЖЕНЕНРИЕЙ ПРОГРАМИРОВАНИЯ У НИХ НЕ ХАВТАЕТ УМА
ПОЕТОМУ ОНИ ПРИДУМАЛИ СВОЙ МАЯНЯМИРОК И НАДРАЧИВАЮТ ДРУГДРУГУ ПЕНИСЫ
И здесь логикоебы, уже второй тред засирают. Пидорните их в отдельный загон.
Поясните популярным языком почему процесс не рассчитанный на многопоточность загружает только одно ядро на 100% не трогая другие для человека который не знает слово многопоточность.
Потому что ты сделал хуево, вот почему.
Поясните насчет текстмайнинга. А точнее насчет текстмайнинга текстов уровня пикрелейтед. Это вообще реально?
>Сразу же подброшу годноты, являющейся классикой CS.
>https://ru.wikipedia.org/wiki/Стек
>https://ru.wikipedia.org/wiki/Обратная_польская_запись
data Nat = Zero | Succ Nat
Ну смотри, вот ты не рассчитан на многопоточность. Ты умеешь одновременно дрочить, кушать и разгадывать капчу? Наверное нет. Вот так и процесс, не рассчитанный на многопоточность, не умеет делать одновременно больше одной вещи. Более того, он вообще не знает, что так можно.
Даже в одном потоке можно эмулировать многопоточное окружение и запускать потоки.
И? Как это относится к тому, что я сказал?
Мне кажется, что тебе следует перечитать изначальный пост с вопросом.
нет, мне тоже не понятно. вопрос - почему, если мой сраный скрипт однопоточно читает сотни мегов данных из файла, грузит их в оперативку и дрочит их там, выводя мне какой то результат, использует только одно ядро процессора. при том, что система может работать с несколькими ядрами, и вообще работа с ядрами чуть ли не на железном уровне реализована.
Потому что поток - это последовательность инструкций. Если эти инструкции выполнять не последовательно, а параллельно, что получится?
Скрыл дауна с двоичной системой.
Ну у тебя тоже "работа с ядрами" чуть ли не на "железном уровне" реализована - ты одновременно и дышишь, и перевариваешь пищу, и поддерживаешь температуру тела, и наблюдаешь мир, и ведешь внутренний диалог. Тем не менее... ты уже попытался дрочить, есть и двачевать одновременно?
Понятно что вообще все эти действия дискретных и на самом деле можно одной рукой бросить а другой жевать хавку, попеременно двачуя. А если сделать третью руку то и капчевать можно паралельно. Или можно тремя руками двачевать, только двачевать, ну или руку менять при дрочке. Так какого же хера не могу менять ядро? Почему юзается строго одно? Пусть типа все ядра руки делают по дешке общего дела, если все это дело уже в общей оперативке например
Уточню. Я понимаю почему так происходит, но мне надо было пояснить это другу. А т.к. он не знал про многопоточность я начал не внятно нести бред про то что "процесс выполняется на доном ядре т.к. его промежуточные вычисления лежат в регистрах этого ядра и команды ассемблера выполняются последовательно, а им нужно знать значения из регистров поэтому распределить между двумя ядрами невозможно, а перебросить процесс целиком бессмысленно." Но он этого похоже не понял. Может есть попроще объяснение?
> почему процесс не рассчитанный на многопоточность загружает только одно ядро на 100% не трогая другие
Потому что для выполнения этого процесса достаточно одного ядра.
>все эти действия дискретных и на самом деле можно одной рукой бросить а другой жевать
Что блядь?
Никогда руками не жевал?
Это называется "шизофазия".
Попробую ответить без использования Гугла и знания ответа.
Возможно причина в том, что локальные переменные могут объявляться и назначаться в произвольные моменты времени, тогда как глобальные доступны всегда и везде.
Вот есть у нас в программе например 1000 функций, в которых по 5 локальных переменных. И каждая эта функция вызывается в непредсказуемые моменты времени. Да, можно конечно выделить память для каждой этой переменной, но это невыгодно в плане количества памяти занятой (это будет 20 кб, допустим). Если в программе, допустим, функция вызывается всего один раз, то нет смысла держать выделенной память для той переменной, которая уже никогда не будет вызвана. Притом компилятор не может предсказать действительно ли она не будет использована или нет ещё раз.
Стек - это "динамическая" память, в которой данные появляются и исчезают по мере того, как они используются. {ассемблер} Ты переносишь, например, передаваемый аргумент функции в стек, затем вызываешь эту функцию и функция из стека достает переданные ей аргументы и раскладывает по соответствующим регистрам, выполняет свои действия и в стек заносит результат.
Проще говоря стек выгодно использовать информационно. "Удалять" из статической памяти значения просто так не получится, потому что в ассемблере динамические адреса к отделам крайне сложно и притом опасно организовывать. А если одна функция изменит память, которая потом будет использоваться другой? В общем хуйня будет. Стек гораздо надежнее и организовываннее в этом плане.
Повторюсь: я нихуя не знаю ответа, я просто предположил.
Бумп
ну естественно было написано не бросить а дрочить, автозамена помогла. но анон выше мне пояснил за локальные адреса в оперативке для каждого ядра. я например думал что все адреса доступны каждому ядру, а не для каждого свои. если реализовано именно так, что для каждого ядра свои, то мне понятно всё понятно.
нет, обьяснение хорошее. просто ему возможно сперва надо пояснить за ассемблер вообще. так то ясен хер, что без преобразований лоренца трудновато будет обьяснить как посчитать сложение скоростей двух тел, летящих со скоростями близкими к скорости света например. но это не проблема преобразований лоренца, это проблема того, кто их не знает
Есть ли какие-то алгоритмы, которые позволяют быстро-быстро перестроить фрактал?
> процесс не рассчитанный на многопоточность
Другими словами, это программа специально и преднамеренно написанная так, чтобы
> загружать только одно ядро на 100% не трогая другие
Поэтому, даже если на самом деле она будет выполняться на шестнадцати ядрах, при корректной работе процессора и операционной системы, результат не будет отличаться от того, как если бы она выполнялся на одном.
Т.е. на любых, совместимых с данной программой, комбинациях железа и операционных систем, для конечного пользователя, она всегда будет
> загружать только одно ядро на 100% не трогая другие
Так как это неотъемлемая часть функционала данной программы, а поэтому должна в точности воспроизводиться при её выполнении.
Дело не в ассемблерах, и не в архитектуре. Дело в том, что программа/алгоритм имеет зависимости по данным(результат предыдущих инструкций используется в следующих), которые мешают "без задней мысли" просто взять и распараллелить. Зачастую, чтобы параллелить программу пользуются некоторыми свойствами алгоритма/операций, программу распараллелить можно по-разному даже в самых простых случаях. К примеру, чтобы просуммировать массив параллельно(грубо говоря, разбить сумму на куски) мы пользуемся ассоциативностью сложения.
Еще фича в том, что даже в параллельных программах необходимы куски кода с гарантированной атомарностью/последовательным выполнением для предотвращения т.н. data races - отсюда всякие синхронизации/разделение ответственности на модификацию/чтение общих данных/копирование данных - у каждого свой экземпляр - опять же программист должен заморачиваться, где, чего и как, организация этого процесса прямиком влияет на производительность. Есть также специальные структуры данных, оптимизированные под параллельное выполнение операций. Соответственно, универсального алгоритма "само собой распараллелься" без модификации кода программистом пока что нет.
Пасани, что вы думаете про homestuck?
Дело как раз в архитектуре (и, как следствие, - в ассемблере для данной архитектуры). Для data deriven design будет получаться мелкодисперсная каша из команд, которые можно почти свободно распылять по ядрам. Гугли Multiclet.
>Multiclet
Это, как я понял, DSP с MIMD-архитектурой.
см.
>https://ru.wikipedia.org/wiki/MIMD
>В MIMD могут возникнуть проблемы взаимной блокировки и состязания за обладание ресурсами, так как потоки, пытаясь получить доступ к ресурсам, могут столкнуться непредсказуемым способом. MIMD требует специального кодирования в операционной системе компьютера, но не требует изменений в прикладных программах, кроме случаев, когда программы сами используют множественные потоки (MIMD прозрачен для однопоточных программ под управлением большинства операционных систем, если программы сами не отказываются от управления со стороны ОС). И системное, и пользовательское программное обеспечение, возможно, должны использовать программные конструкции, такие, как семафоры, чтобы препятствовать тому, чтобы один поток вмешался в другой, в случае если они содержат ссылку на одни и те же данные. Такое действие увеличивает сложность кода, снижает производительность и значительно увеличивают количество необходимого тестирования, хотя обычно не настолько, чтобы свести на нет преимущества многопроцессорной обработки.
Да и если бы ты был прав, проблема параллелизации решалась бы на уровне компилятора языков высокого уровня, не было бы такого многообразия на уровне алгоритмов, структур данных, тех же моделей/подходов к программированию параллельных вычислений - не имеющих к архитектурам и ассемблерам отношения.
Если бы ты был прав, то колесо никогда бы не изобрели только потому, что когда-то люди обходились без колёс.
Да, мультиклет - не серебряная пуля, преобразовывающая любой линейный алгоритм в параллельный. Это способ изначально строить алгоритм в парадигме минимизации зависимостей между данными. Эта парадигма ближе всего к функциональному программированию, наконец пробравшемуся в энтерпрайз из академических кругов. Всё это происходит не просто так, а под давлением потребности в управлении сложностью современных проектов, которые становятся всё сложнее для "голого" компонентного/объектного описания.
(Имел ввиду DDD вообще, а не Мультиклет в частности.)
Это из кусра SIСP?
Дедушка Кнут загрустил...
Есть мнение, что подавляющее большинство будущих погромистов после выпуска будет работать в апликухах и им cs нафиг не нужно, а нужно именно computer programming но так увы не бывает. В discrete math будешь дрочить пруфы, индукцию, рекурсию, number theory и ти тд. И даже удивишься как изъебисто можно объяснять такие простые вещи как if statement
Поясните, аноны, как происходит параллельный доступ к shared-памяти без блокировок? То есть как память может одновременно отвечать n ядрам?
Лол, решил Мочизуку компьютером пруфануть? Тоже об этом думал. Если да, давай отдельный тред создадим, есть мысли. Конкретно, с этими его "картинками" придётся работать вначале отдельно.
В начале треда шёл разговор про стек, локальне переменные, про то что локальные переменные являются моделью хранения временных значений и т.п.
Что об этом почитать? Можно на английском.
Что об этом почитать? Можно на английском.
Разделяют память на непрерывные фрагменты для каждого ядра, например. И разрешается доступ без блокировок только к своему участку.
Про стек и кучу на англовикипедии можно - именно в смысле модели переменных, а не структур данных. Ещё в тему - стековая машина или конечный автомат со стеком - забыл как точно называется.
Деревья дорого обрабатывать рекурсией, в цикле - быстрее.
Мне кажется, что это мнение относительно обоснованно. Но если хочешь быть крутым программиздом, а не быдлокодером и работать в "наукоемких" отраслях(параллельное программирование, игры/графика и визуализация, суперкомпьютинг/моделирование процессов, machine learning и нейросети всякие и.т.д.) - CS может пригодиться, но прям-таки дрочить на неё не рекомендуется(как и со всем остальным).
Можно построить что бы для некоторых n вычислялось так же быстро, нет?
Совсем забыл, что вы у меня есть. За утверждение:
>Моча < Говно < Комбинационная схема < Конечный автомат Автомат с магазинной памятью < Мошина Тьюринга.
В чем заключается разница возможностей данных автоматов?
>Моча < Говно < Комбинационная схема < Конечный автомат Автомат с магазинной памятью < Мошина Тьюринга.
В чем заключается разница возможностей данных автоматов?
Не молчите, отвечайте!
> разница возможностей
Объем памяти. МТ может вычислить любую вычислимую функцию. КА с бесконечной памятью становится МТ, без нее может вычислять только ограниченое (памятью) множество функций. Комбинационная схема не имеет памяти и множество функций которые она способна вычислять еще ограниченей чем у КА. Комбинационная схема дополненая памятью становится КА, дополненая бесконечной памятью - МТ.
>КА с бесконечной памятью становится МТ
Охуеть. Т. е. исходя из того, что ИРЛ не существует МТ с бесконечной памятью, то любой физически реализованный аналог МТ ничуть не лучше КА? К чему тогда все эти вскукареки про полноту по Тьюрингу?
И что насчет автомата с магазинной памятью? Он червь-пидор по сравнению с МТ, несмотря на бесконечную память.
> вскукареки про полноту
Полнотой обладают ЯП а не конструкции вычислительных машин. Я думаю большинство языков не ограничивают как либо доступную память.
> на бесконечную память
У него получается какбы не совсем бесконечная. В каждый конкретный момент его память ограничена стеком. Проблема в том чтобы вернутся назад ему выбросить часть информации. Тоесть при работа часть информации затирается. При "правильных" алгоритмах затирается только ненужная информация, но, возможно, не любые вычисления можно организовать подобным образом.
>Полнотой обладают ЯП а не конструкции вычислительных машин
Ну что же ты так, анон?
>В теории вычислимости исполнитель (множество вычисляющих элементов) называется тьюринг-полным, если на нём можно реализовать любую вычислимую функцию. Другими словами, для каждой вычислимой функции существует вычисляющий её элемент (например, машина Тьюринга) или программа для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями (возможно, при некотором кодировании входных и выходных данных).
Кароч, я не уверен, что отличие тут только объеме памяти, иначе никто бы не заморачивался на с ТМ и все бы хуячили на КА.
Тоже мне CS тред. За базовую хуйню пояснить не могут.
Бумп.
В существующих ограничениях на размер памяти и способов доступа к ней.
В частности у стекового автомата способ доступа – LIFO, у МТ такого ограничения нет.
>В существующих ограничениях на размер памяти
Что реальный КА, что реальная МТ имеют конечный объем памяти. Если дело только в ограничениях размера, то таким образом можно считать физические реализации этих машин эквивалентными. Однако, на деле дела обстоят по другому.
>способов доступа к ней
Ну разница стека и обычной памяти ясна. Но что с памятью автомата? К ней же по сути полный доступ есть в отличии от стека, значит КА должен быть мощнее.
>на деле дела
Пиздец я ебанутый.
>>способов доступа к ней
>Ну разница стека и обычной памяти ясна. Но что с памятью автомата? К ней же по сути полный доступ есть в отличии от стека, значит КА должен быть мощнее.
Иными словами ты хочешь сказать, что при построении реальных физических моделей стекового КА и МТ, можно в КА помимо стека выделить столько состояний сколько ячеек в ленте МТ?
Если говорить не о физических моделях, то поскольку лента в МТ бесконечной длины и доступ к её ячейкам неограничен, то МТ мощнее стекового КА у которого доступ к стеку бесконечной длины ограничен LIFO.
>бесконечной длины
неограниченной длины
>Иными словами ты хочешь сказать, что при построении реальных физических моделей стекового КА и МТ, можно в КА помимо стека выделить...
Погоди. Давай про стековую машину забудем пока и обсудим обычный КА который без стека. который со стеком вообще вроде КА не называют, просто стековая машина или автомат с магазинной памятью и МТ. И таки да, я имею в виду, что будет, если выделить для КА столько состояний, сколько памяти они заняли бы в МТ?
>Если говорить не о физических моделях, то поскольку лента в МТ бесконечной длины и доступ к её ячейкам неограничен, то МТ мощнее стекового КА у которого доступ к стеку бесконечной длины ограничен LIFO.
Тут в принципе понятно.
Да, 'К' в стековом автомате не нужна (что странно, ведь там множество состояний тоже конечно).
Так, имеются две вычислительные модели: МТ с лентой ограниченной некоторым числом, и КА. Докажем, что эти модели эквивалентны, в самом деле поскольку лента ограничена, то число всех конфигураций МТ ограниченно значит для каждой конфигурации выделим состояние в КА, тогда можно показать, что для каждого вычисления МТ существует вычисление в КА (доказывается по индукции на длину вычисления).
>Так, имеются две вычислительные модели...
Отлично, допустим, ты доказал эквивалентность этих машин. К чему тогда все эти разговоры про Тюринг-полноту реальных вычислителей? Может дело не в количестве памяти, а в чем-то еще?
Какие разговоры? Причём здесь Тюринг полнота?
>Причём здесь Тюринг полнота?
Иногда говрят: "Эта машина (не )обладает полнотой по Тьюрингу". Т. е. эквивалентна/не эквивалентна ей. Причем говорят так о реальных языках и машинах. Нахуй так говорить, если по твоей логике ей будет эквивалентно любое говно уровня конечного автомата?
Во-первых полнота по Тьюрингу определяется относительно МТ, а не МТ с ограниченной длиной ленты.
Во-вторых не мешай в одну кучу языки и машины.
>не мешай в одну кучу языки и машины.
Ты заебал.
>For instance, a language can be given as
>- ...>- those strings accepted by some automaton, such as a Turing machine or finite state automaton;
>Во-первых полнота по Тьюрингу определяется относительно МТ, а не МТ с ограниченной длиной ленты
Лан, давай так. Нахуй тогда нужен термин Машина Тьюринга, если согласно твоей логике можно просто говорить о КА с бесконечным числом состояний?
У МТ конечное число состояний.
>У МТ конечное число состояний.
А лента что, к состояниям не относится?
Нет.
Т. е. МТ = КА + лента, так?
Не нашел существенной разницы в формальных определениях. Вон бобер и вовсе как КА выглядит, ток с лентою.
И тем не менее разница есть.
Не мог бы ты, в таком случае, пояснить неофиту в чем она заключается?
Я дал тебе ссылки на статьи, ознакомься с ними и если по ним возникнут вопросы - попробую ответить.
Реквестирую простой и расжеванный туториал по типам нейросетей. Было бы замечтательно если вместе с интерактивненькими примерами, чтобы можно было в браузере ползунки подвигать меняя количество слоев и всего такого.
Подписался на тред.
Конструктивист-кун
Сейчас руковожу магистром-CSником
Конструктивист-кун
Сейчас руковожу магистром-CSником
Я тоже магистр-СSник, только я никому не нужен, можно тебе отдаться?
Теоретически да. Я даже больше скажу - у нас в лабе в Германии много денег и нужны люди для освоения средств, и мне рекомендуется нанять ещё двух как минимум но я никогда ни с кем не завожу контактов с борд попробуй найти сам и сделать вид, что ты не на дваче об этом узнал
А я и не с борд, только когда надо что-то спросить.
Переезжаю в Мюнхен. Холодно или гарячо?
ОП разбанился наконец(моча забанила за один пост связанный по её мнению с N-форсом). Попробую ответить.
Про термин "Комбинационная схема" ничё не знаю. Суть конечного автомата со стеком в том, что он проходит по входным данным(строке) один раз, с возможностью запоминать прошлые символы в стеке и обращаться к ним в LIFO порядке и состояния. Ограничение по кол-ву/направлению проходов видимо делает его менее мощным чем машина Тьюринга(могу ошибаться, это мои маня-фантазии)
Машина Тьюринга - это условно "программируемый" автомат, который может гонять по входным данным сколько угодно раз и куда угодно. Ещё у неё память для хранения промежуточных данных в том же "сегменте", что и входные данные.
Есть кто увлекающийся formal verification / automated theorem proving?
Какие есть эвенты в мире, куда можно сгонять посетить семинары там, что-то обучающее.
Какие есть эвенты в мире, куда можно сгонять посетить семинары там, что-то обучающее.
Я не увлекающийся, но мне любопытна эта область. Основы её в матлоге лежат, так? Есть ли в теоретической области подвижки по сравнению с алгеброй/исчислением предикатов(метод резолюций, если я не ошибаюсь - там основной результат)? Или сейчас всё больше в кодинг упирается?
Model checking.
Конечно, погугли про Bauer, Coquand, Brattka, Voevodsky, Bridges, Richman, Schwichtenberg.
В теор. области ещё constructive/computable analysis
Только что приехал с одной конференции узконаправленной по компсцаенсу. Спрашивали, а в каком, мол, у вас стране (я хохол) состоянии находится CS. Какие тенденции, и так далее. И чему в этом направлении обучают студентов. А я и брякнул: никаких, мол, даже названия такого нет. Теперь вот думаю, может, неправ был. Криптографию, говорю, проходим. Экспертные системы. Тогда на меня рукой вообще махнули: мол, не то это совсем.
Сейчас вот пролистал тредца по диагонали и не понял, чем вы тут занимаетесь. Где датамайнинг, где вычисления на службе смежных областей наук, моделирование экспериментов. CS она большая же, а наши умельцы вечно на нейросети соскальзывают. Хотя основы типа КА знать надо обязательно, да. Волшебный датамайнинг в своей основе всё равно имеет достаточно базовые вещи.
И регрессия, везде эта сраная регрессия.
Извините за неровный почерк, самолёт влияет.
Сейчас вот пролистал тредца по диагонали и не понял, чем вы тут занимаетесь. Где датамайнинг, где вычисления на службе смежных областей наук, моделирование экспериментов. CS она большая же, а наши умельцы вечно на нейросети соскальзывают. Хотя основы типа КА знать надо обязательно, да. Волшебный датамайнинг в своей основе всё равно имеет достаточно базовые вещи.
И регрессия, везде эта сраная регрессия.
Извините за неровный почерк, самолёт влияет.
> почему локальные переменные во всех(или почти всех) известных языках хранятся на стеке
Потому что удобней кучи — в её случае нужно следить за объемом потребляемой памяти. В стек тупо запушил, а когда закончил работу с функцией — выгнал назад. Но именно из-за таких пидорасов и возможен сам феномен переполнение буфера.
> Как это связано со структурой кода(независимо от языка)?
Потому что всё завязано на работе с коллбеками из этого самого стэка.
> Что из себя представляет эта "куча"?
Структуру данных для хранения информации о занятой и свободной памяти. С помощью всяких malloc, realloc и free мы работаем именно с ней.
Ну так то не удобнее, а быстрее наверное в первую очередь.
Так-то да. Помню, еще где-то читал о процессорах с нативной реализацией двух стеков — один для коллбеков, другой для промежуточных данных, но что из этого вышло — хуй знает. Мол работало на два процента медленнее, зато надёжней.
Два стека (опционально) в микроконтроллерах АРМ например. Один типа системный, другой для приложений. "In an OS environment, it is recommended that threads running in Thread
mode use the process stack and the kernel and exception handlers use the
main stack." Но на голом метале пох конечно, по дефолту стек един.
Насколько сложно понять как устроен интерпретатор, скажем, питона или руби? Если я прочитаю dragon book, я смогу понять, что там происходит?
Ты для начала должен понять как интерпретаторы в целом работают.
А что, сразу dragon book не прочитать?
Кстати, я погуглил, пацаны на so пишут, что dragon book устарела. А какие есть хорошие новые книги?
Раз уж кто-то всё-таки заинтересовался стеком в контексте локальных переменных - тогда вопрос. Предложите свои структуры/модель хранения переменных, выполняющих ту же функцию, что и стек и имеющую определенные преимущества/недостатки перед ним.
Моя модель:
Сортированный по ключу вектор с переменными, доступ к переменным по этому ключу а не адресу(бинарный поиск). Будет гораздо менее эффективней стека т.к. доступ не по индексу/адресу, но зато мы получим возможность "стирать" переменные в произвольном порядке, а не по LIFO
Моя модель:
Сортированный по ключу вектор с переменными, доступ к переменным по этому ключу а не адресу(бинарный поиск). Будет гораздо менее эффективней стека т.к. доступ не по индексу/адресу, но зато мы получим возможность "стирать" переменные в произвольном порядке, а не по LIFO
Какая-то у тебя странное компьютер сцайенс. Датамайнинг и вычисления ПРОТЕЙНОВ - это информатика, а не комплюктер сайенс, как по мне.
>Но именно из-за таких пидорасов и возможен сам феномен переполнение буфера.
Нет, не из-за этого.
SICP. Драгон бук уже полвека как не нужен - просто название красивое, вот и вспоминают до сих пор.
Регистры изобрел, ну охуеть.
Очередь вместо стека. http://nsl.com/k/xy/xy.htm
Не читая тред.
> почему локальные переменные во всех(или почти всех) известных языках хранятся на стеке?
На самом деле первым делом переменные принято хранить в регистрах. Регистры - это сверхбыстрая память (быстрее ОЗУ и стека), располагающаяся внутри процессора. Она удобна и достаточно производительна. Их (регистры) количество сильно ограничено и зависит (также как и скорость выполнения инструкций) от архитектуры процессора и разрядности. Так, в ARM их 17, а в Intel - 8. Проблема в том, что в том же Intel с одним из них ты взаимодействовать напрямую всё равно не можешь, так как он достаточно специфичен и хранит в себе указатель на место в коде, по которому находится следующая инструкция (EIP), которая будет выполнена, а другой регистр - указатель на текущую позицию в стеке (ESP). Если сильно захотеть, то можно зарезервировать значение ESP и работать с ним некоторое время (пока не выйдешь из функции), но работа со стеком у тебя будет осложнена либо вообще невозможна, как правило. Несанкционированное изменение регистра EIP привело бы к нарушению алгоритма предсказаний, из-за чего мы получили бы падение производительности.
Если в первом вопросе такой же контекст, как и во втором, то ответ немного другой: если тебе нужно быстрое сохранение значения какого-нибудь регистра, то стек - идеальное место для этого, так как он всегда под рукой и сохранение данных происходит благодаря всего одной инструкции, что удобно (не нужно выделять и освобождать память в куче, что создавало бы затраты). Можно временно хранить и в регистрах, но из-за очень ограниченного их количества такое, как правило, не делается.
> Почему нельзя "удалять" локальные переменные из памяти в произвольном порядке?
Если под локальными переменными подразумевается восстановление сохраненных регистров внутри вызванной функции, то неправильный порядок восстановления приведет к банальной смене местами этих переменных, из-за чего функция, которая вызвала эту функцию, может "повесить" всю программу.
Действий со стеком и регистрами, которые могут запустить подобный сценарий - очень много и у каждого свои нюансы, и если пытаться всё это дело разобрать, то ответ разрастется на несколько постов. Так что думаю, что этого хватит.
> Почему динамическую память называют памятью "на куче"?
Так принято. "Куча" происходит от имен функций HeapCreate/HeapAlloc/HeapFree, которые отвечают за инициализацию, выделение и освобождение памяти в оперативной памяти. Само по себе слово "куча" подразумевает кучку памяти, которую можно использовать в своих нуждах.
> Что из себя представляет эта "куча"?
Динамически выделенное место в оперативной памяти, которое ты можешь использовать для реализации классов, элементов массива, строк... чего угодно, в общем. Если ты пишешь на ассемблере и тебе нужно что-то больше стека, то можно воспользоваться кучей. Впрочем, если на любом высшем языке пишешь, то тоже можно воспользоваться кучей, если ситуация поджимает. В том же delphi процесс работы с динамической памятью автоматизирован, если ты работаешь с массивами и нативными строками, так что там вообще можно не задумываться ни о каких кучах - компилятор всё делает за тебя.
> почему локальные переменные во всех(или почти всех) известных языках хранятся на стеке?
На самом деле первым делом переменные принято хранить в регистрах. Регистры - это сверхбыстрая память (быстрее ОЗУ и стека), располагающаяся внутри процессора. Она удобна и достаточно производительна. Их (регистры) количество сильно ограничено и зависит (также как и скорость выполнения инструкций) от архитектуры процессора и разрядности. Так, в ARM их 17, а в Intel - 8. Проблема в том, что в том же Intel с одним из них ты взаимодействовать напрямую всё равно не можешь, так как он достаточно специфичен и хранит в себе указатель на место в коде, по которому находится следующая инструкция (EIP), которая будет выполнена, а другой регистр - указатель на текущую позицию в стеке (ESP). Если сильно захотеть, то можно зарезервировать значение ESP и работать с ним некоторое время (пока не выйдешь из функции), но работа со стеком у тебя будет осложнена либо вообще невозможна, как правило. Несанкционированное изменение регистра EIP привело бы к нарушению алгоритма предсказаний, из-за чего мы получили бы падение производительности.
Если в первом вопросе такой же контекст, как и во втором, то ответ немного другой: если тебе нужно быстрое сохранение значения какого-нибудь регистра, то стек - идеальное место для этого, так как он всегда под рукой и сохранение данных происходит благодаря всего одной инструкции, что удобно (не нужно выделять и освобождать память в куче, что создавало бы затраты). Можно временно хранить и в регистрах, но из-за очень ограниченного их количества такое, как правило, не делается.
> Почему нельзя "удалять" локальные переменные из памяти в произвольном порядке?
Если под локальными переменными подразумевается восстановление сохраненных регистров внутри вызванной функции, то неправильный порядок восстановления приведет к банальной смене местами этих переменных, из-за чего функция, которая вызвала эту функцию, может "повесить" всю программу.
Действий со стеком и регистрами, которые могут запустить подобный сценарий - очень много и у каждого свои нюансы, и если пытаться всё это дело разобрать, то ответ разрастется на несколько постов. Так что думаю, что этого хватит.
> Почему динамическую память называют памятью "на куче"?
Так принято. "Куча" происходит от имен функций HeapCreate/HeapAlloc/HeapFree, которые отвечают за инициализацию, выделение и освобождение памяти в оперативной памяти. Само по себе слово "куча" подразумевает кучку памяти, которую можно использовать в своих нуждах.
> Что из себя представляет эта "куча"?
Динамически выделенное место в оперативной памяти, которое ты можешь использовать для реализации классов, элементов массива, строк... чего угодно, в общем. Если ты пишешь на ассемблере и тебе нужно что-то больше стека, то можно воспользоваться кучей. Впрочем, если на любом высшем языке пишешь, то тоже можно воспользоваться кучей, если ситуация поджимает. В том же delphi процесс работы с динамической памятью автоматизирован, если ты работаешь с массивами и нативными строками, так что там вообще можно не задумываться ни о каких кучах - компилятор всё делает за тебя.
https://en.wikipedia.org/wiki/Computer_science
3 Areas of computer science
3.1 Theoretical computer science
3.1.1 Theory of computation
3.1.2 Information and coding theory
3.1.3 Algorithms and data structures
3.1.4 Programming language theory
3.1.5 Formal methods
3.2 Applied computer science
3.2.1 Artificial intelligence
3.2.2 Computer architecture and engineering
3.2.3 Computer performance analysis
3.2.4 Computer graphics and visualization
3.2.5 Computer security and cryptography
3.2.6 Computational science
3.2.7 Computer networks
3.2.8 Concurrent, parallel and distributed systems
3.2.9 Databases
3.2.10 Software engineering
Такие дела. А русская версия этой статьи называется как раз информатика. Странное оно не у меня, просто видимо каждый подразумевает что-то своё. Народ, угоревший по датамайнингу и предсказаниям, подразумевает именно это, плюс смежные области. А одна тян просто стала ворчать, что это umbrella term, и реально хрен поймёшь, ты "ещё в cs" или "уже в cs", или чем вообще занимаешься.
> Нет, не из-за этого.
Я не совсем правильно изъяснился — не переполнения буфера, а именно переполнения буфера вместе с внедрением вредоносного кода.
>тян просто стала ворчать, что это umbrella term, и реально хрен поймёшь, ты "ещё в cs" или "уже в cs"
Ну так оно по сути и есть. Не знаю, лично я (и все мои знакомые, блоггеры, которых я читаю, ну и вообще все вот это) понимают под CS ту штуку, которая между логикой и дизайном языков программирования - то есть theoretical computer science по вот этому списку. Но с другой стороны - Concurrent, parallel and distributed systems в theoretical CS тоже изучаются, просто с другой стороны. Вообще, часто говорят о двух традициях в CS - одна от тех, кто любит считать, а другая от тех, кто любит абстракции. Вот я бы первую как раз и называл информатикой, а вторую - комплюктер сцайенс.
Но вообще да, ты прав - со "странное у тебя" я погорячился; извини, если что. С другой стороны, трудно не запутаться, когда словами Computer Science называется нечто, что не является наукой и не про компьютеры.
Переполнение буфера - проблема системы типов, а не стека.
Да вот я тоже запутался. Первым импульсом было явиться на кафедру и заорать, что мы тут фигнёй маемся, а вот за бугром - настоящий компсцаенс. А теперь начинаю догадываться, что забугорные исключают из компсцаенса всё то, в чём не шарят, ещё и стремятся полить более низкоуровневое ковыряние гуаном: мол, это ремесло для колледжей.
>Первым импульсом было явиться на кафедру и заорать, что мы тут фигнёй маемся
Ну, вообще-то это абсолютно правильный импульс был.
> исключают из компсцаенса всё то, в чём не шарят
Почему? Все ж правильно. Есть физика, а есть инженерия. Есть теория типов, а есть датамайнинг. Все правильно. Путаница в названиях, но не в содержании.
Да, в названиях. Но она повсеместна, видимо, эта путаница.
>Ну, вообще-то это абсолютно правильный импульс был.
Не в такой форме. С людьми надо чётко разговаривать, когда уже сам расшарил тему. А не в лихорадке бросаться словами, смысл которых ещё не успел даже по вики пробить, лол.
Думаю, я просто напишу саммари тех тем, которым конференция была посвящена. Кину на столы, пусть сами разбираются, интересно им или нет. Всё равно кафедра ближе к этому треду по направленности, чем к конференции.
> А не в лихорадке бросаться словами, смысл которых ещё не успел даже по вики пробить, лол.
Ну, тут остается только согласиться, ага.
Так это, ты её, ну, кафедру, на LtU подсади. Прям всех. Пусть там, значит, комментируют - глядишь соревновательный дух побудит к разработке и тех областей, которые на конференциях котируются.
>LtU
Шта?
http://lambda-the-ultimate.org/
Ну это как двач для битардов, только лту для комплюктер сцайентистов.
Спасибо, только они у меня не могут в английский тотально все. Буду залипать в одиночку. И то хорошо.
>Регистры изобрел, ну охуеть.
>Очередь вместо стека.
При чём тут регистры и очередь? Ты меня совсем не понял. Моя модель вообще не подразумевала LIFO/FIFO обращения к переменным. Можно было бы удалить из структуры переменную лежащую где-то в середине например. А прямой связи с регистрами не вижу - регистр это не вектор, при очистке одного из регистров все остальные не сдвигаются.
> При чём тут регистры и очередь?
Очередь (и ссылка на описание этой модели) - это я откликнулся на твое предложение предлагать альтернативные стеку модели для хранения контролфлоу и переменных.
> Ты меня совсем не понял.
Да, ты прав. Я каким-то образом умудрился прочитать "сортированный по ключу вектор" как "ассоциативный массив". Бывает. :]
Но я все равно не понял, что ты имел в виду. Раз у тебя можно удалить один элемент со сдвигом остальных, то это двусвязный список, то есть куча. В чем тогда смысл?
>Раз у тебя можно удалить один элемент со сдвигом остальных, то это двусвязный список, то есть куча.
Правильно, примерно так и получается. Только куча всё равно не заменяет стек, т.к. локальные переменные блока кода(в т.ч. указатели на кучу) ты хранишь на стеке. Я же предложил структуру хранения локальных переменных, не привязанную к стеку.
>В чем тогда смысл?
Теоретизирование. Ответ на вопросы: "Что было бы если?", "Почему стек?"
А регистры, как ты заметил, по сути и являются моделью типа "ассоциативный массив", только в отличии от обычной структуры данных, они выделяются и "управляются" на этапе компиляции. Этим компиляторы отчасти и занимаются - решают как распихать по регистрам стек вызовов и локальные переменные.
Действительно ли от польской ноттации весомый профит?
>Ответ на вопросы: "Что было бы если?", "Почему стек?"
Так я у тебя об этом и спрашиваю: в чем смысл такой модели, какие профиты, почему, что было бы если. А ты мне отвечаешь: "почему, что было бы если". Трындец же!
Aye-aye, Captain!
Нет.
Поясните за процессоры на forth
Их нет.
на бумаге говно, а вот при ограниченных возможностях ввода - отличненько просто
их есть
130 ядер, микрропороц какотой, забыл как называется
а ты бы мог и написать название
Вот и расскажи об обграниченных возможностях ввода.
на отличненько просто
В интерпретаторах - действительно от неё профит(структура данных проще и удобнее). Конвертировать в неё из инфиксной всегда можно.
>почему локальные переменные во всех(или почти всех) известных языках хранятся на стеке?
Потому что стек - это готовый сразу доступный буффер, в котором можно использовать немного памяти для своих нужд, и при этом она всегда занята компактно. Иначе нужно просить систему выделить какое-то количество памяти, хорошо если известно сколько нужно заранее, в противном случае - с запасом, потом просить систему освободить её при выходе из блока, в результате динамическая память получится фрагментированной и малопригодной к использованию. Впрочем, к этому таки приходится прибегать, если для данных нужно использовать значительные объёмы.
>Почему нельзя "удалять" локальные переменные из памяти в произвольном порядке?
Ну почему же нельзя? Можно. Лол. Всего-то нужно покопировать немного памяти для соблюдения компактности стековой структуры.
>Как это связано со структурой кода(независимо от языка)?
В общем случае никак. Но в реальности при вызове подпрограмм часто удобно хранить в стеке точку возврата и просто чтобы обходиться без описанной выше возни с динамической памятью.
>Почему динамическую память называют памятью "на куче"?
Если бы я писал менеджер памяти - я бы может быть использовал структуру данных макс хип для менеджмента свободных участков. Лень искать так ли это всегда или лишь в некоторых имплементациях, от которых и повелось так называть динамическую память.
>Что из себя представляет эта "куча"?
В смысле "динамическая память"? Некоторой аналогией можно считать совокупность земельных участков города - некоторые заняты дорогами, некоторые - зданиями, некоторые свободны.
В целом правильно. Дополню и поправлю:
>Потому что стек
быстрее других реализаций ко всему прочему.
>Ну почему же нельзя?
Стек - это принцип LIFO же, pop-push. Нельзя вытащить переменную из середины - придётся нарушать/дополнять функциональность стека.
>В общем случае никак.
Как. Стек напрямую связан со скобочными структурами в ПЯВУ, например - с блоками кода. LIFO-принцип в коде. Скобочные структуры парсятся с помощью структуры данных стек и эта связь не случайна.
В остальном вроде всё верно.
>быстрее других реализаций ко всему прочему.
Если нужно добыть значение из глубины стека не потеряв остальные значения, то вся его "быстрота" ничем не поможет.
>Нельзя вытащить переменную из середины - придётся нарушать/дополнять функциональность стека.
Дополнять функциональность стека - дело хорошее и нужное, если его немножко облагородить (как, например, стек регистров FPU x87), то получается замечательная штука.
>>В общем случае никак.
>Как.
Нет, в общем случае никак, на то он и общий случай, та же лента в машине Тьюринга - это не стек.
Это спор ни о чём. Мир не вертится вокруг стека, и стек удобен лишь в ограниченном спектре задач.
Можно на обычных процессорах так сделать. У gcc у крестов есть параметр компиляции для отдельного хранения адресов возврата и данных на стэке. Во факту адресы возврата будут не в стэке, а в специальном пуле на куче.
>Если нужно добыть значение из глубины стека не потеряв остальные значения, то вся его "быстрота" ничем не поможет.
Обращаться к переменной в данной точке кода мы можем по адресу относительно верхушки стека, для этого push-pop не нужны. Т.к. гарантированно она есть в данной точке(pop её ещё не был сделан) и адрес её относительно верхушки стека фиксирован - в этом собственно и скорость работы.
>Нет, в общем случае никак, на то он и общий случай
Я имел в виду практические реализации ПЯВУ, а не теоретические модели.
>адрес её относительно верхушки стека фиксирован
А если на стеке лежат переменные разного размера?
Поясните, насколько погромистам нужна математика в работе. Нужно ли дрочить матан в институте и если да, то в каких областях он нужен?
Компьютерная графика - это линейная алгебра, например.
Можно примеров? Как в компьютерной графике используются знания из курса линала? Ты только про векторную или про растровую тоже?
Поворот картинки матричным преобразованием вычисляется. Мимошёл.
Изображение выводится в пикселях. Монитор - это матрица из пикселей. Любое изменение картинки на мониторе это преобразование матрицы
Это неважно т.к. размеры переменных известны в compile-time, эта инфа позволяет однозначно вычислить адрес любой переменной в compile-time.
Смотря каким погромистам. Пильщикам сайтов не нужна, а вот где что-то более-менее интересное - уже нужна. Матан дрочить не надо, т.к. в институтах обычно надрачивают тупые задачи для мат. пакетов(интегральчики, уравнения - картофан). Надо получать понимание математических теорий, понятий, концепций, основных и универсальных методов, подходов решения задач. Математика нужна много где - в искуственном интеллекте, включая распознавание образов(в т.ч. нейросетях), экспертные системы; в разработке игр, обработке изображений/звука/видео/3D, шифровании, в алгоритмах сжатия информации, в моделировании процессов реального мира - всего не перечесть.
Матрицы используются в векторной графике - для поворотов, перемещений(читай афинные преобразования), проекций и различных деформаций. Свет, тени, отражения - опять же векторы(падения света, отражения) + матрицы, различные способы вычисления освещенности точки.
Растровая графика - используются уравнения для вычисления цвета пикселя по определенному закону(градиент, сложные заливки) в т.ч. можно использовать диф. уры - различные световые эффекты, прорисовка взрывов, огня(и в векторе и в графике).
Физические движки игр - всё на матане и физике. Правда, чтобы пользоваться движком это всё знать необязательно, т.к. движок это всё реализует и инкапсулирует. Нужно уметь оперировать базовыми понятиями из физики(абсолютно твёрдое тело, сила, импульс, степени свободы к примеру) и осознавать что ты делаешь.
Ещё скажи, что кодстайл соблюдать не надо, ибо ТОТАЛИТАРНО
> скомпилился в машинный код на стороне сервера(возможно через хранимые процедуры это и сделано)
В Oracle DB PL/SQL код так и обрабатывается, кстати.
Бумп.
С чего начать изучение?
Зависит от целей. Можно навернуть структур данных и алгоритмов, мат. логику, а также прочую дискретную математику.
Почему после этих компьютерных наук в голове образуется такая пустота и неудобство?
Монитор облучает голову, мозг разрушается.
Есть версия, что пустота была и до, а теперь ты просто лучше стал её ощущать, и тебе не удобно.
Но ведь у меня целых три кактуса рядом с компутером.
Это деградация?
Можете обьяснить принципы туманных вычислений (fog computing)? Интересует, например, распределение ресурсов в таких сетях. Похоже ли распределение ресурсов в таких сетях на "От каждого по возможностям, каждому по потребностям"?
Бамп
Бамп
Компуктерсаинтач, помогите найти инвариант. Второй день думаю, а время поджимает. На ум приходит только (i>=0)and(r>=-1). Достаточно ли она сильная?
И о чём же ты второй день думаешь?
Впервые об этой вашей логике Хоара вообще слышу, и тем не менее вот тебе инвариант {(i*i=n ^ r>=0) V r<0}, из которого и условия цикла тривиальным образом следует конечное утверждение.
Благодарю, в итоге к такому же решению и пришел.
А с помощью этой логики нас просят доказывать корректность программы/системы в целом. Сир Тони Хоар поджал под себя эту идейку, изначально она Флойду принадлежала.
Грубо говоря, это оверхед порядка O(mnl), где m - количество строк, n - количество видимых переменных, l - количество условий(пропорционально m). Даже с исключительно чистыми функциями это O(m^2). А тестировать всё равно надо, потому что от ошибок в доказательстве никто не застрахован.
Я бы не смог кроме O(m) времени и сил на полезную деятельность ещё тратить O(m^2) на трудоёмкую иллюзорно полезную хуйню.
Но каждому, конечно, своё.
Как вкатиться в теории типов и всю хуйню, не начиная с лоу-левела типа двочиное исчисление, основы матлогики и вся школьная хуйня? А то скучно.
1 АРХИТЕКТУРА ФОН-НЕЙМАНА
2 ТИПОВЫЕ АЛГОРИТМЫ
ВСЕ ОСТАЛЬНОЕ НЕ СВЯЗАННОЕ С КОНКРЕТНЫМИ МАШТНАМИ И ПРОГРАМНЫМИ ПРОДУКТАМАМИ-ВРЕДНАЯ ХУЙНЯ ПРИДУМАННАЯ ДЛЯ ПАРАЗИТИРОВАНИИ В НАУЧНОЙ СРЕДЕ.
2 ТИПОВЫЕ АЛГОРИТМЫ
ВСЕ ОСТАЛЬНОЕ НЕ СВЯЗАННОЕ С КОНКРЕТНЫМИ МАШТНАМИ И ПРОГРАМНЫМИ ПРОДУКТАМАМИ-ВРЕДНАЯ ХУЙНЯ ПРИДУМАННАЯ ДЛЯ ПАРАЗИТИРОВАНИИ В НАУЧНОЙ СРЕДЕ.
>Подразумевает, что 98% исследований в научной среде - не паразитирование
Наивно.
ВЗЯТЬ НАПРИМЕР РЕЛЯЦИОННЫЕ БАЗЫ ДАННЫХ. ТЕ ПРОГРАММИСТЫ КТО ДРОЧАТ НА ТЕОРИЮ ПИШУТ НЕПРИГОДНЫЕ ПРОГРАММЫ. ЧТОБЫ ПИСАТЬ ГОДНЫЕ ПРОГРАММЫИНАДО ДРАЧИТЬ НЕ НА ЕТУ ХУЕТУ А НА АЛГОРИТМЫ ПОИСКА ПО ИНДЕКСАМ И ПОДДЕРДАНИЧ ИНДЕКСОВ. НА ЕТОМ ГАВНИЩЕ УЖЕ РАПТЛИЛИ ОГРОМНЫЕ БАБКИ И НЕ ДУМАЮТ ОСТАНАВЛИВАТСЯ. XBASEЛЕИАЛА НА 286 ПРОЦЕССОРАХ А ЕСКУЕЛЬ ТОРМАЗИТ НА СОВРЕМЕННЫХ 8И ЯДЕРНЫХ
НАЕБОН БУДЕ ПРОДОЛЖАТСЯТПОКА ЕЛИТА НЕ НАУЧИТСЯ ПРОГРАММИРОВАТЬ ЛИБО ЛИШИТСЯ СТАТУСА
НАЕБОН БУДЕ ПРОДОЛЖАТСЯТПОКА ЕЛИТА НЕ НАУЧИТСЯ ПРОГРАММИРОВАТЬ ЛИБО ЛИШИТСЯ СТАТУСА
Хочу сказать, что во многом также мешают лишние абстракции ОС. К примеру, база данных могла бы почти напрямую работать с диском без абстракций. Ядро лишь бы мультиплексировало ресурсы.
Интересно пишешь. Почти, как пр0теин-инсайдер. Где почитать больше?
В чем профит ленивых вычислений? Какие вычисления стоит сделать ленивыми?
В ДАННОМ СЛУЧАЕ СКОРОСТЬ СНИЖАЕТСЯ ЕА НЕКОТОРЫЙ НЕБОЛЬШОЙ КОЭФЫИЦЕНТ А НЕ В МИЛИЕЫ И БОЛЕЕ РА КАК В СЛУЧАЕ СКУЛ ЗАПРОСА НАПИСАННОГО БЕЗ УЧЕТА ТОГО КАК ОН БУДЕР РЕАЛЬНО ВЫПОЛНЯТСЯ
Бумп.
Никак.
угу
видеокурса
дарк соулз?
Перекатимся?
А тем временем, у меня тема для обсуждения. Я заметил, что любой достаточно сложный алгоритм, в особенности всякие генетический, вероятностный, является устойчивым к изменениям. Можно поменять какой-либо параметр или даже подалгоритм и результат не будет отличаться в пределах эпсилон! Можно этому явлению дать название "алгоритмическая устойчивость", дать четкое определение и вывести необходимые и достаточные условия.
А тем временем, у меня тема для обсуждения. Я заметил, что любой достаточно сложный алгоритм, в особенности всякие генетический, вероятностный, является устойчивым к изменениям. Можно поменять какой-либо параметр или даже подалгоритм и результат не будет отличаться в пределах эпсилон! Можно этому явлению дать название "алгоритмическая устойчивость", дать четкое определение и вывести необходимые и достаточные условия.
Ничего, что для такие алгоритмы катятся к ближайшему минимуму оценочной функции и для них есть отдельные алгоритмы по подбору "более оптимальных" начальных параметров? Если ты не изменишь цель, к которой стремишься, то почему должен измениться результат?
Все очень просто. Открываешь видеолекции по сикп от мит, самое начало, и наблюдаешь как лектор зачераивает сперва слово компьютер а затем слово саенс. Вот тебе и ттвет
Нет и не будет никогда прикладных наук. Есть только приложения наук
Народ, в следующем году мне исполняется 26 лет, в следующем же году я собираюсь поступать в ВУЗ с целью заняться "computer science". Подскажите, станет ли помехой мой возраст, если я захочу посвятить себя научной деятельности?
Почему сейчас все компьютеры построены на основе двоичной системы счисления, кроме того что так экономически более выгодно, ведь есть и более производительные варианты, например
на основе системы счисления остаточных классов (СОК),
в своё время с её помощью была построена одна из самых производительных для своего времени ЭВМ К-340А, которая производила вычисления для радиолокационной станции Дуга.
на основе системы счисления остаточных классов (СОК),
в своё время с её помощью была построена одна из самых производительных для своего времени ЭВМ К-340А, которая производила вычисления для радиолокационной станции Дуга.
Как можно дёшево получить образование в сша? Как есть годные университеты с cs и однолетней программой обучения?
Если это утверждение верно, то русалки существуют.
Но ведь существование русалок было доказано Карлом Банзе еще в 1990 году.
Технически наиболее просто, а потому надежно. Выпускались и троичные компьютеры ("Сетунь" - самый известный), при увеличении быстродействия на арифметических операциях одновременно возрастают и помехи.
СОК - непозиционная система счисления, в отличии от позиционной двоичной.
Транзистор может быть включен, и выключен (TRUE/FALSE),
а значит на входах и выходах логических элементов только два значения может быть.
Но ИМХО, основная проблема - именно в сложности конвертации
из позиционной в непозиционную и наоборот:
https://ru.wikipedia.org/wiki/Система_остаточных_классов#.D0.9D.D0.B5.D0.B4.D0.BE.D1.81.D1.82.D0.B0.D1.82.D0.BA.D0.B8_.D1.81.D0.B8.D1.81.D1.82.D0.B5.D0.BC.D1.8B_.D0.BE.D1.81.D1.82.D0.B0.D1.82.D0.BE.D1.87.D0.BD.D1.8B.D1.85_.D0.BA.D0.BB.D0.B0.D1.81.D1.81.D0.BE.D0.B2
Ёбанные пидарасы, что же за хуйню вы тут написали насчёт стека и локальных переменных.
Локальные переменные используют ОБЛАСТЬ ПАМЯТИ стека процессора и доступ у ним ПРОИЗВОЛЬНЫЙ, а не LIFO. (Это по крайне мере верно для Интелловских процессоров)
Локальные переменные названы так потому что после выхода из подпрограммы доступ к ним теряется.
https://en.wikipedia.org/wiki/Function_prologue
http://mohit.io/blog/assembly-and-the-art-of-debugging/
Так что сперва изучите Ассемблер, а потом пытайтесь заниматься своей недонаукой
>почему локальные переменные во всех(или почти всех) известных языках хранятся на стеке?
Удобнее удолять как считают примитивные компутерные саентисты?
1. Нахуй ты учишь необучаемых?
2. Надо изучать не ассемблер бля (потому что языков ассемблера дохуя), а архитектуру, потому что простого знания какого-нибудь masm'a, по мануалам iczellion'a нихуя особо им не даст, ну или по мануалам из пакетов ассемблеров. В.Юров тот еще пидор, написал самую беспонтовую книгу, в плане того, что блядь я раз 500 засыпал, пока учил все, но в итоге все читал.
А так, я вообще угараю с даунов, которые называют еблю с компами компьютерной наукой. Сидишь себе, дрочишь на компы, а тут оказывается, что это наука, ну охуеть теперь
>Нахуй ты учишь необучаемых
>Надо изучать не ассемблер
>а архитектуру
Нет, анон, надо изучать не архитектуру, а систему команд процессора/контроллера.
Ведь именно в эти комманды ассемблером транслируются исполняемые и объектные модули, связываемые линкером.
>masm
Есть ещё там nasm и TASM.
>оказывается, что это наука
Информатика, же. Там ещё и кибернетика недалеко.
Нахуя ему именно команды? Он командами будет знать как память устроена? Да и языков ассемблера хуева куча, просто как говна, в т.ч. fasm, yasm, gas, и т.д.
>Информатика
Ну вот колупаешь ты проги целыми днями. Какая это нахуй наука? Даже Крис Касперски водил по губам долбоебам, которые пытаются "по науке" упаковать экзешник.
>Ну вот колупаешь ты проги целыми днями.
>Какая это нахуй наука?
>не надобно "по науке" упаковать экзешник.
Знаешь, мне эти линкеры напомнили дефрагментацию и упаковку инструкций в непрерывные последовательности.
Поэтому нашёл вот: http://pastebin.com/uygtshiB
Преимуществ у двоичных компов перед троичными нет.
Сетунь закрыли, чтобы можно было невозбранно пиздить ПО у пиндосов.
Чем вообще аноны ИТТ занимаются? Срутся по поводу неточностей в шапке и формулировках оппонентов или что-то изобретают?
мимо
мимо
>Срутся [...] или что-то изобретают?
Всё уже обосрали обсудили. Ты тред пробовал читать?
Пробовал. Пара платиновых вопросов уровня "что почитать, зачем нужны матрицы, нужна ли погромисту математика" и обсуждениели? про стеки, железо и архитектуру на остальные 450 постов. Просто понять не могу, чем этот тред вообще должен быть и не продуктивней будет в программаче продолжать сидеть.
Можно теоретически постоянно использовать стек вместо кучи и будет ли где это плохо/хорошо?
Тред имеет право на жизнь, потому что Computer Science имеет отношение к саентачу. Да, возможно в программаче будет продуктивнее - зависит от критерия продуктивности.
Вопрос по бессмысленности подходит для собеседований - чтобы ввергать в ступор голодных студентов. Можно, но очень заёбисто, например фп тебе в помощь.
И даже деревья можно на стеке хранить? Вообще все структуры данных и всё-всё-всё? А фп тут вряд-ли поможет как-то, разве что комбинаторная логика и там композиция.
>И даже деревья можно на стеке хранить?
Да.
> Вообще все структуры данных
Да.
> и всё-всё-всё?
В принципе - да. Даже небо, даже Аллаха.
Например, хранишь компактно в стеке, глубоко копируешь свою произвольную структуру данных при записи, и дальше используешь её вместо старой, при этом используешь только функции без побочных эффектов, ссылки считаешь или избегаешь. Для фп подобные пляски (чистота) являются естественными, а в особо запущеных случаях - и единственно допустимыми.
Допустим есть конечное множество M, все элементы которого - натуральные числа. Есть известное число N. Нужно выбрать m - подмножество M таким образом, чтобы
1) для любых i, j из m: |i-j| >= N
2) размер m максимален
Есть какие-нибудь быстрые решения без перебора всех вариантов?
1) для любых i, j из m: |i-j| >= N
2) размер m максимален
Есть какие-нибудь быстрые решения без перебора всех вариантов?
Напрашивается динамическое программирование. Ты не стесняйся, тащи на двачи всю свою домашку.
Это не домашка, это мне для своего хобби-прожекта.
Поясните, пожалуйста, за клэйтронику (программирование нанороботов) и используемые там алгоритмы.
Что такое замыкание? Как оно связанно с рекурсией?
Держи друг, тут различные статьи на эту тему
http://www.cs.cmu.edu/~seth/papers/goldstein-robosphere04.html
>Что такое замыкание?
За тебя что, погуглить википедию? Прочитай хотя бы её, если будет не понятно - спрашивай конкретнее.
>Как оно связанно с рекурсией?
Как блесна связана с водопроводом? Как метеорит связан с земледелием? Как червячная передача связана с социологией?
Ответы на эти и другие занимательные вопросы в нашей постоянной рубрике "очень косвенно, блджад".
Поссал на итт даунов. Даже в CS литературе объясняют что 0 это не натуральное число.
ну ты рофлишь что ль? это обычный псведокод. тут "словами" описывают алгоритм, нужен минимальный словарный запас английского, чтобы понимать это. другое дело - поймёшь ли ты сам алгоритм
АВТОМАТИЗИРОВАТЬ МОЖНО ТОЛЬКО ПОВТОРЯЮЩИЕСЯ ПРОЦЕССЫ
Ты бы и собаку автоматизировал.
Да, это повторяющийся процесс. Котиков не стал бы, они какие-то нех.
Еще, вспомни 60е. Роботов-сабачек, ага. лол
> Ты бы и собаку автоматизировал.
> Да, это повторяющийся процесс.
Мааам, у нас тут комютерссайнс
А я пришел спросить, как местные относятся к competitive programming?
Норм, спорт как спорт, забавно, если с знакомыми участвуешь, например.
У меня неожиданно возник странный вопрос, который и задать больше некуда. Вот есть куча в памяти процесса, она так названа почему ? Потому что по своей сути представляет одноимённую древообразную структуру данных. А другие подходы к организации кучи были ? Например просто таблицу свободой и выделенной памяти поддерживать. Я попробовал погуглить alternatives for process memory heap, находит альтернативы вообще для всей концепции stack-heap-static memory.
Это не "классической" математики тред.
Это не тред того, что проходится в школах/университетах под названием "информатика".
Это не тред программирования в обычном смысле и того, как написать программу, делающую X на L, вопросов вроде "Какие подводные камни технологии/языка T".
CSTCS - CSTCS iS Thread about Computer Science.
Сразу же подброшу годноты, являющейся классикой CS.
https://ru.wikipedia.org/wiki/Проблема_обедающих_философов
https://ru.wikipedia.org/wiki/Стек
https://ru.wikipedia.org/wiki/Обратная_польская_запись
Вопрос ньюфагам на понимание - почему локальные переменные во всех(или почти всех) известных языках хранятся на стеке? Почему нельзя "удалять" локальные переменные из памяти в произвольном порядке? Как это связано со структурой кода(независимо от языка)?
Почему динамическую память называют памятью "на куче"? Что из себя представляет эта "куча"?
Думаю, хватит для начала.