Архив форума ЛГ - что у вас в данный момент в буфере обмена?

что у вас в данный момент в буфере обмена?

6yXou

Назад к темам раздела.

2005-12-22 11:42:08

6yXou

Алгоритм Дейкстры
Этот алгоритм ищет кратчайшие расстояния от одной вершины до всех остальных во взвешенном графе без рёбер отрицательного веса за время O(N2). Возможна модификация до времени О(MlogN) при хранении графа списком рёбер, её мы рассматривать не будем. В случае, когда данную задачу необходимо решить на графе с рёбрами отрицательного веса, больше подходит алгоритм Форда-Беллмана, но он работает уже за время O(N3) (или O(MN)).
Данный алгоритм проще пишется для графа, представленного на матрице смежности, однако, если вам потребуется реализовать его для списка рёбер, это не представит большого труда и итоговая сложность работы останется той же.

Итак, перейдём к описанию работы алгоритма. Помимо матрицы смежности нам понадобится массив расстояний D: array[0..MaxN] of Longint и массив меток Use: array[0..MaxN] of Boolean.

Алгоритм работает N итераций, причём на I-ой итерации в элементе D[J] хранится длина кратчайшего пути из стартовой вершины в J-ую, состоящего не более чем из I рёбер. На каждой итерации из массива D выбирается наименьший неиспользованный элемент (пусть его номер равен Min), и производится релаксация по всем рёбрам, исходящим из Min-ной вершины. После этого помечаем Min-ный элемент использованным и заходим на следующую итерацию. Т.о. после отработки N итераций в массиве D будут храниться кратчайшие пути до всех вершин из начальной, состоящие не более чем из N рёбер, т.е. все кратчайшие пути. Вот фрагмент программы, выполняющей данные действия (здесь I, J: Integer, а Х - номер стартовой вершины):

1
2
3
4
5
6
7
8
9
10
11
12
For I := 1 to N do
D[I] := Inf;
D[X] := 0;
D[0] := Inf + 1;
For I := 1 to N do Begin
Min := 0;
For J := 1 to N do
If (D[J] < D[Min]) and not Use[J] Then Min := J;
Use[Min] := True;
For J := 1 to N do
If D[Min] + A[Min, J] < D[J] Then D[J] := D[Min] + A[Min, J];
End;

В строках 1-2 инициализируется массив D, а далее нужно детально рассмотреть несколько моментов. Во-первых, ячейка с номером начальной вершины забивается нулём, а не Inf-ом, поскольку на нулевой итерации алгоритма до начальной вершины путь существует (т.к. он состоит из нуля рёбер) и равен, соответственно, нулю (строка 3). Во-вторых, нам понадобится нулевая ячейка массива D (несмотря на то, что никакой нулевой вершины у нас нет), которая забивается числом Big + 1, чтобы при поиске минимальной нам подошла первая попавшаяся неиспользованная ячейка (строка 4), а заодно и нулевая ячейка массива Use, чтобы не вылезти за границы массива на первой итерации цикла. Нулевая ячейка массива D полагается равной Big + 1, а не просто Big для случая с несвязным графом, при котором в строке 11 Min мог бы быть равен нулю, что привело бы к обращению за границы матрицы смежности. А так нам подойдёт неиспользованный элемент массива D даже если он равен Inf.

В строке 5 запускается цикл в N обновлений массива D. В строках 6-8 ищется минимальный неиспользованный элемент массива D. В строке 9 он помечается использованным. В строках 10-11 производится релаксация по всем ребрам, исходящим из выбранной вершины (Min).

Если по окончании работы алгоритма в некоторой ячейке массива D всё ещё хранится значение Inf, это значит, что кратчайшего пути из начальной вершины до соответствующей этой ячейке вершины не существует (граф несвязен).

Стоит заметить, что этот же алгоритм используется для решения более распространённой задачи нахождения кратчайшего пути между заданными двумя вершинами в графе. В качестве начальной, соответственно, используется одна из вершин, и выводится значение ячейки D с номером другой вершины. Если это значение равно Big, значит, между этими вершинами не существует пути. Алгоритм, который ищет кратчайшее расстояние только между двумя вершинами, науке неизвестен. Более того, доказано, что алгоритм нахождения кратчайшего расстояния между двумя вершинами графа асимптотически не может быть оптимальнее алгоритма, находящего кратчайшие расстояния от одной вершины до всех остальных.

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

2005-12-22 11:44:04

POCOMAXA

6yXou

2005-12-22 11:59:49

6yXou

1. Теоретические сведения.

Сокеты (sockets) представляют собой высокоуровневый унифицированный интерфейс взаимодействия с телекоммуникационными протоколами. Сокет – это описатель поставщика транспорта.WinSock расположен между сеансовым и транспортным уровнями. Иными словами Winsock управляет всеми аспектами сеанса связи и при необходимости форматирует данные согласно целям программы.
Сокет создается одной из двух функций:
• WSASocket(
int af,
int type,
int protocol,
LPWSAPROTOCOL_INFOA lpProtocolInfo,
GROUP g,
DWORD dwFlags
);

• socket(
int af,
int type,
int protocol
);
Af – Определяет семейство адресов протокола. Например если нужно создать UDP или TCP, нужно подставлять константу AF_INET, чтобы сослатся на протокол IP.
Type – Тип сокета для данного протокола, он может принимать одно из следующих значений SOCK_STREAM, SOCK_DGRAM, SOCK_RAW, SOCK_RDM.
Protocol – указывает конкретный транспорт.
GROUP – всегда равен 0, так как ни одна версия winsock не поддерживает группы.
dwFlags – флаги.

Семейство адресов и разрешение имен.

Для связи средствами WinSock важны механизмы адресации рабочих станций в конкретных протоколах.
При использовании IP компьютерам назначается IP-адрес, состоящий из 32 бит. Для взаимодействия с сервером по TCP или UDP клиент должен указать IP-адрес сервера и номер порта службы. В WinSock IP-адрес и порт службы задаются в структуре SOCKADDR_IN:
struct sockaddr_in {
short sin_family;
u_short sin_port;
struct in_addr sin_addr;
char sin_zero[8];
};
Sin_family – должно быть AF_INET, то есть указывает на использовании протокола IP.
Sin_port – задает какой коммуникационный порт TCP или UDP будет использоватся.
Sin_addr – структуры SOCKADDR_IN хранит IP-адрес в 4 байтном виде.
Sin_zero – это поле является просто заполнителем что бы структура SOCKADDR_IN равнялась структуре SOCKADDR.

Порядок байт.
Разные процессоры в зависимости от конструкции представляют числа в одном из двух порядков байт: big-endian или little-endian. Например процессор Intel x86 представляет многобайтные числа, следую от менее значимого к более значимому байту (little-endian).
Если номер порта и IP-адрес хранятся в памяти компьютера, они хранятся в системном порядке (host-byte-order). Но стандарты Интернет требуют, чтобы многобайтные значения представлялись от старшего байта к младшему (в порядке big-endian), что обычно называется сетевым порядком (network-byte-order).
Существует ряд функция для преобразования многобайтных чисел из системного порядка в сетевой и обратно.
Функции для преобразования из системного порядка в сетевой:

• u_long htonl(u_long hostlong);
• int WSAHtonl(…);
• u_short htons(u_short hostshort);
• int WSAHtons(…);

Функции для преобразования из сетевого порядка в системный:

• u_long ntohl(u_long netlong);
• int WSANtohl(…);
• u_short ntohs(u_short nethort);
• int WSANtohs(…);
•
Разрешение имен.
Для подключения к узлу по IP Winsock-приложении должно знать IP адрес этого узла, но большинство людей обращаются к компьютерам при помощи легко запоминаемых имен узлов, а не IP-адрес.
В Winsock представлено несколько функций для определения IP-адреса по имени узла:
• gethostbyname(…);
• WSAAsyncGetHostByName(…);
И несколько функций для обратной задачи, определения имени по IP-адресу:
• gethostbyaddr(…);
• WSAAsyncGetHostByAddr(…);
Все перечисленные выше функции возвращают после своего выполнения структуру HOSTENT:
struct hostent {
char FAR * h_name;
char FAR * FAR * h_aliases
short h_addrtype;
short h_length;
char FAR * FAR * h_addr_list;
};

h_name – имя узла, если в сети используется DNS, то в качестве имени сервера будет возвращено полное имя домена.
H_aliases – массив дополнительных имен узла.
H_addrtype – содержит возвращаемое семейство адресов.
H_length – определяет длину в байтах каждого адреса из поля h_addr_list.
h_addr_list – Массив содержащий IP-адреса узла.

Инициализация Winsock.

Любое winsock приложение перед вызовом функции должно загрузить соответствующую версию библиотеки Winsock.
Int WSAStartup(
WORD wVersionRequested,
LPWSADATA lpWSAData
);
Параметр wVersionRequested задает версию загружаемой библиотеки Winsock. Старший и младший байты определяют дополнительный и основной номер версии библиотеки.
Параметр lpWSAData – указатель на структуру LPWSADATA, которая при вызове функции WSAStartup заполняет сведениями о версии загружаемой библиотеки:

typedef struct WSAData {
WORD wVersion;
WORD wHighVersion;
char szDescription[WSADESCRIPTION_LEN+1];
char szSystemStatus[WSASYS_STATUS_LEN+1];
unsigned short iMaxSockets;
unsigned short iMaxUdpDg;
char FAR * lpVendorInfo;
};

wVersion – значение загруженной версии Winsock.
wHighVersion – значение максимальной версии Winsock.
szDescription, szSystemStatus – заполняются но не во всех версиях Winsock.
iMaxSockets – максимальное значение одновременно открытых сокетов.
iMaxUdpDg – максимальный размер датаграмы.
lpVendorInfo – зарезервировано для информации изготовителя реализации Winsock и не используется ни на одной из платформ Win32.

После создания сокета определенного протокола следует связать его со стандартным адресом, вызвать функцию bind:

int bind(
SOCKET s,
const struct sockaddr FAR * name,
int namelen
);

s – задает сокет на котором ожидается подключение клиентов.
name – структура с параметрами сокета (IP-адрес, порт, тип протокола).
namelen – размер name.

Протоколы, не требующие соединения

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

Простейшая функция приема:

int recvfrom(
SOCKET s,
char FAR * buf,
int len,
int flags,
struct sockaddr FAR * from,
int FAR * fromlen
);

s – сокет для приема данных.
buf – буфер куда будут записываться принятые данные.
len – число принимаемых байт.
flags – флаги.
from – структура SOCKADDR для данного протокола слушающего сокета.
fromlen – длинна структуры from.

Простейшая функция отправки данных:

int sendto(
SOCKET s,
const char FAR * buf,
int len,
int flags,
const struct sockaddr FAR * to,
int tolen
);

s – сокет для приема данных.
buf – буфер который следует отправить.
len – число отправляемых байт.
flags – флаги.
to – указатель на структуру SOCKADDR с адресом принимающей рабочей станции.
tolen – размер структуры to.

Обе функции приема и отправки возвращают, сколько байт реально было принято/отправлено.

2005-12-22 12:03:43

Sing

эээ...что это?

2005-12-22 12:05:41

6yXou

Sing
это отчёты по алгоритму Дейкстры (основы искуственного интелекта) и UDP (вычислительные сети)

2005-12-22 12:13:35

Sing

6yXou
ааа, ну тогда понятно
))

2005-12-22 12:28:27

MyOwn31

У меня в буфере обмена весь "Евгений Онегин" забит... правда, обычным способом не умещается, так что приходится использовать программы для увеличения размера буфера.

2005-12-22 21:06:55

Мясник_Джо

у мну вот чего..

http://www.fantasyland.ru/cgi/forum_rooms_a.php

2005-12-22 21:07:50

DeDarK

http://www.fantasyland.ru/cgi/pl_info.php?login=DeDarK

2005-12-22 21:10:54

Mat

ID: 24811

2005-12-22 21:20:47

DeDarK

а тема хорошая, на АГ в брехнотрепе была когда-то :)

2005-12-22 21:32:34

_TiriL_

у меня вот это:
Shvezar_SATAN (09:08 PM) :
я тут пока домой шел, у мню идея в голову пришла, коли мне и Димасу в принципе негде справить новый год, может собрать в его квартире тех, кто тож собираецца дома его отмечать???

2005-12-22 21:46:28

Dima

_TiriL_

2005-12-22 21:50:15

DocenT

21:33] Вы побеждаете в битве!!! За проведенное сражение Вы получаете 10 EXP и зарабатываете 12 Золота!!

вот что в буфере)

2005-12-22 21:51:33

_TiriL_

Dima
не сцы, это не про тебя :))))

2005-12-22 23:45:54

Дука

С пометкой в гвлерею!!!

2005-12-22 23:46:18

wind

http://www.fantasyland.ru/help_old/item_hlp.php?type=3&level=0

2005-12-22 23:47:30 sm0kez0rr

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

фтЫкаешь ? дафай ечё курнём !

2005-12-23 09:36:36

DeDarK

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

2005-12-23 15:12:54

DeDarK

База: Ледрак
Координаты: 8:82
переименовать базу
Гранит: 14
Спайс: 0 / 500
Кредиты: 213

Энергия: 2 / 5
Войска: 1 / 10

:)

2005-12-24 00:30:58

DeDarK

http://www.fantasyland.ru/cgi/loc.php?rnd=owyy6gcz o204keh1js1i

ну АКТИВНЕЕ!

2005-12-24 11:07:04

6yXou

Задание:
Промоделировать дискретную многотональную модуляцию.

Теория дискретной многотональной модуляции (DMT).
DMT использует модуляцию со многими несущими. Время разбивается на
стандартные «периоды символа» (symbol period), в каждый из которых
передается один DMT – символ, переносящий фиксированное количество бит.
Биты объединяются в группы и присваиваются сигнальным несущим различной
частоты. Следовательно, с частотной точки зрения, DMT разбивает канал на
большое число подканалов.
Биты для каждого подканала преобразуются в сложное число, от значения
которого зависит амплитуда и фаза соответствующего сигнальной несущей
частоты. Таким образом, DMT можно представить как набор КAM систем,
которые функционируют параллельно, каждая на частоте несущей
соответствующей частоте подканала DMT . Итак, DMT
передатчик по существу осуществляет модуляцию путем формирования пакетов
сигнальных несущих для соответствующего количества частотных подканалов,
объединения их вместе и затем посылки их в линию как «символа DMT».
Модуляция/демодуляция с использованием многих несущих реализуется в
полностью цифровой схеме с помощью развития методов быстрого преобразования
Фурье БПФ(Fast Fourier Transform – FFT
При поступлении данных они сохраняются в буфере. Пусть данные поступают
со скоростью R бит/с. Они должные быть разделены на группы бит, которые
будут затем присвоены DMT символу. Скорость передачи DMT символа обратно
пропорциональна его длительности Т, таким образом число бит присваиваемых
символу будет b=R.T. (т.е. символьная скорость будет 1/Т). Из этих b бит,
bi бит (i=1, …, N=16) предназначены для использования в I подканале.
Существенной проблемой является межсимвольная интерференция(ISI). Межсимвольная интерференция проявляется в том, что заключительная часть предыдущего DMT-символа искажает начало следующего символа, чья заключительная часть, в свою очередь искажает начало следующего за ним символа и т.д. Другим словами подканалы не являются полностью независимыми друг от друга с точки зрения частоты. Наличие эффекта ISI приводит к появлению интерференции между несущими (Inter-Carrier Interference – ICI). Для того, чтобы решить данную
проблему существует способы:

. Ввести дополнительный интервал перед каждым символом. В данном случае
передача по линии будет иметь всплески, причем длина такого всплеска
будет равна длине DMT символа. Однако в этом случае всплески, займут лишь
около 30% всего времени, что критически снизит эффективность ADSL
системы.

. Ввести «циклический префикс» (cyclic prefix), который прибавляется к
каждому модулированному сигналу. Конечно число символов в таком префиксе
должно быть значительно меньше N. Корректор осуществляет поиск на наличие
данного префикса и, при наличии ISI предполагается, что интерференция
распространится не далее данного префикса. Поскольку циклический префикс
удаляется в приемнике, возможная ISI также удаляется до начала процесса
демодуляции с помощью БПФ. Данный метод снижает
сложность аппаратной реализации, и вместе с тем позволяет достигнуть
высокой эффективности. Например 5% избыточность привносимая префиксом,
является небольшой.
При использовании DMT количество бит данных, передаваемых по каждому
подканалу может варьироваться в зависимости от уровня сигнала и шума в
данном подканале. Это не только позволяет максимизировать
производительность для каждой конкретной линии, но также
позволяет уменьшить влияние таких эффектов как переходные помехи или RFI
(смотри рисунок ).

Ход работы:

DMT Modulator
У нас в программе используются 4 блока Modulator bank(в котором реализуется КAM модуляция):
У нас в каждом блоке происходит 4 КAM модуляции
Таким образом мы разбиваем канал на 16 подканалов.
Потом с помощью блока Vert Cat мы из 16 подканалов преобразуем в 1 последовательный вектор состоящий из 16 элементов.
Потом мы добавляем к нашим 16 символам еще 16 для помехоустойчивости( они образуются из наших 16 символов путем обратного порядка следования элементов, переменны знака на противоположный мнимой части и замены 1 элемента на 0)т.е.мы сдвигаем частоту.
Данный вектор из 32 элементов подается на вход блок инверсного быстрого преобразования Фурье. А дальше отправляются в канал.

DMT Demodulator
Полученные данные идут на блок быстрого преобразования Фурье.
Потом мы отбрасываем 16 последних символов предназначенных для помехозащищенности в канале. А потом данные идут на 4 блока Demodulator Bank, где происходит 16 КАМ демодуляций. Далее биты собираются в 1 вектор.

Распределение бит по частотным подканалам при использовании DMT
У нас в программе зависит от вектора b который характеризует количество бит передаваемых для каждого подканала.
Зависимость данных(битов) передаваемых по подканалам от выбранного нами вектора b:

№ подканала 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
b 1 1 3 3 4 4 5 6 7 5 3 3 2 2 1 1
date 1 1 3 3 4 4 5 6 7 5 3 3 2 2 1 1

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

2005-12-24 11:09:32

Destroyer_

Well done, my friend, I sense your heart is true.
You now have earned the right to your next clue:
The Mona Lisa's dwelling once housed kings.
A lavish Paris palace with three wings.
One wing is Sully... one is Richelieu.
Please name the third (I've mentioned only two).

2005-12-25 07:30:29

Destroyer_

P.S. Не дате заглохнуть прикольной теме!

2005-12-25 07:31:53

GEOhunter

[07:04] Ваши Оруженосцы складывают инструмент... Они грязные и усталые и ... ничего не нашли...