Вероятность

50 на 50

Либо будут, либо нет.

Смотря что ещё дополнительно известно про содержимое файлов. Одно дело, когда внутри текст в latin1, другое дело, когда набор из /dev/random

А к чему вопрос сабжа-то?

>А к чему вопрос сабжа-то?
Сдана одна и та же "лаба по программированию".
Вот и интересно - какова вероятность совпадения двух исходников.

Проверил бы чексуму и не мучился... Лично я уже на такие грабли однажды больно наступил, теперь размерам не доверяю.

> Смотря что ещё дополнительно известно про содержимое файлов. Одно дело, когда внутри текст в latin1, другое дело, когда набор из /dev/random

Глупости. Какая разница, что там внутри. Есть два подмножества из N членов. Вероятность совпадения определяется одной формулой. Я не помню. То-же самое, если взять два набора цифр от нуля до девяти и подсчитать вероятность того, что они высроены в том-же порядке.

>Проверил бы чексуму и не мучился... Лично я уже на такие грабли однажды больно наступил, теперь размерам не доверяю.

Не, не в этом дело - просто теоретические изыскания.... Как корректно рассчитать вероятность такого события...

А... да рассчитать можно, только лень в три часа ночи думать. И это будет функция от размера.

Какие же вы тупые. :(

p = 0.5^(N*количество-битов-в-байте)

Я так понимаю, что это произведение вероятностей совпадения
i-тых байт соответственно: P{a_i = b_i}.
Поскольку P{a_i = b_i} = P{a_j = b_j}, то вероятность равна
(P{a_i = b_i})^N

P{a_i = b_i} = 256 / (256*256) = /*252^2 - число всевозможных
                                   комбинаций a,b*/
             = 1/256

Т.е. ответ (1/256)^N

>Вот и интересно - какова вероятность совпадения двух исходников.

Либо надо попытаться максимально точно описать содержимое файлов, либо тупо посчитать как для "случайного набора буков". Второе проще, но результат будет весьма далёк от правильного, первого значения.

Второй вариант.

Пусть в тексте используется m знаков (сколько их там на самом деле -- посчитаешь). Тогда для данной работы длиной N символов вероятность совпадения с другой работой (такого же размера) равна (1/m)^N.

>> Смотря что ещё дополнительно известно про содержимое файлов. Одно дело, когда внутри текст в latin1, другое дело, когда набор из /dev/random

>Глупости. Какая разница, что там внутри.

Огромная разница. man условная вероятность. Если на пальцах -- сравни шанс встретить голого мужика в душевой и на северном полюсе.

Ананимус-школьник=тян детектед, про Шеннона слыхом не слыхивал. Двойка.

P.S. Вероятность зависит от языка программирования, стиля писавших исходники, их характеров и много еще. Если оба любители писать строго по книжке, то весьма большая.

> Какая разница, что там внутри. Есть два подмножества из N членов. Вероятность совпадения определяется одной формулой.

Чуваки, вы Шеннона и Котельникова не проходили в школе?

Есть информационная энтропия, которая зависит именно от характера содержимого файла.

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

А энтропия информации = условная вероятность, как тут уже написали. При шифровании энтропия сохраняется, так что нормальная криптография должна "скрывать" характер информации, не позволяющий косвенно оценить энтропию и статистически поломать шифр.

Учиться, учиться и ещё раз..

> Вот и интересно - какова вероятность совпадения двух исходников.

читать про трансформации исходного кода, рефакторинг, метапрограммирование, преобразования AST, обфускаторы.

Оценивать "совпадение" надо семантики, а не текста-в-текст буквально. Грубо говоря, если ты переименуешь переменные и навставляешь левых неиспользуемых или промежуточных переменных, всё равно AST у тебя не изменятся и это будут одна и та же программа. Если AST изоморфны, почти то же самое.

"вероятность совпадения двух исходников" в смысле кто у кого спёр легко определяется кто с кем мог контачить, анализом стиля. Был в интернете сайт-программа какого-то препода, которая автоматически определяла плагиат, погугли.

> Т.е. ответ (1/256)^N

по-твоему, все комбинации бит равновероятны, и след. не зависит от предыдущих? lol

>Сдана одна и та же "лаба по программированию".

>Вот и интересно - какова вероятность совпадения двух исходников.

как препод я тебе скажу, что из двух курсов обычно бывает процентов 20-30% уникальных работ, они сразу запоминаются, потом у каждого студиозуса если есть что сказать, есть работа, то у него есть свой стиль, который проглядывает между строк. Так что кто у кого спёр сразу видно, всё равно работ-то мало и они все на виду.

Общее число комбинаций для одного файла: 2^{8N}
Общее число комбинаций для n файла: 2^{8Nn}

Интересует одновременное одинаковое состояние всех файлов; таких состояний 2^{8N} (независимо от числа файлов, т. к. все одинаковые)

Итого, вероятность (согласно классическому определению) P = 2^{8N(1-n)}

Проверка для n=1 =) P=1, то есть файл всегда совпадает с самим собой =)

проще ограничить по числу студентов в группе/на курсе, макс. количеству контактов одного студента :)

>Вероятность зависит от языка программирования, стиля писавших исходники, их характеров и много еще. Если оба любители писать строго по книжке, то весьма большая.

+1, вероятность побайтного совпадения двух хеллоувордов одинакового размера близка к единице.

А вероятность совпадения размеров автора не интересует что ли?

А как сравнивать? Если я в начале пустую строку добавлю, файлы будут считаться разными на одну строку или на все строки?

сильно не ругайте, у меня и капча braking.

метрики KLOC/SLOC ?
но они от языка зависят, вот мерять AST -- уже лучше

>А как сравнивать?

Никак. Но нужно, если автор хочет посчитать вероятность совпадения любых двух работ.

>по-твоему, все комбинации бит равновероятны, и след. не зависит от предыдущих?

В постановке в начале топика это так

два произвольных файла из /dev/urandom, как тебе тут уже писали или всё-таки текст?

если текст, то на каком языке? живой естественный язык или формальный язык программирования?

например, в разных языках частоты встречаемости *букв* разные. Если просто составить таблицы частот, а потом симметрично зашифровать (например, одноразовым криптоблокнотом, читай "Криптономикон" Н. Стивенсона, увлекательная байка) -- можно определить язык, на котором текст.

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

Возникают "марковские цепочки" вероятностей встречаемости элементов предложения (букв в слогах, слогов в слове, слов в предложении). Например, как работает бредогенератор текста вроде http://vesna.yandex.ru ? анализирует встречаемость элементов, условную вероятность для разных стилей текста по базе текстов в одном стиле; строит марковские цепочки вероятности, причёсывает синтаксис, (тут уже начинается анализ ЕЯ)

А для авторских работ это в каком-то смысле проще -- у каждого автора вырабатывается свой уникальный стиль который плагиаторы копипастой переработать не в состоянии, так что простой литературоведческий анализ работ автора может сказать, свой он у него или "на основе" другого автора или стянут целиком. Конечно, для нормального анализа должно быть достаточно много материала.

с формальными языками вроде языков программирования в чём-то проще, но в целом так же (в чём-то стиль заметить ещё проще).

В общем, дети, читайте книжки, хотя бы с того же "Код"а Петцольда, курите буквари по радиотехнике, теории информации и криптографии

и нарабатывайте свой язык, пишите материала *много* чтобы ваш плагиат было хотя бы не так заметно :)))

Дядя, это ты мне написал?

целился в топикстартера =)

Задача же одна и та же была. Если результат правильный, ответы должны совпадать.

потом он уточнил про лабу