Дискретный анализ-2008: встреча

Вниманию второго курса 2008-го года, группам 08-206 и 08-208.

В связи с тем, что первые три недели сентября я буду в командировке, я хотел бы встретиться со студентами в субботу, 30.08.08, в 10:00 рядом с кафедрой.

Я хочу познакомиться, рассказать о курсе, ответить на ваши вопросы и раздать задания, чтобы вы могли в сентябре начать делать лабораторные работы и вычислительную практику. Задания будут именными, и раздавать я их буду лично в руки пришедшим.

Здравствуйте, я студент из группы 08-208, Рудешко Антон. Я живу далеко от москвы, и не могу успеть на встречу. Можно попросить вас передать мое задание старосте группы?

Я передам задания Валентину Евгеньевичу Зайцеву, у него их можно будет получить под роспись.

Хорошо, спасибо.

То что я не наблюдаю никакой активности, связанной с зданиями, это значит что всё всем понятно? И задания по вычислительной практике все себе выбрали?

Если же понятно не всё, то можно у меня уточнить.

Я выбрала задание для практики. Оно следующее:

Раздел новости

8. Найтии все эпитеты, связанные с заданным объектом.


Могу ли я взять его себе?

> у меня есть большое желание научиться программировать.

Это не проблема --- достаточно сделать все задания самостоятельно.

> Раздел новости
> 8. Найтии все эпитеты, связанные с заданным объектом.
> Могу ли я взять его себе?

Да, оно не занято. Только мне нужно знать ваше имя, чтобы записать. Если опасаетесь расскрывать инкогнито, можете написать на andrey@kalinin.ru.

В 1 лабе можно пользоваться string'ом ?

> В 1 лабе можно пользоваться string'ом ?

Нет.
Нигде нельзя.

Если я правильно понял,то есть таблицы должны быть упорядочены при помощи заданной СД (например Красно-Черного дерева),а не хранится друг за другом в списке или массиве?

Вроде таблицы должны храниться в списке (например), а данные в таблице храниться с помощью Красно-Черного дерева (например). Разве не так?

Вопросы я понял двояким образом (то ли об организации таблиц, то ли об организации списка таблиц), поэтому попытаюсь ответить и про то, и про другое.

Организация таблицы
--------------------------

Индексов к данным может быть несколько, по разным столбцам.

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

Идентификаторы строкам можно выбирать двояко:
- вычислять как-то по строке
- выделять порядковый номер.

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

Поэтому, логично взять ту же СД и таблицу строить на ней, даже если нет индексов.

Организация списка таблиц
---------------------------------

В задании нет явного ограничения на количество таблиц, кроме оперативной памяти. Это означает, что может быть миллион таблиц из одного элемента, а операция
<таблица> + 1,2,3
всё равно должна выполняться быстро; то есть, таблица должна находиться быстро.

Следовательно, сами таблицы тоже правильно увязать в СД "имя таблицы -> таблица"

Возник вопрос. При использовании метода Patricia всплывает необходимость работы с булевским типом данных. Как его нужно реализовывать? Ведь, в языке программирования C89 этот тип отсутствует, а С99 поидее использовать нельзя.

Во-первых, никакой связи между Patricia и типом bool нет.
Во-вторых, C99 использовать можно.

PS. Но, всё-таки, зачем вам тип bool? Для реализации флажков? Там имелось в виду, что это 1 бит, отведённый под флажки, а это не тип bool (его размер как минимум 1 байт).

Имхо, для Патриции надо использовать флажок транспарант int: 0, когда обе ссылки - не на детей, 1 - когда нулевой на сына, 2 - когда единичный и 3 когда оба. Просто и можно читать бинарными операторами. А памяти - все равно 4 байта.



----------
Дайте мне исходники Вселенной и хороший дебаггер!.. ©

Узел Патриции состоит из:
- количества пропускаемых бит
- идентификатора ключа
- двух ссылок направо и налево
- двух флажков-признаков листовых ссылок

Если считать, что все эти поля (флажки считаем за одно поле) --- целые 32-х битные числа, то узел занимает 5 таких чисел, то есть 5*4=20 байт.

Однако, размер узла можно и уменьшить. К примеру, размерность идентификатора ключа и ссылок зависит от максимального количества узлов, которые мы можем представить. Для узла в 20 байт только на представление 2^32 узлов (максимальное количество идентификаторов) уйдет 80ГБ, такого количества памяти я предоставить точно не смогу, поэтому пространство 2^32 --- излишнее, можно по крайней мере по одному биту откусить от ссылок и от идентификатора ключа. Так как нам нужны только два бита, то их можно спокойно разместить в ссылках (в старших битах, к примеру) и тогда размер узла Патриции сокращается до 16 байт, а пространство представляемых ключей --- до 2^31.

На самом деле, тот факт что и 2^31 тоже излишне большое пространство, да и длина ключей не очень велика, позволяет упаковать количество пропускаемых бит в оставшиеся поля и сократить размер узла до 12 байт.

Что же касается вообще представления узлов, то важно, чтобы из размер был бы кратен 4 (или 8) байтам; для доступа к битовым полям можно использовать либо битовые операции ( x & 0xF0000000 ), либо битовые поля в структурах данных ( struct s { int x : 1; int y : 2; int z : 34} )

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

Например, практически наверняка, с вероятностью 99,(9)% число, представляющее указатель, будет чётным (это связано с выравниванием структур; более того, скорее всего он даже будет кратен выравненному размеру структуры). Следовательно, можно использовать этот эффект для хранения одного флажка: если указатель чётный, то флажок равен 0; если указатель нечётный, то флажок равен 1, а указатель перед фактическим применением нужно на 1 уменьшить.

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

Эх... Вот обучали бы такого плана приемам программирования в институте... Ни одного занятия бы не пропустил! Или до этого надо дойти самому --- и тогда ты тру-программист?



----------
Дайте мне исходники Вселенной и хороший дебаггер!.. ©

Кого вы трёте? Программистов? Впрочем, не важно.

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

Так что зачем его рассказывать в институте? Если будете работать программистом, то когда прижмёт и не такое выдумаете. А на все случаи жизни рецептов дать нельзя.

Можно взять себе для вычислительной практики задние №13(там где рассчитать PageRank страниц),если оно еще не занято?
Мурашев 08-206

Забыл написать: да, 13-е задание ещё не занято, записал за вами.

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

То есть является ли неправильной например такая команда
!new table1(a:!int,b:short,c:!string[10])

И если является, то надо ли ее исправить так
! new table1 ( a : !int , b : short , c : ! string [ 10 ] )

И первая, и вторая команда является правильной.
Как я сказал, количество пробелов между токенами может быть каким угодно (в частности, нулевым).

А есть ли какое-нибудь ограничение(верхний предел) на длину входной строки с командой?

Можно ли считать что идентификаторы не могут начинаться с цифр?

Ограничения на длину строки нет.
Давайте будем считать, что идентификаторы с цифры начинаться не могут. (я из задания это условие убрал в своё время, но, наверное, был неправ)

Андрей Леонидович, можно в качестве варианта задания практикума взять такую задачу: «Выделение связей между людьми в социальной сети ВКонтакте. Определение социальных групп и их состава»?


Пример: [oleshkevich.ru]



KISS; DRY!

А как вы получите доступ к данным ВКонтакта?

это зависит от того сколько потребуется данных. к примеру в первом круге у меня 150 друзей, во втором порядка 10 тысяч в третьем около 70 тысяч.
существуют некоторые проблемы:
а) страницы со списками друзей открыты не у всех, в первом круге примерно у 30 % они закрыты, во второго у 40-60%.
б) страницы с личными данными (главная страница пользователя) открыты у всех друзей первого круга, и у 60% второго круга.
в) таймлимиты на запросы, около 4-5 секунд

я думаю без лишних телодвижений можно собрать информацию о 100К-1М пользователей



KISS; DRY!