Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Если не сложно, приведи пример дипломной работы твоего вуза, удостоенной "Editor Choice" в PC Magazine.
А медаль "лучшему бетоноукладчику" не показать? Сама постановка вопроса уже выдает Вас с головой.
Пример, который Вы привели и просите у меня, — это результат добротной инженерной работы: ноль науки, зато много вероятно неплохого кодинга. Это отличный результат для трехмесячных курсов программирования ("освой MFC за 12 уроков") или даже для профессионального училища (ПТУ). В университете дипломные работы обычно совсем другие — они должны содержать хоть сколько-то науки, изобретать что-то новое, содержать какие-то нетривиальные идеи. Умения пользоваться MSDN и клепать формочки недостаточно для защиты диплома.
Теперь что касается студенческих работ моего вуза.
Я не преподаватель и не в курсе большей части работ, но кое-какие примеры видел. Вот, например, некоторые студенческие работы моего факультета в области обработки и сжатия видео: http://compression.ru/video/index_ru.htm
Те же технологии в коммерческой упаковке: http://www.yuvsoft.com/technologies.html
Из клиентов (покупателей технологий) — Intel, Samsung, Real и куча компаний поменьше.
Если немного вернуться к теме компрессии, которую тут обсуждали.
У нас на факультете есть спецкурс (т.е. даже не основной предмет), в рамках которого студенты выполняют ряд интересных заданий, в том числе написание универсального компрессора — на это задание дается 2-3 недели (в Вашем вузе за это академика бы давали, похоже). http://graphics.cs.msu.ru/courses/mdc2003/assigns/index.html
А вот пример решения такого задания (написанный за пару недель), который сжимал в среднем лучше, чем тогдашний rar: http://about.thedeemon.com/products/arh/
Здравствуйте, Sinclair, Вы писали:
S>Я уже как-то предлагал в этом форуме сделать такой хеш-код, чтобы двум сообщениям с одинаковым смыслом сопоставлялось одно 32хбитное число. А разным, естественно — разные числа. Это бы позволило эффективно бороться с баянами.
Интересная идея
S>Предположение о том, что сообщений с различными смыслами больше четырех миллиардов не выдерживает никакой критики.
Предположение о том, что некто может однозначно и непогрешимо различать имеют ли разные сообщения одинаковый или различающийся смысл не выдерживает никакой критики.
S>очевидно, что вообще различных сообщений меньше двух миллионов.
Э.. это общее количество сообщений на RSDN вообще?
Здравствуйте, SE, Вы писали:
SE>Предположение о том, что некто может однозначно и непогрешимо различать имеют ли разные сообщения одинаковый или различающийся смысл не выдерживает никакой критики.
С таким настроением ты грант не получишь S>>очевидно, что вообще различных сообщений меньше двух миллионов. SE>Э.. это общее количество сообщений на RSDN вообще?
Это заведомо больше, чем общее количество сообщений на RSDN.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>>>очевидно, что вообще различных сообщений меньше двух миллионов. SE>>Э.. это общее количество сообщений на RSDN вообще? S>Это заведомо больше, чем общее количество сообщений на RSDN.
Либо я чего то не понял, либо это количество давно уже за 3 млн. перевалило.
... << RSDN@Home 1.2.0 alpha 4 rev. 1095 on Windows Vista 6.0.6001.65536>>
Здравствуйте, D. Mon, Вы писали:
DM>А вот пример решения такого задания (написанный за пару недель), который сжимал в среднем лучше, чем тогдашний rar: DM>http://about.thedeemon.com/products/arh/
Ну, то что арифметическое сжатие один из лучших в плане качества алгоритмов (и весьма простой. кстати) — давно известно. Проблема только в том, что он очень медленный. Хотя конечно, с учетом современных многоядрастых процов, SSE и всяких CUDA ... Неплохая темка для диплома, кстати
... << RSDN@Home 1.2.0 alpha 4 rev. 1095 on Windows Vista 6.0.6001.65536>>
Здравствуйте, AndrewVK, Вы писали:
AVK>Либо я чего то не понял, либо это количество давно уже за 3 млн. перевалило.
ой,
Тогда придется брать хешкоды подлиннее
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[7]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, AndrewVK, Вы писали:
AVK>Ну, то что арифметическое сжатие один из лучших в плане качества алгоритмов (и весьма простой. кстати) — давно известно. Проблема только в том, что он очень медленный. Хотя конечно, с учетом современных многоядрастых процов, SSE и всяких CUDA ...
Само арифметическое сжатие не такое уж и медленное — оно и в rar'е давно используется, и в видеокодеках (например, Lagarith — довольно шустро сжимает видео без потерь, используя быструю реализацию арифм. сжатия, где деление выражено через умножение; и CABAC — то что в H.264 вместо Хаффмана). Но само по себе оно много не дает по сжатию, и мощным становится в сочетании с контекстным моделированием, которое требует кучу памяти и потому уже тормозит.
Здравствуйте, Nuzhny, Вы писали:
VD>>Дваркин, я тебя умоляю, ты только иероглифы не изобретай, а то ведь китайцы и японцы в суд подадут.
N>Стыд и срам. Переход на личности в споре, оскорбления и каверканье фамилии. Давно такого не было, но я краснею.
Какой спор? Какой переход? Смешно, вот и смеюсь.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[6]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, D. Mon, Вы писали:
DM>А медаль "лучшему бетоноукладчику" не показать?
Такие аргументы обычно приводят, когда более серьезных нет.
>Сама постановка вопроса уже выдает Вас с головой. DM>Пример, который Вы привели и просите у меня, — это результат добротной инженерной работы: ноль науки, зато много вероятно неплохого кодинга. Это отличный результат для трехмесячных курсов программирования ("освой MFC за 12 уроков") или даже для профессионального училища (ПТУ).
Прекрасная идея! Предлагаю автору приступить к ее реализации. Схема такая — идешь в ближайшее подходящее ПТУ (или курсы), набираешь там человек 15-20, даешь им задания, и через 3 месяца мы имеем с десяток программ , выполненных на уровне мировых стандартов, которые PC Magazine тут же немедленно прореферирует и будет рекомендовать всем, кто этот журнал читает. Дальше, конечно, найдутся последователи, и через пару лет мы закидаем весь мир высококачественным ПО на самую различную тематику, так что PC Magazine и др. журналы будут не успевать их рецензировать!
>В университете дипломные работы обычно совсем другие — они должны содержать хоть сколько-то науки, изобретать что-то новое, содержать какие-то нетривиальные идеи.
Если речь идет о студентах, которые действительно имеют своей целью работать в науке, идти после вуза в аспирантуру, то ты прав — их дипломная работа должна продемонстрировать, что они к такой деятельности способны.
Но я готовлю программистов. Не научных сотрудников, а просто программистов. И студенты мои ориентированы именно на программистскую карьеру, а отнюдь не на научную. И вот здесь идея о том, что они обязательно должны на дипломе заниматься тем, что им больше никогда не придется делать, мне кажется совершенно неверной. Пусть они лучше научатся как следует делать то, чем им придется потом заниматься.
А иначе интересный эффект может получиться. Потребуем от всех студентов, чтобы они, по твоей рекомендации, на дипломе занимались научной работой. Но дипломирование через полгода закончится, и... куда их теперь ? Всех в науку ? Там мест такого количества нет, да и не надо, да и не хотят они. Все же в программисты пойдут ? Но там им мощную конкуренцию составят выпускники трехмесячных курсов программирования ("освой MFC за 12 уроков") и профессиональных училищ (ПТУ), которые за то же время напишут программы мирового класса, как ты обещал. . Они пожалуй, и нынешних программистов всех вытеснят...
Да... До чего не дойдешь, если поставить перед собой задачу во что бы то доказать свою правоту. Несмотря ни и невзирая на.
DM>Если немного вернуться к теме компрессии, которую тут обсуждали. DM>У нас на факультете есть спецкурс (т.е. даже не основной предмет), в рамках которого студенты выполняют ряд интересных заданий, в том числе написание универсального компрессора — на это задание дается 2-3 недели (в Вашем вузе за это академика бы давали, похоже).
Ну никак не может дойти до тебя (и до других тоже, увы), что я вовсе не тему компрессии предложил обсуждать!
DM>А вот пример решения такого задания (написанный за пару недель), который сжимал в среднем лучше, чем тогдашний rar:
И не сжатия! А иного представления входных данных!
With best regards
Pavel Dvorkin
Re[7]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Но я готовлю программистов. Не научных сотрудников, а просто программистов.
Как говорится — делай хорошо, а плохо оно само получится.
Обучение науке на программистском вузе/потоке — это в первую очередь разработка алгоритмов, изучение непонятной проблемной области, и построение модели ее решения. А это в последующей "программистской деятельности" пригодится очень много раз.
Я вот никакой хоть сколько то приличной научной работы написать не смог, и все равно считаю, что не зря меня на факультете учили заниматься наукой и преподавали математику и общие основы программирования, а не "то, что потребуется в реальной работе". То, что требуется в реальной работе — меняется постоянно, а необходимость решать проблемы — остается постоянно.
Re[7]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Но я готовлю программистов. Не научных сотрудников, а просто программистов. И студенты мои ориентированы именно на программистскую карьеру, а отнюдь не на научную. И вот здесь идея о том, что они обязательно должны на дипломе заниматься тем, что им больше никогда не придется делать, мне кажется совершенно неверной. Пусть они лучше научатся как следует делать то, чем им придется потом заниматься.
Собственно, примерно это я и понял о Вашем вузе и его преподавателях. Такие училища стране тоже нужны.
PD>А иначе интересный эффект может получиться. Потребуем от всех студентов, чтобы они, по твоей рекомендации, на дипломе занимались научной работой. Но дипломирование через полгода закончится, и... куда их теперь ? Всех в науку ?
Главное, чтобы научились думать и учиться (и правильный диплом должен этому способствовать, и даже требовать). Тогда можно и в борщ, и в красную армию, тьфу, т.е. и в науку, и в индустрию. А вот если научились только конкретный инструмент использовать, то им уже сложнее придется.
PD>Да... До чего не дойдешь, если поставить перед собой задачу во что бы то доказать свою правоту. Несмотря ни и невзирая на.
Вы очень самокритичны, это хорошо.
PD>Ну никак не может дойти до тебя (и до других тоже, увы), что я вовсе не тему компрессии предложил обсуждать!
Ну, раз мне и другим это было столь неочевидно, значит так хорошо объяснили.
Я в первом посте увидел два аспекта идеи:
1. Экономия места/трафика (т.е. все же компрессия). Этот вопрос был позднее разобран, идея не выдержала критики, а автор оказался не знаком ни с азами теории информации (работами Шеннона и Колмогорова), ни с арифметикой. И учиться тоже не хочет, похоже.
2. Независимость от кодировки текста. Это идея не рабочая, т.к. там же было предложено не входящие в словарь слова посылать как есть, т.е. все равно в некоторой кодировке.
Re[2]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Sergey, Вы писали:
S>Архиваторы примерно так и работают. Только у них слово не совпадает со словом языка, да и словарь они вместе с сообщением пересылают.
У архиваторов могут быть адаптивные алгоритмы.
Договариваются об исходных стартовых условиях (например: равномерное распределение букв), кодируют/декодируют очередную букву (Хаффман) или строчку (Лемпел-Зив) и корректируют словарь.
В этом случае пересылка стартового словаря — это пересылка номера (каким словарём пользоваться). Очень компактно!
Ну а ЛЗ с окном вообще не требует словаря — там в роли словаря выступает хвост декодированного текста.
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[2]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, netch80, Вы писали:
N>Идея не новая. У автора ARJ был следующий архиватор JAR (не путать с явовским суффиксом файлов), в котором был словарь английского и подстановка номера слова при сжатии. Я его видел в районе 95-го, но он страшно жрал память и диск, и что-то с реализацией не сложилось. Но примерно тогда же начал кончаться и ARJ.
Дядюшка Арджи скончался, отчасти, потому что не поддерживал длинные имена (Windows 95 с FAT32).
Я очень хорошо помню этот трах-тибидох с форматом ZIP, было несколько конкурирующих версий архиватора (две из которых — фирменные, PKWare: pkzip25 и кажется, pkzipw), поддерживавшие LFN. И благодаря этой конкуренции всё как-то хорошо сложилось.
А ардж так и вошёл в Лету с форматом имён 8.3
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[8]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
LCR> Выводы высосаны из пальца.
Возможно.
Считаете ли Вы озвученную тему достойной курсовой работы? Считаете ли Вы допустимым преподавателю программирования в университете не быть знакомым с азами теории информации — идеями Шеннона и Колмогорова?
Re[10]: Кодирование слов при передаче по сети (покритикуйте
D. Mon,
LCR>> Выводы высосаны из пальца.
DM>Возможно. DM>Считаете ли Вы озвученную тему достойной курсовой работы?
Да. Сложность задачи зависит от пристальности взгляда.
Когда студент принесёт программу и результаты сравнения с известными алгоритмами, возникнут вопросы: "почему так плохо?", "как улучшить?". И направления для дальнейших исследований: частотный анализ, морфологический анализ, обобщения алгоритма на смешанные тексты, и дальше на произвольные наборы данных. И не надо говорить, что студент изобретёт велосипед. Во-первых, курсовая — это учебный труд, призванная показать, что студент в состоянии использовать изученный материал. Во-вторых, неожиданности-таки случаются, поскольку разум студента не замутнён "широкоизвестными и хорошо зарекомендовавшими себя решениями", и есть вероятность придумать что-то принципиально новое.
DM> Считаете ли Вы допустимым преподавателю программирования в университете не быть знакомым с азами теории информации — идеями Шеннона и Колмогорова?
Да, считаю. Почему? Потому что теория сложности по Колмогорову нужна только при теоретическом анализе вычислительных алгоритмов. В рамках курсов Павла Лазаревича, даже если взять смежные области радиусом с километр, понятие о k(x) будет только мёртвым грузом. Которое, тем не менее думаю, ему известно.
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
DM>>Возможно. DM>>Считаете ли Вы озвученную тему достойной курсовой работы? LCR>Да. Сложность задачи зависит от пристальности взгляда.
LCR>Когда студент принесёт программу и результаты сравнения с известными алгоритмами, возникнут вопросы: "почему так плохо?", "как улучшить?". И направления для дальнейших исследований:
Насколько я припоминаю, дипломная работа, как любая научная работа, начинается с очень интересной вводной части. В которой пишут историю проблемы, что было сделано уже в этой области, и после этого делается плавный переход к постановке решаемой проблемы.
Эту работы зарезал бы еще рецензент, уважаемый коллега. А если каким-то чудом рецензент бы (не глядя) то подписал, то потом научного руководителя распяли бы на доске. К сожалению. На ВМиК МГУ, выпускником которого является D.Mon, за такую работу человек с высокой определенностью получит неуд.
Re[11]: Кодирование слов при передаче по сети (покритикуйте
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
LCR>Когда студент принесёт программу и результаты сравнения с известными алгоритмами, возникнут вопросы: "почему так плохо?", "как улучшить?". И направления для дальнейших исследований: частотный анализ, морфологический анализ, обобщения алгоритма на смешанные тексты,
Именно это я имел в виду. В частности, есть такое наблюдение — средний человек имеет активный словарный запас всего лишь в несколько тысяч слов (где-то читал, что вроде 2000, боюсь ошибиться). Это, конечно, не означает, что у всех этот запас один и тот же, но безусловно означает, что есть слова "популярные", а есть не очень. Это как-то следует учесть или нет ? Впрочем, это не единственное соображение, конечно, так что прежде чем давать это в виде курсовой, необходимо все хорошенько продумать. И , вполне возможно и даже наверняка здесь нужна консультацию не столько математика, сколько хорошего филолога — лингвиста.
With best regards
Pavel Dvorkin
Re[8]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, fmiracle, Вы писали:
F>Обучение науке на программистском вузе/потоке — это в первую очередь разработка алгоритмов, изучение непонятной проблемной области, и построение модели ее решения. А это в последующей "программистской деятельности" пригодится очень много раз.
Если под словами "в первую очередь" понимать, что это должно быть в начале курса обучения — согласен. Именно это и делается, есть курс по структурам данным и алгоритмам, который я читал лет 7-8. А вот если под словами "в первую очередь" понимать, что это главное (а это , видимо, и есть, то понимание, которое ты сюда вложил) — согласен лишь отчасти. База — дело очень важное, но и знание современных технологий — не менее. Вот предсавь себе выпускника, который эту базу знает очень хорошо, но кроме консольных приложений (разве с их помощью нельзя разрабатывать алгоритмы ?) ничего писать не умеет ? В академическом институте он себе место найдет и будет дальше разрабатывать алгоритмы, но ведь мы готовим все-таки практических программистов. Куда его возьмут в реальных условиях ?
Перекуём баги на фичи!
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
