| ← Август 2005 → | ||||||
|
2
|
4
|
|||||
|
9
|
10
|
11
|
12
|
13
|
14
|
|
|
15
|
16
|
17
|
18
|
20
|
21
|
|
|
22
|
25
|
26
|
27
|
28
|
||
|
29
|
30
|
31
|
||||
За последние 60 дней ни разу не выходила
Сайт рассылки:
http://rusfaq.ru
Открыта:
14-07-2005
Статистика
0 за неделю
RusFAQ.ru: Математика
| Информационный Канал Subscribe.Ru |
/ НАУКА И ОБРАЗОВАНИЕ / Точные науки / Математика
Выпуск № 30
от 02.08.2005, 18:30
| Администратор: | Tigran K. Kalaidjian |
| В рассылке: | Подписчиков: 55, Экспертов: 14 |
| В номере: | Вопросов: 2, Ответов: 2 |
Вопрос № 24130: Доброго времени суток всем! Подскажите пожалуйста где найти алгоритм поиска всех "циклов" в графе(имеется в виду направленный граф). То есть найти все ситуации когда выходя из одной вершины по исходящей стрелке проходишь определённый путь и...
Вопрос № 24131: Вопрос из синтеза: "смайлик с висилицей" Очень - очень прошу!!! Объясните мне пожалуйста, почему именно то нули в сегменте B не отображается для цифр 5 и 6 и отображаются для всех остальных? пожалуйста.. как для мла...
| Вопрос № 24.130 |
|
Доброго времени суток всем! Подскажите пожалуйста где найти алгоритм поиска всех "циклов" в графе(имеется в виду направленный граф). То есть найти все ситуации когда выходя из одной вершины по исходящей стрелке проходишь определённый путь и возвращаешься в ту с которой начал: 1-2-3-1 1-2-1 1-1 ... спасибо!!! |
| Отправлен: 27.07.2005, 23:48 Вопрос задал: DeadRat (статус: Посетитель) Всего ответов отправлено: 1 |
| Отвечает: mvp Здравствуйте, DeadRat! Пусть граф задан в виде матрицы инцедентности А, т. е. строчки и столбцы пронумерованы согласно вершинам графа. А(n, m) = 1, если существует направленное ребро из вершины n в вершину m. Если A(n, n) = 1, то это петля. Если возвести матрицу А в квадрат, то получим вершины, которые связаны маршрутом, длиной два. Если возвести в степень n - длиной n. Если, произвести транзитивное замыкание, то получим матрицу достижимости B = A + A^2 + ... + A^n. B(n, m) <> 0, если существует путь из вершины n в вершину m. Для вашей задачи суммирование не обязательно, вам нужно лишь возвети матрицы в степени вплоть до n. Обозначим: A(1)=A, A(2) = A^2, ..., A(n) = A^(n). Если А(k)(i, i) = 1, то существует цыкл длиной k, проходящий через вершину i. Чтобы определить, через какие вершины ещё проходит цыкл, смотрим матрицу А(к - 1) на i -ю строку. В ней содержатся вершины, которые достигаюся с i-ой, за k-1 шагов. Нам нужно найти вершину р, такую что А(к-1)(i, p)<>0 и А(1)(p, i) = 1, т. е. из которой есть путь длины 1 в вершину i. Далее рассматриваем матрицу А(k-2) и смотрим на p-ю строку. Нужно найти вершину p1, такую что А(k - 2), (p, p1) <> 0 и А(1)(p1, p) = 1 и т. д., пока не дойдём до А(2). Полученная цепочка в обратном направлении и будет наш цыкл: i- (pk-3)-...-p1-p-i. Остаётся заметить, что могут быть цыклы разной длины, проходящие через одну вершину, и все они будут найдены. Но ещё могут существовать разные цыклы одинаковой длины, проходящие через одну и туже вершину, тогда поиск назад нужно будет проводит для всех вершин, удовлетворяющих условию (см. выше). --------- Моя совесть чиста - не бывшая в употреблении |
| Ответ отправил: mvp (статус: 3-ий класс) Отправлен: 28.07.2005, 15:47 |
| Вопрос № 24.131 |
|
Вопрос из синтеза: "смайлик с висилицей" Очень - очень прошу!!! Объясните мне пожалуйста, почему именно то нули в сегменте B не отображается для цифр 5 и 6 и отображаются для всех остальных? пожалуйста.. как для младенца. Объясните...!!! Не ругайтесь... "смайлик без висилицы" :-) Если можно, то скажите, где можно найти подобные примеры таких задач, как синтезировать схемы. Приложение: |
| Отправлен: 27.07.2005, 23:51 Вопрос задал: Терсков Алексей Николаевич (статус: Посетитель) Всего ответов отправлено: 1 |
| Отвечает: Ayl Здравствуйте, Терсков Алексей Николаевич! Чего-чего? Какие-такие нули? Давай сначала. Вот твой семисегментный элемент: A F B G E C D Расписываем таблицу зависимости сегментов от цифр (таблица 1): 0: A, B, C, D, E, F 1: B, C 2: A, B, D, E, G 3: A, B, C, D, G 4: B, C, F, G 5: A, C, D, F, G 6: A, C, D, E, F, G 7: A, B, C 8: A, B, C, D, E, F, G 9: A, B, C, D, F, G Т.о., видим, что сегмент B должен гореть при всех цифрах, кроме 5 и 6. Кодируем цифры с помощью 4-х сигналов x3, x2, x1, x0. Для этого для КАЖДОЙ цифры n мы должны составить такую функцию Fn(X), где X - это множество {x3, x2, x1, x0}, чтобы Fn(n) = 1 и Fn(k) = 0 для k != n. Такая функция есть конъюнкция переменных x3, x2, x1, x0, причем переменная берется "как есть", если в двоичной записи этой цифры в соответствующем разряде стоит 1, и с отрицанием, если 0. Получаем 10 функций: F0(X), F1(X), ..., F9(X). Теперь для каждого элемента e из множества E = {A, B, C, D, E, F, G} 7-ми сегментного индикатора нужно написать функцию G(e, X) такую, чтобы G(e, X) = 1, когда элемент e входит в множество сегментов для цифры n = X' (X' - это значение выражения x3*8+x2*4+x1*2+x0), и G(e, X) = 0 в противном случае (см.Таблицу 1). Эта функция определяется дизъюнкцией таких Fn(X), для которых в Таблице 1 элемент e входит в множество сегментов для цифры n. Т.о., для сегмента B функция G(B, X) = F0(X)+F1(X)+F2(X)+F3(X)+F4(X)+F7(X)+F8(X)+F9(X). А насчет того, почему 0 не отображаются, так это следует из того, как строилась функция G(e, X). > Очень прошу от вас словестный алгоритм как получились значения функции Fb = 0 для цифр 5 и 6. Хм. Вообще-то, сначала строится функция G(B, X) и уже в нее подставляются значения X для цифр 5 и 6. Если произведешь все вычисления, то убедишься, что G(e, X) = 0, если X={0,1,0,1} или X={0,1,1,0} и G(e,X)=1 для остальных наборов, кроме двоичных разложений чисел от 10 до 15. Для них тоже 0, т.к. они не учитывались. Насчет того, где найти. Попробуй в инете по словам: "синтез логических схем", "построение логических схем", "прикладная теория цифровых аппаратов" и т.п. У меня в институте был курс ПТЦА, там я и научился... --------- Трудное - то, что можно сделать немедленно. Невозможное - то, для выполнения чего требуется немного больше времени |
| Ответ отправил: Ayl (статус: Профессор) Отправлен: 28.07.2005, 12:10 Оценка за ответ: 5 Комментарий оценки: Да сразу всего не понять! Буду разбираться! |
© 2001-2005, RusFAQ.ru, Россия, Москва. Все права защищены.
Идея, дизайн, программирование, авторское право: Калашников О.А.
Subscribe.Ru
Поддержка подписчиков
Другие рассылки этой тематики
Другие рассылки этого автора
Подписан адрес:
Код этой рассылки:
science.exact.mathematicsfaq
Отписаться
Вспомнить пароль
| В избранное | ||
