Дискретный анализ: курсовая работа

Задания на курсовую работу я раздаю уже давно; вот они же, сформулированные более четко:

[kalinin.ru]

Здравствуйте, Андрей Леонидович!

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

Заранее спасибо !

Андрей Леонидович, доброе утро(или день?..)))))))))

Скажите, пожалуйста, какие поставлены ограничения на длину хэш-таблицы?

размер массива порядка 25000 допустим??

добустимо использовать <openssl/md5.h> ?

Всем привет.

Ирина, нет, 25000 может не хвтатить. Ограничений на количество слов нет, кроме естественного (256 букв латинского алфавита), а это о-о-очень много. Однако, в оперативную память все поместится.

То есть вы должны уметь в какой-то момент увеличивать размер хеш-таблицы в зависимости от ее заполненности.

Илья, напомните, пожалуйста, зачем вам md5? Я могу вспомнить проблему проверки целостности файла с данными во втором задани, и все... но во втором задании хвтаит magic number, я не требую проверки целостности через хеши.

Илья,
я вспомнил.

У вас задание про выделение неинформативных блоков из html-страниц? Вы там md5 хотите использовать, для подсчета контрольных сумм блоков? А crc32 там не подойдет?

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

Еще, хочу обратить внимание, что в пример к второму заданию курсовой, вкрались опечатки: команды Save и Load не предваряются восклицательными знаками (хотя должны, по описанию формата входных данных)

Правильно:

! Save /path/to/file
! Load /path/to/file

ну сrc32 - тогда все намного лучше, просто вы на лекции про md5 говорили, и я понял, что это было обязательным условием.
Хорошо, что я ошибался.
Спасибо.

Вопрос по классу string. Разве нельзя написаить свой, а потом его использовать ?

Про string:
Можно.
Но зачем?

просто удобно, использовать его. как использовали "STL-ский".

Илья,

написать класс String очень сложно (как и любую другую библиотеку общего назначения). Даже если вы об этом не задумываетесь, то вы все равно заранее производите какие-то обобщения его функциональности, которые вам, на самом деле, не нужны для решения данного задания курсовой работы.

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

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

И это, на самом деле, не так просто.

Допустим, перед вами есть задача A. Вы взялись ее решать и разбили на подзадачи, A1, A2 и A3. Психологически, очень легко и удобно выбрать из них какую-то самую простую для вас подзадачу (допустим, A1) и броситься на ее решение. При этом вы можете ее обобщить, начать сразу думать об ее универсальности и т.п. и в конце-концов, после долгих мучений и бессонных ночей, решить самым общим образом некую задачу B1, в которую выродилась исходная подзадача A1.

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

Кроме того, очень вероятно что исходное разбиение на подзадачи A1,A2 и A3 было неправильным, а выбрали вы его только из-за того, что в нем возникла задача A1, которую вы сразу обобщаете до B1 и которую вы знаете, как решать. А на самом деле, было разбиение, лучшее A1,A2 и A3, и не содержащее в себе A1, такое тоже может быть.

Выбор оптимального разбиения на подзадачи --- дело опыта и чувства вкуса, на самом деле. У кого много опыта и хороший вкус, лучше разбивает задачу на подзадачи. Но человек малоопытный почему-то всегда пытается выделить известные ему подзадачи и, хоть тресни, не может видеть решение без них.

Вот при наличии в библиотеке языка C функций из string.h создание собственного класса String для решения второго задания курсовой --- излишне обобщенная подзадача. Вам вообще не надо ее решать, так как, несмотря на запрещение STL, у вас все для работы со строками есть.

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

Пока все это писал, вспомнил характерную дискуссию:
[iseg.livejournal.com]
В ней iseg --- Илья Сегалович, человек сделавший поисковую машину Яндекса, сейчас технический директор Яндекса. Кто такой arbat, честно говоря, не знаю, но по стилю его высказываний это и не важно, потому как он там для мебели выступает. Так вот Сегалович в этой переписке написал в одном из своих комментариев:

"Я постараюсь уволить программмиста, который затеет написание еще одного стринга. Ну или по крайней мере не буду платить ему премию. "

Так что написание String'а это известная болезнь, которую надо срочно лечить. То есть, как захочется написать String, сразу бить себя по рукам и приговаривать "не пиши, не пиши" пока не отпустит.

Нужно ли убирать теги оформления внутри <td> </td>.
Или по ним тоже строится словарь частот.

То есть? <td>ааа<u>bbb</u>ccc</td> --- убирать ли <u>? Я бы убирал.

да, так.
но если этого не делать вы снижать оценку будете или нет?
Если будете:
по какому набору тегов проводить отсев ?
спасибо.

Илья,

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

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

Так что, ответ на ваш вопрос следующий: если вы совсем (совсем-совсем!) не сделаете 3-е задание (но при этом сделаете 2 обязательных задания), то общая оценка за всю курсовую работу будет "удовлетворительно". А на пятерку нужно сделать третье задание так, чтобы оно работало (удаляло навигационную обвязку, искало, классифицировало и т.п.) как можно чаще и лучше. Чем лучше, тем больше вероятность пятерки, естественно.

Еще одно уточнение: во втором задании курсовой работы под словом понимается последовательность букв латинского алфавита. То есть, это 26 букв и нет различия между большими и маленькими буквами.

Андрей Леонидович, возможен ли случай сохранения словаря с одним размером таблицы, а затем загрузки того же словаря при другом размере?



//--------------------------
"Я не боюсь потерять голову, я опасаюсь потерять лицо"

Думаю, что размер не важен. Вы же его выбираете исходя из имеющихся данных...

Правда, я не понимаю, каким образом этот размер перед сохранением был выбран один, а перед загрузкой --- иной?

Вот как я планировал делать: сначала мы динамически выделяем память под массив структуры. И заполняем словарь. Когда словарь будет заполнен на 70%, то увеличиваем с помощью realloc'а массив и ре-хешируем словарь с учетом нового размера.

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



//--------------------------
"Я не боюсь потерять голову, я опасаюсь потерять лицо"

А кто мешает уменьшить таблицу до размеров старого словаря?
Можно даже уменьшать не физически (при помощи realloc), а логически (уменьшая размер таблицы, но помня, что на самом деле там есть еще память, до которой при необходимости можно увеличить таблицу без обращения к realloc).

Андрей Леонидович, а существует ли ограничение по времени (в рамках разумного, естественно) ?



//--------------------------
"Я не боюсь потерять голову, я опасаюсь потерять лицо"

насчет b-дерева.. смотрел описание, и возникла пара вопросов: дереву достаточно иметь двух потомков? если на множестве строк располагать одной операцией сравнения, отображающей две строки на 1, 0 то не представляю чего там делать сильноветвистому дереву.. далее, на уровне своей программы за пределы предоставленной оперативной памяти я надеюсь выходить не надо?)

>>Андрей Леонидович, а существует ли ограничение по времени (в
>>рамках разумного, естественно) ?
так там же не просто так дали такие типы данных.. если программа написана как надо, то и работать она будет довольно быстро просто по определению таких данных как деревья, хэш-таблицы и прочие стандартные объекты хранения данных с быстрым поиском, вставкой и тп

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



//--------------------------
"Я не боюсь потерять голову, я опасаюсь потерять лицо"

> Андрей Леонидович, а существует ли ограничение по времени
> (в рамках разумного, естественно) ?

Жестких --- нет, потому что все компьютеры разные и вычислить это время сразу не получится. Но есть логические ограничения на изменения скорости выполнения базовых операций, которые следуют из используемых структур данных.

В вашем случае, на мой взгляд, есть единственная проблема: перестройка всей таблицы. Эта операция действительно выполняется медленно и может сказаться на скорости добавления элемента конкретно того элемента, который вызвал переполнение таблицы. Ну и выполняйте ее пореже: размер таблицы увеличивайте всегда, допустим, в два раза и будет хорошо.

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

> насчет b-дерева.. смотрел описание, и возникла пара вопросов:
> дереву достаточно иметь двух потомков?

Дерево не может иметь потомков. Потомки в "деревянной" терминологии есть у узлов дерева.

Два потомка в Б-дереве могут быть только у корневого элемента. У остальных количество потомков зависят от степени дерева как t-1, ..., 2t-1.

> если на множестве строк располагать одной операцией
> сравнения, отображающей две строки на 1, 0 то не представляю чего
> там делать сильноветвистому дереву..

А какая разница, в каком алфавите представляются ключи в Б-дереве, от этого же нечего не зависит? Там сравниваются сами ключи, а не их представления в каком-либо алфавите.

Зависимость вида дерева от алфавита есть только в дереве ключей, которое в задании второй курсовой представлено в своей модификации PATRICIA. Там, действительно, все ключи представляются в виде последовательности нулей и единиц.

> далее, на уровне своей программы за пределы предоставленной
> оперативной памяти я надеюсь выходить не надо?)

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

ВАЖНО для тех, кто получил первое задание в разделе алгоритмов на строках (про сравнение пяти файлов). Это студенты Брагин, Киселёв, Самбукова и Троепольский.

Я осознал, что первое задание выбивается из всех остальных, где нужно запрограммировать известный и расписанный в книжках чуть ли не до кода алгоритм тем, что там нужно хоть чуть-чуть, но подумать. Поэтому:

- задание можно упростить до следующего вида: найти LCS между двух строк одного файла, состоящих из целых неотрицательных чисел. Используйте алгоритм из Гасфилда.

- если же вы сделаете задание в исходной формулировке, то делать третье задание не нужно.

1) в первом задании, третьего варианта, под алгоритмом бойера-мура подразумевается его самый простой вариант описанный [www.examen.ru] здесь?
2) вы проверили второе задание которое я отсылал по почте?
3) "1. Написать самообучающийся классификатор текстов на основе теоремы Байеса." - какой смысл вкладывается в понятие "самообучающийся"? классификация текстов для какой конкретно задачи должна идти? спам-неспам подойдет?

Уважаемый xaxa3217, это вы всё мне?

Докладываю:

1. В первом задании под алгоритмом Бойера-Мура подразумевается тот алгоритм, который я рассказывал на лекции и так называл. Ещё его можно посмотреть в Гасфилде, я его там вычитал (честно сонаюсь!) Подойдет так же его модификация Апостолико-Джанкарло. Ходить по ссылке и сличать то что там написано с тем, что я рассказывал, я естественно, не буду.

2. Если бы вы ещё точно себя идентифицировали. Впрочем, с этим вопросом всё просто, методом исключений: нет, не проверял.

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

компетентным в условиях курсовой только вы и являетесь, наверное прекрасно это понимаете сами, впрочем, метод исключения, судя по трем ответам на три вопроса, у вас налажен, поэтому мне остается лишь подтвердить - да это всё вам! за первый ответ спасибо, за второй пока не за что, а насчет третьего.. скажу так. у меня, к сожалению, нет возможности восполнить потерянные часы лекций или хотя бы вернуть время вспять, но прошу же как человека (просто представьте, что я только что переведенный на 8ой факультет африканский студент по обмену) - что же все-таки такое этот !самообучающийся! классификатор на !основе! теоремы байеса? у меня эти два выделенных слова вместе не вяжутся, потому что та самая "основа" отодвигается на второй план - так что же нужно писать? самообучающийся классификатор текстов или классификатор текстов на основе теоремы байеса? про спам-неспам смысл вопроса был только в условии да-нет, то есть самих классов текстов должно быть только два или больше? просто пока не ясно к какой практической задаче должно все это свестись.. вы уж простите дурака, у нас в африке все без царя в голове

Вот не надо, я вас прошу, не надо про Африку. Вы же знаете, мы все здесь интернационалисты и к афроПриМатам относимся толерантно.

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

Кстати сказать, если есть бинарный классификатор, то его всегда можно обобщить на сколько угодно тематик, если для каждой из n тематик документов C1...Cn построить свой бинарный классификатор.

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

>>Кстати сказать, если есть бинарный классификатор, то его всегда >>можно обобщить на сколько угодно тематик, если для каждой из n >>тематик документов C1...Cn построить свой бинарный классификатор.
ну это понятно дело, мне конкретика просто нужна была. вдруг нужно сделать антиспам, который определенные тексты писем относит к порно с красивыми девочками, а другой к порно с дедушками. мне тогда было бы дурно фильтры с соотв. "вероятностными словарями" составлять)

Если бы вы раньше объявили сферу ваших интересов, то можно было бы сойтись на задаче определения порнографических картинок, хорошее задание на курсовую для озабоченных студентов.

Исправление же базы на лету это только вопрос пересчёта статистических данных, а не вопрос вида классификатора.

Хороший же спам-фильтр из НБК не сделать. Дело в том, что практически все спам-фильтры, основанные на НБК, как раз и являются поделками уровня курсовой работы. Развитие там заключается, во-первых, в переходе к методу Фишера определения достоверности, и, во-вторых, к использованию дополнительных эвристик определения спама. В итоге, если продукт развивается, обучение там начинает только мешаться.

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

Нет, просто вы неверно понимаете термин. Он самообучающийся из-за метода настройки (наличия процесса обучения), а не из-за своих продуктовых свойств.

Но это, в общем, уже не важно.

Андрей Леонидович, а каким образом можно востановить отчеты по лабораторным работам в случае их утери ?