Вы в курсе, что есть ДВЕ РАЗНЫХ школы вероятности?
Школы вероятности? Вы имеете в виду два философский учения. В теории вероятностей, если уж вероятностное пространство зафиксировано, то вероятности событий определяются однозначно.
И говорите про себя: я им явно не понравился, с большой вероятностью там отказ.
Вот этого я как раз не понимаю. Ребёнок, которого спрашивают, уже родился, т.е., один из двух вариантов уже реализован. Вероятность выпадения орла или решки уже подброшенной и изученной монетки может быть только 1 и 0, никак не 1/2.
Всё верно, задача поставлена некорректно — никакой случайности там нет.
Про SSA и SIA интересно, конечно, но это философия. И стоило об этом, ИМХО, сразу написать — всё же это блог «Математика» )) А с точки зрения математики в задачах с вопросом «чему равна вероятность» либо только один ответ, либо задача поставлена некорректно. В данном же случае у читателя могло возникнуть впечатление, что это парадоксы вроде парадокса Монти Холла, где правильный ответ противоречит интуиции. Но на самом деле просто задача просто поставлена некорректно. И есть две философские школы, которые рассказывают о том, как это правильно трактовать (т.е. чему соответствует эта некорректная формулировка). Но, к сожалению, в тексте статьи это не объясняется и не разбирается…
Мне кажется, что полезно понять, почему, например, первая задача некорректна.
Жил был моряк. У него было две любимых женщины в разных портах, и он хотел детей – вот только не решил, одного или двух. Он решил кинуть монету. Орел – будет один ребенок от одной из женщин (к которой первой зайдет в порт по работе – это уж как получится), решка – сделает по ребенку каждой женщине. Неизвестно, как выпала монета, и как его бросала судьба по миру, но вы – его ребенок. Какова вероятность, что вы – его единственный ребенок?
Некорректность задачи заключается в том, что когда сын пытается оценить вероятность того, что он единственный, никакой случайности в задаче нет. Нет никакого случайного процесса, а есть только неизвестный сыну результат подбрасывания монетки, но этот результат уже зафиксирован. Поэтому вопрос в задаче не имеет смысла. Это как спрашивать, с какой вероятностью какое-то конкретное число простое. Если число фиксировано, то оно или простое или нет.
А далее в тексте идёт рассуждение, что правильно интерпретировать эту постановку примерно так. Предположим, что вы — путешественник по параллельным мирам. И вы случайно становитесь сыном моряка в одном из двух миров, в которых у отца выпали орёл и решка соответственно. И нужно оценить вероятность того, что вы попадёте в мир, где сын является единственным. И весь вопрос в том, что означает «случайно становитесь сыном моряка», нужно ли считать, что все миры равновероятны (есть только два мира), или что все сыновья равновероятны (есть три сына). В первом случае ответ будет 1/2, во-втором 1/3.
Резюме: с точки зрения математики задача некорректна, т.к. поставленный вопрос не имеет смысла, т.е. никакого парадокса нет.
Чтобы попасть к нам в магистратуру человек должен неплохо учиться в бакалавриате, да.
Можно ли считать, что после бакалавриата человеку нет смысла учиться?
Если ставить перед собой целью зарабатывать «тысяч, ну может, 100-150», то не нужно — чтобы найти подходящую вакансию в каком-нибудь «бодишопе» хватит и двух-трёх курсов в приличном бакалавриате.
Если же ставить перед более амбициозные, то есть смысл ещё поучиться, приобрести знания и опыт, и уже с ними выходить на рынок трудоустройства.
1. Это условные названия направлений, по которым в нашей магистратуре читаются курсы. Курсы по направлению «промышленная разработка ПО» — это набор курсов о разработке программных продуктов. Слово «промышленная» означает, что цель разработки — это создание программных продуктов, а не, например, исследования или развлечение. Т.е. студент, который это направление выбирает, видит разработку ПО основным видом своей деятельности в будущем.
2. Слово «алгоритмы» там действительно лишнее — попало туда случайно. Убрал, спасибо, что заметили. Если вы не хотите заниматься теоретическими исследованиями в области теории языков, то вас никто заставлять не будет =).
3. Если после курсов направления «теории языков программирования» вы не будете уметь спроектировать ЯП (синтаксис, семантику, систему типов) и реализовать для него компилятор, то у вас будут большие проблемы с закрытием сессии =). Аналогично, если после курсов направления «промышленная разработка ПО» вы не сможете заниматься разработкой ПО. Ссылка на хедхантер по запросу «опыт промышленной разработки»
На edu.ifmo.ru/specs_list нужно выбрать «01.04.02 Прикладная математика и информатика», и далее в списке «Разработка программного обеспечения / Software Engineering»
Так ведь такой алгоритм уже построен! Для алгоритма Левина верна следующая теорема. Теорема:
Если P=NP, то существует такой полином p, что алгоритм Левина решает SAT за время p(n).
Вот это я не очень понимаю. Любое доказательство P=NP будет означать, что оптимальный алгоритм для NP-полных задач (алгоритм Левина) является полиномиальным. Т.е. даже «неконструктивное» доказательство P=NP, позволяет получить явный полиномиальный алгоритм для NP-полных задач. Никто не будет, конечно, применять алгоритм Левина на практике, но всё же это совершенно конкретный алгоритм.
Да, у этого вопроса есть три возможных решения: P=NP, P!=NP и «недоказуемо». Если ZFC противоречива, то там одновременно могут быть доказательства и P=NP, и P!=NP. Вопрос скорей всего в том, что ZFC по теореме Гёделя неполна, т.е. есть недоказуемые в ней [верные] утверждения.
Тогда мы возвращаемся к исходному вопросу: что значит, что архиватор «оптимальный»? =) Думаю, что я понял, что вы хотите сделать, но мне кажется, что не очень корректно говорить об «оптимальном архиваторе» в данных терминах, т.к. нам приходится одновременно накладывать ограничения и на память и на время.
Возьмём задачу X из PSPACE и сведём её в задаче «проверить, что программа со входом А и памятью B завершается выходом С»: программа — программа для решения X, A — вход для X, B — ограничение на память для X, а выходы нужно перебрать (для этого нужно дополнительное место, но оно длины |C|). Таким образом мы за полиномиальную память сведём любую PSPACE задачу к этой.
если всего состояний 2^|A|, а PSPACE требует 2^(|A|^p)
Это утверждение я не понял. Что значит «требует»?
Мне кажется, что вы запутались в иерархии классов. Из того, что P=NP, не следует, что любой экспоненциальный алгоритм имеет полиномальный аналог. Из P=NP не следует P=E (или EXP). Более того, P!=E, это безусловный результат, «иерархия по времени». Из того, что P=NP, следует только коллапс полиномиальной иерархии. То есть полиномиальные алгоримты появятся у тех задач, которые можно записать с константным количеством кванторов «существует» и «для любого».
Вы не ответили на вопрос, как будет устроена проверка того, что программа со входом A и ограничением на память B завершается с выходом C? Насколько я понимаю, эта задача полна для PSPACE. Из P = NP не следует, что P = PSPACE.
Вход — сжатые данные (начальное состояние программы) — выход разжатый размер.
Это архиватор? На выходе «разжатые данные» или их размер?
Куда делись «алгоритм+память»? Вы пишете, что «начальное состояние» это и «сжатые данные» и сертификат. Не понимаю, что имеется в виду. Можете описать задачу математически? Может быть тогда все вопросы отпадут.
Школы вероятности? Вы имеете в виду два философский учения. В теории вероятностей, если уж вероятностное пространство зафиксировано, то вероятности событий определяются однозначно.
Это не математика, а фигура речи. Не путайте.
Всё верно, задача поставлена некорректно — никакой случайности там нет.
Мне кажется, что полезно понять, почему, например, первая задача некорректна.
Некорректность задачи заключается в том, что когда сын пытается оценить вероятность того, что он единственный, никакой случайности в задаче нет. Нет никакого случайного процесса, а есть только неизвестный сыну результат подбрасывания монетки, но этот результат уже зафиксирован. Поэтому вопрос в задаче не имеет смысла. Это как спрашивать, с какой вероятностью какое-то конкретное число простое. Если число фиксировано, то оно или простое или нет.
А далее в тексте идёт рассуждение, что правильно интерпретировать эту постановку примерно так. Предположим, что вы — путешественник по параллельным мирам. И вы случайно становитесь сыном моряка в одном из двух миров, в которых у отца выпали орёл и решка соответственно. И нужно оценить вероятность того, что вы попадёте в мир, где сын является единственным. И весь вопрос в том, что означает «случайно становитесь сыном моряка», нужно ли считать, что все миры равновероятны (есть только два мира), или что все сыновья равновероятны (есть три сына). В первом случае ответ будет 1/2, во-втором 1/3.
Резюме: с точки зрения математики задача некорректна, т.к. поставленный вопрос не имеет смысла, т.е. никакого парадокса нет.
Можно ли считать, что после бакалавриата человеку нет смысла учиться?
Если ставить перед собой целью зарабатывать «тысяч, ну может, 100-150», то не нужно — чтобы найти подходящую вакансию в каком-нибудь «бодишопе» хватит и двух-трёх курсов в приличном бакалавриате.
Если же ставить перед более амбициозные, то есть смысл ещё поучиться, приобрести знания и опыт, и уже с ними выходить на рынок трудоустройства.
2. Слово «алгоритмы» там действительно лишнее — попало туда случайно. Убрал, спасибо, что заметили. Если вы не хотите заниматься теоретическими исследованиями в области теории языков, то вас никто заставлять не будет =).
3. Если после курсов направления «теории языков программирования» вы не будете уметь спроектировать ЯП (синтаксис, семантику, систему типов) и реализовать для него компилятор, то у вас будут большие проблемы с закрытием сессии =). Аналогично, если после курсов направления «промышленная разработка ПО» вы не сможете заниматься разработкой ПО.
Ссылка на хедхантер по запросу «опыт промышленной разработки»
На edu.ifmo.ru/specs_list нужно выбрать «01.04.02 Прикладная математика и информатика», и далее в списке «Разработка программного обеспечения / Software Engineering»
На сайте compscicenter.ru в разделе поступление: compscicenter.ru/enrollment.
Leonid A. Levin. Universal sequential search problems. Problems of Information Transmission, 9:265–266, 1973.
Так ведь такой алгоритм уже построен! Для алгоритма Левина верна следующая теорема.
Теорема:
Если P=NP, то существует такой полином p, что алгоритм Левина решает SAT за время p(n).
Возьмём задачу X из PSPACE и сведём её в задаче «проверить, что программа со входом А и памятью B завершается выходом С»: программа — программа для решения X, A — вход для X, B — ограничение на память для X, а выходы нужно перебрать (для этого нужно дополнительное место, но оно длины |C|). Таким образом мы за полиномиальную память сведём любую PSPACE задачу к этой.
Это утверждение я не понял. Что значит «требует»?
Мне кажется, что вы запутались в иерархии классов. Из того, что P=NP, не следует, что любой экспоненциальный алгоритм имеет полиномальный аналог. Из P=NP не следует P=E (или EXP). Более того, P!=E, это безусловный результат, «иерархия по времени». Из того, что P=NP, следует только коллапс полиномиальной иерархии. То есть полиномиальные алгоримты появятся у тех задач, которые можно записать с константным количеством кванторов «существует» и «для любого».
Это архиватор? На выходе «разжатые данные» или их размер?
Куда делись «алгоритм+память»? Вы пишете, что «начальное состояние» это и «сжатые данные» и сертификат. Не понимаю, что имеется в виду. Можете описать задачу математически? Может быть тогда все вопросы отпадут.