(Cesarstwa i elektronika)(1).pdf

REKREACJE MATEMATYCZNE

Ian Stewart

Cesarstwa i elektronika

waliæmy si« kolorowaniem

map. Chociaý problem ten wy-

daje si« troch« niepowaýny, matematy-

ka, b«dca jego podstaw, jest ca¸kiem

uýyteczna. Mapy wiý si« z grafami Ð

diagramami, w ktrych wierzcho¸ki s

po¸czone liniami zwanymi kraw«dzia-

mi. Gruboæ grafu, poj«cie wprowadzo-

ne przy okazji zagadnienia cesarstw na

Ziemi i Ksi«ýycu, zosta¸a niedawno po-

ýytecznie wykorzystana w produkcji ob-

wodw scalonych. Zwizek ten przed-

stawi¸a Joan P. Hutchinson z Macalester

College w St. Paul (Minnesota) w arty-

kule wydrukowanym w czasopiæmie Ma-

thematics (vol. 66, nr 4, padziernik 1993).

Zastosowanie to odkryli naukowcy

z AT&T Bell Laboratories w Murray Hill

(New Jersey). Przypomnijmy, ýe graf

nazywamy p¸askim, gdy moýna go na-

rysowa na p¸aszczynie, tak by ýadne

jego dwie kraw«dzie si« nie przecina¸y.

Nast«pnym etapem jest graf gruboæci

dwa, ktrego kraw«dzie moýna podzie-

li na dwa zbiory w taki sposb, ýe kaý-

dy z nich jest p¸aski. Graf ma gruboæ

trzy, gdy jego kraw«dzie moýna pogru-

powa w trzy takie zbiory itd.

Graf o gruboæci dwa moýna sobie wy-

obrazi jako coæ w rodzaju ãkanapkiÓ.

Na jednej kromce rysujemy kraw«dzie

z pierwszego zbioru, tak by si« nie prze-

cina¸y, na drugiej zaæ Ð drugi zbir kra-

w«dzi, takýe bez ýadnych przeci«.

Wierzcho¸ki rozszerzone do linii piono-

wych tworz nadzienie. Graf, ktry po-

trzebuje t warstw chleba, ma gruboæ t .

Na pocztek wyobramy sobie obwd

elektryczny w postaci grafu. Jego w«z¸y

s elementami elektronicznymi, a kra-

w«dzie po¸czeniami elektrycznymi. Je-

æli uk¸ad scalony mamy zbudowa po

jednej stronie p¸ytki z obwodem druko-

wanym, to musi by on p¸aski, by unik-

n zwar. Wykorzystujc obie strony

p¸ytki Ð analogicznie do dwch kromek

chleba w kanapce Ð moýemy konstru-

owa grafy gruboæci dwa. Wraz z liczb

p¸ytek gruboæ grafu b«dzie ros¸a. Po-

dobne rozwaýania daje si« stosowa do

bardziej zaawansowanych technologicz-

nie obwodw scalonych, poniewaý w

bardzo duýej skali integracji (VLSI Ð ve-

ry large scale integration) obwody mu-

sz by budowane warstwami.

Typowa p¸ytka z obwodem druko-

wanym jest uk¸adem 100 na 100 dziur,

w ktrych mog by umieszczone kom-

ponenty elektroniczne po¸czone pozio-

mymi i pionowymi liniami; te moýna

z kolei pokry ãæcieýkamiÓ materia¸u

ãKANAPKAÓ przedstawia graf

gruboæci dwa: dwa p¸askie grafy,

ktrych wierzcho¸ki zosta¸y rozcigni«te

do pionowych linii.

przewodzcego. åcieýki pe¸ni funkcj«

drutu ¸czcego komponenty. Bardzo

waýnym problemem dla producentw

obwodw scalonych jest wykrywanie

p¸ytek ze zb«dnymi po¸czeniami Ð do-

datkowych kawa¸kw æcieýek, ktre ¸-

cz elektrycznie komponenty tam, gdzie

nie powinny one by po¸czone.

Ze wzgl«dw praktycznych produ-

cenci obwodw scalonych ¸cz kompo-

nenty na p¸ytce drukowanej w ãsieciÓ.

Sie jest zbiorem komponentw po¸czo-

nych æcieýkami tak, by nie zawiera¸y za-

mkni«tej p«tli. Problem, ktry nas inte-

resuje, to stwierdzenie, czy dwie rýne

sieci mog zosta przypadkowo zwarte.

Najprostszym sposobem jest sprawdze-

nie, czy wszystkie pary sieci s po¸czo-

ne. Moýna skonstruowa obwd biegn-

cy od jednej sieci do dodatniego bieguna

baterii i od ujemnego bieguna baterii po-

przez ýarwk« do drugiej sieci. Jeæli b«-

d one przypadkiem po¸czone, to po-

p¸ynie prd i ýarwka si« zapali.

Oczywiæcie w prawdziwych urzdze-

niach testujcych stosuje si« bardziej

skomplikowan elektronik«, jak cho-

by komputer sprz«ýony z robotem, kt-

ry automatycznie wyrzuca wadliwe

p¸ytki, ale podstaw jest w¸aænie ta idea.

K¸opotw przysparza fakt, ýe n sieci wy-

maga n ( n Ð 1)/2 prb Ð tyle ile jest par

sieci. Poniewaý zwykle jest 500 sieci,

oznacza to, ýe kaýda p¸ytka wymaga

125 tys. testw, a wi«c o wiele za duýo.

Stosujc poj«cie gruboæci grafu, moýe-

my bardzo szybko zmniejszy liczb« te-

stw do zaledwie 11. W rzeczywistoæci

odrobina pomys¸owoæci zredukuje t«

liczb« do jedynie czterech.

Punktem wyjæcia jest zamiana sche-

matu p¸ytki z obwodem drukowanym

+ Ð

PüYTKA Z OBWODEM DRUKOWANYM zawiera dziury (k¸ka) , w ktrych znajduj si«

komponenty (kwadraty) . Komponenty s po¸czone æcieýkami metalu w ãsieciÓ;

przyleg¸e sieci maj rýne kolory. Ale niepotrzebne æcieýki (czarne) mog powodowa b¸«dy,

¸czc przyleg¸e sieci. Jeæli przyczepimy ýarweczk« z bateri do obwodw testujcych

sie zielon i niebiesk, to zwarcie pozwoli na przep¸yw prdu i ýarweczka si« zaæwieci.

72 å WIAT N AUKI Listopad 1997

W poprzednim miesicu zajmo-

w graf, ktry zawiera informacje o zwar-

ciach. Nazwijmy go grafem sieci obwodu

scalonego. Poniewaý szukamy krtkich

spi« pomi«dzy rýnymi sieciami, to kaý-

dej sieci przypisujemy jeden w«ze¸.

Kraw«dzie tego grafu sieci reprezen-

tuj potencjalne, a nie rzeczywiste zwar-

cia (gdybyæmy bowiem wiedzieli, gdzie

te zwarcia s, nie musielibyæmy testowa

obwodu). Mwic æciælej, dwa w«z¸y gra-

fu sieci b«d po¸czone kraw«dzi, gdy

tylko odpowiadajce im sieci s ãprzyle-

g¸eÓ Ð co oznacza, ýe moýna je ¸czy po-

ziom lub pionow lini prost, ktra nie

przechodzi przez inne poærednie sieci.

Oczywiæcie zwarcie moýe teoretycznie

nastpi pomi«dzy dwoma nie przylega-

jcymi sieciami. Ale prawie wszystkie ta-

kie spi«cia musz takýe ¸czy przyleg¸e

sieci. Fabryczny robot zazwyczaj dwu-

krotnie przechodzi nad p¸ytk: raz robic

po¸czenia poziome, a drugi raz drukujc

pionowe. B¸«dy si« pojawiaj, gdy po¸o-

ýy on za duýo materia¸u przewodzce-

go, nieopatrznie ¸czc dwie sieci. Taki

b¸d nazywamy ãprodukcyjnymÓ. (S

takýe inne, znacznie rzadsze sposoby wy-

produkowania wadliwych p¸ytek, ale nie

b«dziemy ich tu rozwaýa.) Ta dodatko-

wa linia materia¸u przewodzcego moýe

biec przez kilka sieci, ale dwie z nich b«-

d przyleg¸e. Tak wi«c wystarczy rozwa-

ýy tylko przyleg¸e sieci.

Za¸oýy¸em wczeæniej, ýe graf p¸ytki

z obwodem drukowanym ma gruboæ

dwa, co odpowiada jej dwm stronom.

Z tych samych powodw graf sieci ma

gruboæ dwa. Ale w myæl twierdzenia

sformu¸owanego przez XIX-wiecznego

brytyjskiego matematyka PercyÕego Joh-

na Heawooda kaýdy graf gruboæci dwa

moýna pokolorowa 12 kolorami. Kaýde-

mu wi«c wierzcho¸kowi moýemy przy-

pisa jeden z dwunastu kolorw, tak by

wierzcho¸ki po¸czone kraw«dzi by¸y

rýnych barw. Moýemy teraz to poko-

lorowanie odnieæ do sieci uk¸adu sca-

lonego. A zatem kaýdej sieci przypo-

Wydawnictwo

proponuje:

Jak dzia¸aj witaminy i mikroelementy?

Czy moýna i naleýy bra je w tabletkach?

Czy ich nadmiar moýe zaszkodzi?

Czytelnik znajdzie w ksiýce odpowiedzi

na te i inne pytania, proponowane dawki,

opis zalecanej diety, a takýe ograniczenia

w stosowaniu i objawy niepoýdane.

Autorzy ksiýki bardzo rzetelnie opisuj

potwierdzone wynikami badaÄ

mechanizmy dzia¸ania witamin

i mikroelementw, jak rwnieý

omawiaj przypisywane,

a nie udowodnione korzyæci

ze stosowania tych sk¸adnikw.

W ksiýce podane s rwnieý polskie

nazwy preparatw i zalecane w Polsce

dzienne zapotrzebowanie na te sk¸adniki,

w zaleýnoæci od wieku i kondycji.

Autorami ãWitamin i mikroelementwÓ

s najlepsi lekarze amerykaÄscy,

ktrym patronuje Farmakopea Stanw

Zjednoczonych (USP) Ð organizacja

ustanawiajca standardy lekw

i preparatw odýywczych w USA.

l cena ok¸adkowa 9,90 z¸ l

cena w sprzedaýy wysy¸kowej 5,50 z¸ l

Earl Mindell

Autor s¸ynnej ãBiblii witaminÓ, dr Earl

Mindell, raz jeszcze doradza, jak ýy

i odýywia si« zdrowo. Przedstawia

100 sk¸adnikw pokarmowych, zi¸,

witamin i mikroelementw potrzebnych

cz¸owiekowi dla zachowania dobrej

formy, opisujc mechanizm ich dzia¸ania,

potencjalne korzyæci i ograniczenia

w stosowaniu. Szczeglne znaczenie

przywizuje do tych sk¸adnikw diety,

ktre mog w znaczcy sposb

przyczyni si« do obniýenia poziomu

cholesterolu oraz by przydatne

w profilaktyce przeciwnowotworowej.

Autor omawia rwnieý cz«ste

dolegliwoæci i schorzenia wieku

æredniego i starszego (m.in. chorob«

Alzheimera, choroby nowotworowe,

choroby zwyrodnieniowe staww)

i radzi, jak im zapobiega. Cho do

niektrych informacji naleýy podchodzi

z pewnym dystansem, na pewno

proponowane przez autora dieta

i styl ýycia pomog utrzyma si«

w dobrej formie i prowadzi

zdrowy tryb ýycia.

M üODOåC I

STO SKüADNIKîW POKARMOWYCH,

OD KTîRYCH ZALEûY

ZDROWIE

I DOBRE SAMOPOCZUCIE

GRAF SIECI obwodu scalonego

przedstawionego obok ma gruboæ dwa,

po jednej dla kaýdej strony p¸ytki.

Kaýda sie jest reprezentowana

przez wierzcho¸ek (w«ze¸);

przyleg¸e wierzcho¸ki s po¸czone

kraw«dziami Ð to potencjalne zwarcia.

l Cena ok¸adkowa 14,60 z¸ l

cena w sprzedaýy wysy¸kowej 10 z¸ l

Ksiýki moýna kupi w ksi«garniach lub zamwi w sprzedaýy wysy¸kowej:

listownie w Klubie Ksiýki Ksi«garni Krajowej, skrytka pocztowa 21, 02-600 Warszawa13;

telefonicznie pod numerami: 0-800-244-88 (po¸czenie bezp¸atne) oraz (0-22) 43-51-21 i 43-41-61.

Koszt wysy¸ki 3 z¸.

BIBLIA

AUTOR ãBIBLII WITAMINÓ

BIBLIA

M üODOåC I

+ Ð

¸czenia. Teraz dodajmy bramk« lub

prze¸cznik pomi«dzy obwodami testu-

jcymi 1 i 2. Sprawdmy dalej, czy ob-

wd testujcy 3 jest po¸czony z obwo-

dem utworzonym przez po¸czenie

obwodw 1 i 2. Jeæli tak, to jest on po¸-

czony z obwodem testujcym 1 lub 2.

W kaýdym przypadku jest to b¸d i od-

rzucamy t« p¸ytk«. Nast«pnie dodajmy

drug bramk« ¸czc obwd testujcy

3 z dwoma poprzednimi i sprawdmy

nasz p¸ytk« jak poprzednio. W ten spo-

sb wystarczy jedynie 11 testw.

Allen J. Schwenk z West Michigan

University w Kalamazoo zorientowa¸

si«, ýe liczb« testw moýna jeszcze bar-

dziej zredukowa. Zapiszmy liczby 1,

2, ..., 12 w systemie dwjkowym: 0001

aý do 1100. Ponumerujmy odpowiednio

nasze obwody testujce. Przygotujmy

ãsuperobwdÓ testujcy, ktry ¸czy

wszystkie obwody testujce zaczynaj-

ce si« od 0 oraz drugi ¸czcy wszystkie

obwody testujce zaczynajce si« od 1.

Sprawdmy teraz, czy te dwa super-

obwody s po¸czone; jeæli tak, to od-

rzucamy badany obwd scalony. Jeæli

nie, to konstruujemy dwa nowe super-

obwody ¸czce obwody testujce o tych

samych cyfrach na drugim miejscu ich

binarnego zapisu. Nast«pnie sprawdza-

my, czy s one po¸czone. To samo robi-

my dla trzecich i czwartych cyfr dwj-

kowego zapisu. I tyle. Sprawdzajc

zasadnoæ tego testu, pami«tajmy, ýe je-

æli dwa rýne obwody testujce s po¸-

OBWîD TESTUJCY ¸czy

wszystkie sieci danego koloru.

Umieszczajc ýarweczk« pomi«dzy

ý¸tym i niebieskim obwodem testujcym,

moýemy wykry zwarcie

pomi«dzy sieciami o tych kolorach.

BRAMKI lub prze¸czniki ¸cz

kolejno 12 obwodw testujcych,

zmniejszajc ca¸kowit liczb« testw

wykrywajcych zwarcia.

czone, to ich binarne zapisy rýni si«

co najmniej jedn cyfr, a wi«c jeden

z czterech testw wykryje b¸d.

Zmniejszenie liczby testw ze 125 tys.

do zaledwie czterech jest tym cenniejsze,

im wi«ksza jest produkcja, poniewaý wy-

maga budowy tych skomplikowanych

obwodw i superobwodw testujcych

tylko raz dla kaýdego typu p¸ytki.

W ubieg¸ym miesicu zacz«liæmy od

kolorowania map cesarstw ziemsko-ksi«-

ýycowych, a dziæ koÄczymy na oszcz«d-

nej metodzie testowania p¸ytek z obwo-

dami drukowanymi. To, co jest waýne w

matematyce, to nie szczeglna reali-

zacja jakiejæ idei, ale moýliwoæci, jakie

ona daje, gdy rozwijamy j sprytnie i z

wyobrani. T¸umaczyli

Zdzis¸aw Pogoda i Robert Wolak

rzdkowujemy jeden z dwunastu kolo-

rw w taki sposb, by sieci o tej samej

barwie nigdy do siebie nie przylega¸y.

Poniewaý poszukujemy zwar pomi«-

dzy przyleg¸ymi sieciami, to wiemy, ýe

moýemy si« ograniczy do spi« pomi«-

dzy sieciami o rýnych barwach. W tym

celu dla kaýdego z 12 kolorw konstru-

ujemy ãobwd testujcyÓ. Ta struktura

podobna do rozga¸«zieÄ drzewa zrobio-

na jest z materia¸u przewodzcego i ¸-

czy wszystkie sieci danego koloru.

Przypuæmy, ýe wybraliæmy dwa ko-

lory Ð niebieski i ý¸ty. Przyczepiamy na-

sze obwody testujce koloru niebieskie-

go i ý¸tego do p¸ytki z obwodem dru-

kowanym, uwaýajc, by ich nie po¸czy.

Nast«pnie pod¸czamy bateri« i ýar-

weczk« do naszych obwodw testuj-

cych i sprawdzamy, czy p¸ynie prd.

Jeæli obwd scalony zosta¸ wykona-

ny poprawnie, to nie pop¸ynie ýaden

prd, poniewaý niebieski obwd testu-

jcy ¸czy jedynie niebieskie sieci, ý¸ty

zaæ jedynie ý¸te sieci, a na p¸ytce z ob-

wodem drukowanym ýadna niebieska

sie nie powinna by po¸czona z sieci

ý¸t. Gdy jednak wyst«puje b¸d ãpro-

dukcyjnyÓ ¸czcy sie niebiesk z ý¸-

t, to prd pop¸ynie.

Zwrmy uwag«, ýe test nie wskaýe

nam, gdzie jest b¸d. Poniewaý odrzuca-

my wszystkie wadliwe p¸ytki z obwo-

dami drukowanymi (nie naprawiamy

ich), to nie musimy tego wiedzie. ûeby

znale b¸d produkcyjny, wystarczy

sprawdzi wszystkie pary obwodw te-

stujcych. Jest ich tylko 12, a zatem licz-

ba tych par wynosi 12 x 11/2 = 66. Za-

miast wi«c 125 tys. lub wi«kszej liczby

testw wystarczy przeprowadzi tylko

66 Ð a to oznacza juý post«p.

Moýemy jednak jeszcze bardziej upro-

æci operacj«. Sprawdmy obwody testu-

jce 1 i 2; odrzumy wszystkie p¸ytki

z obwodami drukowanymi majce po-

SPRZ¢ûENIE ZWROTNE

czerwiec 1997] omawialiæmy kla-

syczny problem w«drwki konia szacho-

wego. Solomon W. Golomb z Universi-

ty of Southern California napisa¸, ýe

udowodni¸ kilka wynikw na ten temat

w artykule ãOf Knights, Cooks, and the

Game of CheskersÓ opublikowanym

w Journal of Recreational Mathematics

(vol. 1, nr 3, ss. 130-138; lipiec 1968).

Praca ta zawiera m.in. twierdzenie przy-

pisywane Louisowi Psa Ð ýe szachow-

nica 4 x n nie dopuszcza zamkni«tej w«-

drwki skoczka po wszystkich polach,

oraz twierdzenie o istnieniu takiej drogi

na szachownicy 3 x 10.

Z kolei Andy Campbell z West Hart-

ford (Connecticut) przypomina problem

magicznej drogi konia. Jest to zamkni«-

ta droga na szachownicy 8 x 8 o nast«-

pujcej w¸asnoæci: jeæli kolejne po¸oýe-

nia skoczka oznaczymy numerami od 1

do 64, to liczby te utworz kwadrat ma-

giczny (tzn. sumujc osobno wszystkie

rz«dy, kolumny i przektne dostaniemy

te same wyniki). Nie udowodniono ani

istnienia, ani teý nieistnienia takiej dro-

gi, ale znanych jest kilka prawie ideal-

nych rozwizaÄ:

(a) droga skoczka, w przypadku ktrej

rz«dy i kolumny sumuj si« do 260, ale

nie przektne,

(b) magiczny kwadrat utworzony z po-

¸wek drogi skoczka (1Ð32 oraz 33Ð64),

z ktrych kaýda pokrywa po¸ow« sza-

chownicy,

74 å WIAT N AUKI Listopad 1997

K ilka miesi«cy temu [ åwiat Nauki ,

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: