Вопросы по алгоритмам и технологиям

Здравствуйте!

Хочу попросить помощи по пяти задачам из универа. Гуглить пытался, но ничего толкового это не дало.

Первый вопрос по дисциплине "Моделирование". Препод на лекциях данный критерий не давал, а когда подходил за консультацией, то он не смог объяснить и предложил взять другой. Но у меня сейчас просто принцип разобраться именно с этим критерием.
Второй вопрос по дисциплине "Теория принятия решений". Там на мой вопрос препод смогла сказать только про то, что надо использовать деревья, теорию графов и, возможно, рекурсию. А как именно не сказала. Сам дойти не могу.
Оставшиеся вопросы по дисциплине "Системное программное обеспечение". Лекции и методички написаны в основном для MS DOS. В крайнем случае для MS Windows. По поводу написания кода для Linux-систем он ничего сказать не смог, т.к., как он говорит, почти не использовал.

1) Критерий промежутков между днями рождений
Собственно данный критерий описан в "Искусстве программирования" Кнута (2 том), но не так подробно, как хотелось бы.
В данном критерии используется переменная R, которая показывает числа равных промежутков. Но проблема заключается в том, что в последовательности промежутков могут быть разные числа и они могут повторяться (например, [0, 0, 1, 2, 3, 5]). Как в этом случае считать R? Также в данном параграфе, на удивление, ни слова не сказано о вычислении вероятностей (указаны только для конкретного примера). Можно использовать их или как-то вычислять?

2) Оптимизация опорного плана методом потенциалов
Имеется опорный план, который надо оптимизировать вышеуказанным методом. Дошел до момента составления циклов. Здесь по данному моменту указано только то, что надо желательно использовать рекурсивный алгоритм. Теоретически надо использовать дерево для хранения информации, но как это правильно сделать не представляю.

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

4) Демон, таймер, прерывания
Требуется написать демона, который по нажатию комбинации клавиш на клавиатуре (написать свое прерывание) будет по таймеру выводить какую-либо информацию в окно терминала. Если по написанию демонов информации навалом, то со всем остальным проблемы. Пробовал читать мануал по settimer() но ничего путного из этого не вышло. Также читал http://linuxforum.ru/viewtopic.php?id=18995 и http://linuxforum.ru/viewtopic.php?id=18235, но разобраться не смог. По написанию своих прерываний толковой информации найти не смог.

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

Прошу помощи. Если кто-нибудь сможет меня подтолкнуть в нужном направлении, то буду премного благодарен.

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

3) "как минимум название и частоту системной шины" - противные характеристики... ИМХО надо смотреть, туда, откуда dmidecode берёт инфу.
и что вообще такое название системной шины и что вы понимаете под системной шиной? FSB?

4) сдаётся мне в оригинале это звучало "написать резидентную программу под dos". предлагаю поставить dosbox и не откланяться от задания - так будет и проще и полезней.

5) звучит как бред...
взаимоблокировка: создаёте два мьютикса и потоки их захватывают/освобождают пока оба не повиснут в тупике.
переполнение буфера оно и в африке переполнение буфера.

ЗЫ: Внимание товарищи студенты и все остальные учащиеся

"Fat-Zer" написал:

FSB?

Да, вероятно она.

"Fat-Zer" написал:

"написать резидентную программу под dos"

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

"Fat-Zer" написал:

взаимоблокировка: создаёте два мьютикса и потоки их захватывают/освобождают пока оба не повиснут в тупике.
переполнение буфера оно и в африке переполнение буфера.

А поподробнее можно? И как это показать из программы?

"Fat-Zer" написал:

ЗЫ: Внимание товарищи студенты и все остальные учащиеся

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

Также хотелось бы получить ответы и по первым двум вопросам.

"Osanve" написал:

Да, вероятно она.

ЕМНИП для FSB универсальных способов нет... оно где-то в памяти и зависит от оборудования...

"Osanve" написал:

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

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

"Osanve" написал:

А поподробнее можно? И как это показать из программы?

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

"Osanve" написал:

данный пост нарушает указанные по ссылке правила, то прошу закрыть тему.

я к тому что:

"Fat-Zer" написал:

Вопросы по содержанию задания здесь задавать мало-полезно, ибо форумчане не ваши преподаватели и не знают "что тут подразумевается"

"Osanve" написал:

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

Язык какой надо?

"Fat-Zer" написал:

так что делаете так же как с мышью (это же вы с год назад с ней игрались?)

Да, я с ней игрался, только полгода назад. В конце концов использовал gpmlib.

"Fat-Zer" написал:

блокировку можно показать так: каждый поток периодически что-то печатает, а потом перестаёт...

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

"NoXi0uZ" написал:

Язык какой надо?

Язык в принципе не важен. Я выбрал С.

"Fat-Zer" написал:

я к тому что:
Fat-Zer пишет:

Вопросы по содержанию задания здесь задавать мало-полезно, ибо форумчане не ваши преподаватели и не знают "что тут подразумевается"

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

"Fat-Zer" написал:

таймер - или подписываетесь на SIG_ALARM или банально уходите в sleep()

Благодарю. Препод это одобрил, следовательно одной проблемой меньше.

"Fat-Zer" написал:

ЕМНИП для FSB универсальных способов нет... оно где-то в памяти и зависит от оборудования...

А если взять конкретно ASUS eeePC 1001PXD с Debian amd64 на борту. То что тогда делать?

"Osanve" написал:

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

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

"Osanve" написал:

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

ну да... правда я их всё равно не распарсил....

"Osanve" написал:

А если взять конкретно ASUS eeePC 1001PXD с Debian amd64 на борту. То что тогда делать?

ладно... скажу прямым текстом: глупая это затея... ИМХО частоту FSB хрен-получишь...

"Fat-Zer" написал:

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

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

"Fat-Zer" написал:

ну да... правда я их всё равно не распарсил....

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

"Fat-Zer" написал:

ладно... скажу прямым текстом: глупая это затея... ИМХО частоту FSB хрен-получишь...

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

"Osanve" написал:

Препод говорил, что есть стандартная функция в винде. Правда на MSDN я ее найти не смог.

"bormant" написал:

Посмотрите в районе WMI - Computer System Hardware Classes: http://msdn.microsoft.com/en-us/library … s.85).aspx

Благодарю. Вероятно имело ввиду это: http://msdn.microsoft.com/en-us/library/windows/desktop/aa394123%28v=vs.85%29.aspx

"Osanve" написал:

Взаимоблокировка в кольцевом буфере - это когда указатель на считывание обгоняет указатель на запись

бред какой-то... это не взаимоблокировка... это вообще некорректное поведение для кольцевой очереди.

"Osanve" написал:

А вот как в кольцевом буфере определить, что уже некуда писать не понимаю.

когда кольцевой буфер полностью заполнен: "голова догнала хвост".

"Osanve" написал:

Благодарю. Вероятно имело ввиду это: http://msdn.microsoft.com/en-us/library … 85%29.aspx

фигня какая-то... и где вы тут частоту увидели?

"Fat-Zer" написал:

фигня какая-то... и где вы тут частоту увидели?

Да, каюсь, обознался. Сейчас в руки, наконец-то, попала методичка там упоминается это: http://msdn.microsoft.com/en-us/library/windows/desktop/aa394072%28v=vs.85%29.aspx

"Fat-Zer" написал:

бред какой-то... это не взаимоблокировка... это вообще некорректное поведение для кольцевой очереди.

Но препод сказал, что данный момент надо показать

"Fat-Zer" написал:

когда кольцевой буфер полностью заполнен: "голова догнала хвост".

Благодарю

Прошу проверить и оценить код по первому вопросу (вроде как разобрался) (Python 3)

def birthdays():
    m = 2**25
    n = 512
    r_array = [0, 0, 0, 0]
    p_array = [0.368801577,
               0.369035243,
               0.183471182,
               0.078691997]
    for i in range(1000):
        queye = [int(random.random()*m) for j in range(n)]
        queye.sort()
        sub_queye = [queye[j] - queye[j-1] for j in range(1, len(queye))]
        sub_queye.append(queye[0] + m - queye[-1])
        sub_queye.sort()
        r = 0
        for j in range(1, len(sub_queye)):
            if(sub_queye[j] == sub_queye[j-1]):
                r += 1
        if(r >= 3):
            r_array[3] += 1
        else:
            r_array[r] += 1
    V = 0
    n = sum(r_array)
    for i in range(4):
        V += r_array[i]**2 / p_array[i]
    V /= n
    V -= n
    hi = hi_sqr_kv(3)
    if((V >= hi[2]) and (V <= hi[3])):
        return 'Генератор псевдослучайных чисел удовлетворителен'
    elif((V >= hi[1]) and (V <= hi[4])):
        return 'Генератор псевдослучайных чисел слегка подозрителен'
    elif((V >= hi[0]) and (V <= hi[5])):
        return 'Генератор псевдослучайных чисел подозрителен'
    else:
        return 'Генератор псевдослучайных чисел неудовлетворителен'

Описание критерия слово в слово как у Кнута.

Взаимоблокировка в тривиальном случае:
Для выполнения операции каждому из процессов 1 и 2 требуется наличие обоих ресурсов A и B. ВременнАя диаграмма:
- Процесс 1 захватил ресурс A
- Процесс 2 захватил ресурс B
- Процесс 1 пытается захватить и ждёт освобождения ресурса B
- Процесс 2 пытается захватить и ждёт освобождения ресурса A
deadlock

"bormant" написал:

Взаимоблокировка в тривиальном случае:
Для выполнения операции каждому из процессов 1 и 2 требуется наличие обоих ресурсов A и B. ВременнАя диаграмма:
- Процесс 1 захватил ресурс A
- Процесс 2 захватил ресурс B
- Процесс 1 пытается захватить и ждёт освобождения ресурса B
- Процесс 2 пытается захватить и ждёт освобождения ресурса A
deadlock

Это я знаю, курс на интуите по осям читал :) Просто на данный момент Fat-Zer не может понять смысла задания. Хотя я тоже. Для чего показывать взаимоблокировку, если ее надо избегать? Но этот вопрос уже выходит за рамки темы.

"Osanve" написал:

Да, каюсь, обознался. Сейчас в руки, наконец-то, попала методичка там упоминается это: http://msdn.microsoft.com/en-us/library … 85%29.aspx

частоты по прежнему не вижу... для остальных характеристик никакого высокоуровнего интерфейса АФАИК нет... только ручками, из памяти, как dmidecode делает... и то если они доступны...

"Osanve" написал:

Для чего показывать взаимоблокировку, если ее надо избегать?

"Fat-Zer" написал:

как dmidecode делает

Благодарю. Может что-нибудь интересное у них найду, если это то: http://linux.die.net/man/8/dmidecode, http://www.nongnu.org/dmidecode/

"bormant" написал:

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

Благодарю за разъяснения.