ISSN 0351-6652 Letnik 22 (1994/1995) Številka 2 Strani 80-83 Franc Savnik: MNOŽICE IZ RAČUNALNIKA Ključne besede: matematika, kombinatorika, računalništvo, naravna števila, podmnožice. Elektronska verzija: http://www.presek.si/22/1216-Savnik.pdf © 1994 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo RRCUI1RU1ISW0 MNOŽICE IZ RAČUNALNIKA Na stikih med raznorodnimi vedami se že od nekdaj dogajajo posebno zanimive stvari. To velja tudi za znanosti, ki mejijo na matematiko; mednje tradicionalno uvrščajo astronomijo, fiziko in tehniko. V zadnjih nekaj desetletjih pa so začeli matematične metode uporabljati tudi v kemiji, biologiji, jezikoslovju, sociologiji in v številnih drugih znanostih, za katere je pred tem veljalo mnenje, da z matematiko nimajo nobene zveze. Precej zaslug za vstop matematike kot pomožne vede v te znanstvene panoge ima kombinatorika, o kateri zgodovina matematike poroča, da ima svoje korenine med ugankami in razvedrilno matematiko, v raznih igrah (tudi tistih za denar), v začetkih verjetnostnega računa in da je nasploh dolgo životarila na meji med znanostjo in razvedrilom Dandanes pravimo, da se kombinatorika ukvarja z vprašanji, ki so povezana z razmeščanjem elementov končnih množic. Njene rezultate izdatno uporabljajo tudi v računalništvu, saj so kombinatorični algoritmi podlaga Številnim računalniškim programom. V sestavku se bomo dotaknili predstavitve dane končne množice v računalniku in si ogledali dva postopka za oblikovanje pod-množic množice prvih n naravnih števil V računalniku Imejmo naravno število n in označimo z !Nn množico vseh naravnih Števil od 1 do n. Vprašamo se: Kako predstaviti v računalniku poljubno podmnožico množice IN„? Ena izmed možnosti je. da za vsako naravno število od 1 do n preverimo, ali pripada množici 5. Odgovor Da označimo z 1. odgovor Ne pa z 0 Odgovore zapišemo po vrsti z desne proti levi; tako dobimo za vsako podmnožico S množice ll\ln natanko doiočeno zaporedje enic in ničel. Zgled: /1 = 8, Ms = {1,2,3,4,5.6.7,8}, 5= {1,2,3,6}. Množici S ustreza zaporedje odgovorov 00100111. Mimogrede omenimo, da turbo pascal namenja takšni predstavitvi množice največ 32 krat 8 bitov in s tem omogoča uporabo osnovne množice, ki ima največ 256 elementov. O O 0 O Nabor ničel in enic, ki smo jih prirediti množici S, lahko razumemo kot dvojlški zapis števila; imenujmo ga število množice 5 in ga označimo s S tem je vsaki podmnožici množice INn prirejeno natanko določeno število in vsaki n-mestni dvojiški številki ustreza natanko določena podmnožica množice INn. Množica INn ima torej toliko pod množic, kot je števil 0,1,. .., 2" — 1, ki se jih da zapisati z n-mestnimi dvojiškimi številkami. Ker je takih Števil 2". lahko rečemo: Množica z n elementi ima natanko 7" podmnožic. Zgled: Podmnožice množice IN3 in njihova dvojiško zapisana števila: 5 0 {1} {2} {1,2} {3} {1,3} {2,3} {1,2,3} cr{5) 000 001 010 011 100 101 110 111 Iz računalnika Pri oblikovanju podmnožic množice INn si najprej izberemo prvo pod-množico — običajno je to prazna množica — in pravilo, ki vsaki pravi podmnožici 5 C INn priredi njeno neposredno naslednico S'. Za začetek oblikujmo postopek, ki izpiše vse podmnožice množice INn po njihovih naraščajočih številih. Naj bo 5 prava podmnožica množice !Nn in — 6: izpiši - množico(S); ponavljaj k — min(tN„ \ S); S - S U {k} \ {1,2.....Jk-1}: izpisi- množico(S); do izpolnitve pogoji S = "J: do tod. Oglejmo si še postopek, ki izpiše podmnožice množice ll\ln v leksiko-grafskem vrstnem redu. Ime izvira iz grških besed lexis (beseda) in grapheln (pisati) in označuje vrstni red, ki ga uporabljamo pri razvrščanju besed v slovarjih. Naj bosta Si = {¡\, h, ■ ■ •/'p) ¡n S 2 = {jlJl.- Jr} različni podmnožid dane množice INn, ki smo jima elemente zapisali po velikosti od najmanjšega do največjega. Za množico Si rečemo, da je leksikografsko pred množico S2, če je prazna ali če obstaja takšno naravno število k. da se množici Si in S2 ujemata v prvih k — 1 elementih in je < j Zgled: Podmnožice množice IN3 leksikografsko uredimo v zaporedje (fl, {1}. {1.2}, {1,2,3}, {1,3}, {2}, {2.3}, {3}. Naj bo S kaka prava podmnožica množice lNn in m njen največji element; če je množica S prazna, vzemimo m — 0. Podmnožice množice IN^, ki leksikografsko sledijo množici S, naredimo tako, da za vsak naravni it od m + 1 do n priključimo množici S število k in naredimo vse podmnožice množice INn, ki imajo množico S U {it} za svoj začetni del. Glede na to, da je prazna množica podmnožica vsake množice, je delo smiselno začeti z S — (i; uporabimo postopek Naredi..podmnožice-2(m, n: celi števili; S: množica); k : naravno Število; od tod izpiši.. množico(S); za vsak k od m + 1 do n ponovi Naredi_podmnoiice_2(fc. n, S U {fc}); do tod. Postopek sprožimo s klicem Naredi- po d množice-2(0, n, 0). Vabim vas, da poskusite napisati postopke, ki izpišejo podmnožice množice l!Mn še v kakem drugem vrstnem redu, na primer - po naraščajočem številu elementov, pri čemer so množice z enakim številom elementov razvrščene po svojih številkah ali pa leksikografsko, - tako, da se vsaki dve sosednji množici razlikujeta natanko v enem elementu, Franc Ssvnik