Zasadazero-jedynkowa
Siecisortuj¡ce
Siecibitoniczne
Sie¢MergeSort
Algorytmy Równoległe i Rozproszone
Cz¦±¢ II - Sieci porównuj¡ce
Stronagłówna
Łukasz Kuszner
pokój 209, WETI
kuszner@kaims.pl
Stronatytułowa
JJ
II
J
I
Oficjalna strona wykładu
Wykład 15 godzin, Projekt 15 godzin
Strona
1
z
22
2011
Powrót
FullScreen
Zamknij
Koniec
Sieciporównuj¡ce
Zasadazero-jedynkowa
Siecisortuj¡ce
Siecibitoniczne
Sie¢MergeSort
1.Sieciporównuj¡ce
Stronagłówna
Sie¢ porównuj¡ca składa si¦ tylko z przewodów i komparatorów.
x
0
= min
{
x,y
}
Stronatytułowa
x
JJ II
y
0
= max
{
x,y
}
J I
y
Zakładamy, »e komparator działa w czasie
O
(1), to znaczy czas
pomi¦dzy pojawieniem si¦ danych na wej±ciu (na rysunku po le-
wej stronie), a pojawieniem si¦ wyników na wyj±ciu (na rysunku
po prawej stronie) jest stały. Przyjmujemy, »e sie¢ ma
n
wej±¢
a
1
,a
2
,...,a
n
i
n
wyj±¢
b
1
,b
2
,...,b
n
, a graf sieci jest acykliczny.
Strona
2
z
22
Powrót
FullScreen
Zamknij
Koniec
Sieciporównuj¡ce
Zasadazero-jedynkowa
Siecisortuj¡ce
Siecibitoniczne
Sie¢MergeSort
Stronagłówna
Stronatytułowa
Gł¦boko±¢sieci
JJ II
Wej±cie sieci ma gł¦boko±¢ 0. Je±li wej±cia komparatora maj¡ gł¦-
boko±¢
d
x
i
d
y
, to wyj±cie ma gł¦boko±¢ max(
d
x
,d
y
) + 1.
Gł¦bo-
ko±¢sieci
definiujemy jako najwi¦ksz¡ gł¦boko±¢ wyj±cia.
J I
Strona
3
z
22
Powrót
FullScreen
Zamknij
Koniec
Sieciporównuj¡ce
Zasadazero-jedynkowa
Siecisortuj¡ce
Siecibitoniczne
Sie¢MergeSort
Przykład
Stronagłówna
a
0
1
a
1
Stronatytułowa
a
0
2
a
2
JJ II
J I
a
0
3
a
3
Strona
4
z
22
a
0
4
a
4
Powrót
Powy»sza sie¢ porównuj¡ca ma gł¦boko±¢ 3.
FullScreen
Zamknij
Koniec
Sieciporównuj¡ce
Zasadazero-jedynkowa
Siecisortuj¡ce
Siecibitoniczne
Sie¢MergeSort
2.Zasadazero-jedynkowa
Lemat1
Je±lisie¢porównuj¡cadlaci¡guwej±cio-
wegoa
= (
a
1
,a
2
,...,a
n
)
wyznaczaci¡gwyj±ciowy
b
= (
b
1
,b
2
,...,b
n
)
,todladowolnejfunkcjiniemalej¡cejtasa-
masie¢zci¡giemwej±ciowymf
(
a
) = (
f
(
a
1
)
,f
(
a
2
)
,...,f
(
a
n
))
wyznaczaci¡gwyj±ciowyf
(
b
) = (
f
(
b
1
)
,f
(
b
2
)
,...,f
(
b
n
))
.
Stronagłówna
Stronatytułowa
JJ II
J I
wiczenie1
Przeprowad¹ pełny dowód lematu
1
.
Wskazówka1:
Rozwa» pojedynczy komparator. Z monoto-
niczno±ci
f
wynika, »e max
{
f
(
x
)
,f
(
y
)
}
=
f
(max
{
x,y
}
) i
min
{
f
(
x
)
,f
(
y
)
}
=
f
(min
{
x,y
}
)
Wskazówka2:
Zastosuj indukcj¦ na gł¦boko±¢ sieci.
Wskazówka3:
zob. Cormen str. 718
Strona
5
z
22
Powrót
FullScreen
Zamknij
Koniec