Struktuurisemiootika: erinevus redaktsioonide vahel

Eemaldatud sisu Lisatud sisu

Reasisene

Redaktsioon: 28. veebruar 2012, kell 21:34

Struktuurisemiootika (inglise keeles semiotics of the structure) on uurimissuund graafiteooria ja semiootika piirimail. See kujutab endast praktilist moodust struktuuri ja selle omaduste semiootiliseks modelleerimiseks (inglise keeles ka computational semiotic) ^[1].

Graafe on mitmesuguste kaudsete invariantide (polünoomide, [[spekter|spektrite jt) baasil esitatud nö kanoonilisel kujul ^[2]. Paraku ei sisalda niisugused esitused teavet graafi struktuuri ja selle sümmeetriaomaduste kohta. Graafi esitamisel tema automorfismide rühma põhjal tekib keerukama struktuuri puhul palju küsitavusi.

Selgitus

Struktuuri all mõistetakse siin selle üldist, abstraktset tähendust kui elementidevahelist seostust või organiseerimisvormi ^[3] ^[4]. Graafi struktuur on selle tippude ja tipupaaride omadus olla graafis invariantselt seostatud, st organiseeritud mingil kindlal viisil – st struktuuri üldise tähenduse kujutamine graafidel. Graafi struktuur on isomorfsete graafide klassi täielik invariant.

Struktuuri ja invariandi mõisted on lihtsalt ja piltlikult selgitatavad Rubiku kuubiku põhjal.

Kommentaarid Rubiku kuubiku elementide kohta: a) Rubiku kuubiku igal tahul on üks element keskel, neli elementi servades ja neli elementi nurkades. b) Kihti pöörates elementide "positsioonid" ei muutu, need jäävad invariantseks. c) Seega moodustavad kuubiku 6 elementi „keskpositsiooni“, 24 elementi „nurkpositsiooni“ ja 24 elementi „servpositsiooni“. d) Rubiku kuubik on esitatav struktuuri säilitava graafina millel on kolm tipupositsiooni. e) Elementide "positsioonid" langevad kokku rühma AutG orbiitidega.

Lähteprintsiip

Lähtugem hüpoteetilisest kuid töötavast põhimõttest, graafi G struktuur S on identifitseeritav (mõõdetav) tribuut, $\,S={\mathfrak {F}}(G)$ , ning on modelleeritav tema „elementaarosakeste“, st tipupaaride identifitseerimise ehk märgistamise teel ^[5].

Teostus

Vastav algoritm ^[6] rajaneb lokaalsetel invariantidel ehk märkidel. See tuvastab: a) iga naabertippude paari jaoks selle kuuluvuse vöösse (vööde parve või oksa) ning selle suuruse +d; b) iga mitte-naabertippude paari jaoks nendevahelise kauguse –d ja vastava ahela (või ahelate parve; c) mõlemal juhul ka vastavat vööd või ahelat moodustavate tippude arv n ja servade arv m.

Saadud invariant-nelikute, paari- ehk binaarmärkide d.n.m. korrastatud (dekomponeeritud) süsteem on semiootiline mudel S, kui struktuuri kirjeldus.

Struktuuri uurimine tähendab selle mudeli S uurimist. Erinevate struktuuride arv võrdub mitteisomorfsete graafide arvuga. Struktuuride ekvivalentsuse tuvastamine kujutab endast vastavate mudelite ekvivalentsuse lihtsat fikseerimist.

Structural equivalence — Näide 2. Struktuuride ekvivalentsus ja graafide isomorfsus.

Kommentaarid näitele 2: a) Erinevad graafid omavad siin ekvivalentseid semiootilisi mudeleid, st et nende struktuurid on ekvivalentsed ja vastavad graafid on isomorfsed. b) Semiootiline mudel on tuvastanud kolm tipupositsiooni (-orbiiti) ja viis tipupaari orbiiti, sh kaks „mitteserva orbiiti“ c) Vastavused struktuuride vahel avalduvad tipupaari-orbiitide tasemel. d) Binaarmärgid tuvastavad iga tipupaari puhul tema "seisundi" struktuuris, näiteks E: +3.6.10 tähendab: "see tipupaar kuulub rohkem kui ühte vösse pikkusega d=4". e) Üldjuhul on struktuur tuvastatav oma lähte binaarmärkide tasemel kuid teatud sümmeetriliste graafide puhul peab kasutama täpsustatud binaarmärke.

Struktuurne ekvivalentsus on isomorfism tipupaari orbiitide tasemel. See on tuvastav vastavate mudelite lihtsa võrdlemise teel. Erinevate struktuuride arv võrdub graafide erinevate isomorfismiklasside arvuga. Semiootiline mudel S esitab selle klassi graafide ühist struktuuri. Graafide isomorfismi tuvastamine ei tähenda veel struktuuri tuvastamist, see kujutab endast vaid nende ekvivalentsuse kindlaksmääramist.

Struktuuri olulisemaid omadusi on sümmeetria. Sümmeetria on graafi tippude ja tipupaaride omadus jaotuda orbiitideks, st ekvivalentsus- või transitiivsusklassideks. Sümmeetriaomadused, st orbiidid (positsioonid) on märgimaatriksis äratuntavad kui binaarmärkide ekvivalentsusklassid. Äratuntavad on nii tipu- kui ka tipupaari orbiidid (positsioonid), sh viimase puhul serva- ja "mitteserva"' orbiidid. See lihtne moodus asendab ja katab nende tavapärast käsitlemist automorfismirühmade AutG abil ^[7].

Orbiitidel on oluline rolli graafi struktuuri uurimisel. On fikseeritud seaduspärasusi sümmeetriaomaduste ja tugevregulaarsuse vahel ^[8]. Sümmeetriatunnuste (graafi orbiitide arvu ja nende võimsuste) baasil on välja töötatud sümmeetriaomaduste klassifikatsioon. Esitatakse moodus sümmeetria mõõtmiseks. Ka asümmeetria on sümmeetriaomadus.

Igale tipupaari orbiidile (positsioonile) vastab üks positsioonistruktuur. Selle moodustavad orbiiti kuuluvad tipupaarid ning see kujutab endast vahendit struktuuri nö varjatud külgede uurimiseks. Näiteks, on selgunud, et Folkmani graafi üheks positsioonistruktuuriks on Peterseni graaf, jne.

Arendus

Igale tipupaari orbiidile (positsioonile) vastab ka üks naaberstruktuur, mis saadakse serva eemaldamisel või lisamisel orbiiti kuuluva tipupaari vahele. Need moodustavad n- tipuliste struktuuride konstruktiivse süsteemi ^[9]. See on seotud Ulami hüpoteesi ehk rekonstruktsiooniprobleemiga.

Rekonstrueerimisprobleemi puhul võib rääkida suurimatest alamgraafidest nii tippude G/v kui ka servade G/e eemaldamise mõttes ^[10]. Servade puhul saab rääkida ka väikseimatest ülemgraafidest.

Näide 3: Kuueelemendiliste struktuuride konstruktiivse süsteemi võre esimene pool.

Vanameistri W. T. Tutte järgi peaks rekonstruktsiooniprobleemi lahenduse otsingud baseeruma isomorfismiklassidel, mis loob täiesti uue pildi sellest probleemist. ^[11]

Isomorfismiklass kujutab endast isomorfsete graafide hulka. Isomorfsed graafid omavad üht ja sama struktuuri. See struktuur on kujutatav kanooniliselt vastava semiootilise mudeli S näol. Igal graafil (struktuuril) on oma suurimad alamgraafid (naaberstruktuurid) ja väikseimad ülemgraafid (naaberstruktuurid) mis saadakse vastavalt serva (seose) eemaldamisel või lisamisel. Kõik n-tipulised graafid (n-elemendilised struktuurid) moodustavad võre mille elementideks („tippudeks“) on struktuurid (vastavat isomorfismiklassi esindavad graafid) ja seosteks („servadeks“) struktuuridevahelised seosed.

Kommentaarid näitele: a) Iga graaf selles kuueelemendilise struktuuride võres esindab oma isomorfismiklassi ehk struktuuri, mis on esitet maatriksi S näol. b) Iga struktuur selles võres on mõne(de) teise (teiste) struktuuri(de) suurim alamstruktuur või väikseim ülemstruktuur. c) Iga struktuur on dekomponeeritav oma suurimateks alamstruktuurideks või komponeeritav oma väikseimateks ülemstruktuurideks. d) Iga struktuur on rekonstrueeritav (taastatav) oma nii oma suurimate alamstruktuuride kui ka väikseimate ülemstruktuuride baasil. e) Eelmises näites esitatud struktuur kannab siin järjekorranumbrit 22. f) Esitatud struktuuride täiendid asuvad sümmeetriliselt selle võre teises pooles. g) Kuueelemendiliste struktuuride (mitteisomorfsete graafide) arv on 156.

Kõik struktuurid (graafid) kuuluvad niisugustesse võredesse. Naaberstruktuurideks on siin nii suurimaid alam- kui ka väiksemaid ülemstruktuure. Rekonstruktsiooniprobleem seisneb vaid küsimuses: Kas erinevad struktuurid saavad omada täpselt ühesuguseid naaberstruktuure. Sellele probleemile üksikute graafiklasside pidi lähenemine ei ole mõttekas.

Kokkuvõte

Struktuur (ladina sõna structura – (sise)ehitus) on defineeritud kui süsteemi elementide (peamiselt püsivat) sidususe- või organiseerituse vormi. Aja jooksul on "struktuur" hargnenud eritähenduslikeks mõisteteks või on muutunud sisult ähmaseks käibesõnaks ^[12].

Struktuurisemiootika püüab mõistele "struktuur" omistada kindla tähenduse ja sisu: struktuur on isomorfsete graafide täielik invariant, st struktuuri invariantsete atribuutide süsteem, mis on esitatud semiootilise mudeli S ehk struktuuri teksti näol.

Tegemist on küllaltki delikaatse teemaga. Esiteks, tänapäeval puudub struktuuri mõiste kõiki rahuldav määratlus, teiseks, mõned matemaatikud ei aktsepteeri graafide struktuurisemiootilist käsitlemist ja kolmandaks, semiootikat on siin käsitletud üsna pinnapealselt.

Vaatamata sellele avab struktuurisemiootika graafide „varjatud külgi“, lahendab mõningaid klassikalisi probleeme mitteklassikalisel viisil ning püstitab ja lahendab uusi. Peamiseks probleemiks on struktuuri kanooniline esitamine ja struktuuride süsteemi konstrueerimine, mis on seotud taastatavuse ülesandega.

Struktuuri ja struktuurse ekvivalentsuse tuvastamise keerukus sõltub vaid tipupaaride arvust ja see ei ole võrreldav isomorfismi tuvastamise toimingutega. Struktuurisemiootika kujutab endast heuristiliste meetodite kompleksi struktuursete omaduste tundmaõppimiseks.

Viited

↑ Rieger, Burghard B. 1998. A Systems Theoretical View on Computational Semiotics. Modeling text understanding as meaning constitution by SCIPS, in: Proceedings of the Joint IEEE Conference on the Science and Technology of Intelligent Systems (ISIC/CIRA/ISAS-98), Piscataway, NJ (IEEE/Omnipress) 1998, pp. 840-845
↑ Y. Gurevich. From Invariants to Canonization. – The Bull. of Euro. Assoc. for Comp. Sci., No. 63, 1997
↑ Schmidt, Henrik, 1991. Philosophisches Wörterbuch. Stuttgard. ISBN 5250017940
↑ Новая философская энциклопедия. 2001, Москва. ISBN 9785244011159
↑ John-Tagore Tevet, 1990. Interpretations on some Graph Theoretical Problems, Estonian Acad. of Sciences.
↑ Tevet, John-Tagore. 2002. Isomorphism and Reconstruction of the Graphs: A constructive approach and development. S.E.R.R. Talinn.
↑ Tevet, John-Tagore, 2010. Graafide varjatud külgi. S.E.R.R,. Tallinn, ISBN 9789949213108
↑ Tevet, John-Tagore, 2007. Bisümmeetrilise struktuuri semiootika. S.E.R.R,. Tallinn
↑ Tevet, John-Tagore, 2007. System analysis of the graphs. Tallinn, online: (http://tallinn.ester.ee/record=b2297694~S1*est )
↑ Harary, Frank. 1964. On the reconstruction of a graph from a collection of subgraphs. – Theory of Graphs and its Applications - Proc. Sympos. Smolenice, 1963). Publ. House Czechoslovak Acad. Sci., Prague, 1964, pp. 47–52
↑ Tutte. W. T. 1998. Graph Theory As I Have Known It. Clarendon Press, Oxford.
↑ The Penguin Dictionary of Philosophy. 1997, London. ISBN 0140512500

Valik kirjandust

Rieger, Burghard B. 1998. A Systems Theoretical View on Computational Semiotics. Modeling text understanding as meaning constitution by SCIPS, in: Proceedings of the Joint IEEE Conference on the Science and Technology of Intelligent Systems (ISIC/CIRA/ISAS-98), Piscataway, NJ (IEEE/Omnipress) 1998, pp. 840-845.
Tevet, John-Tagore 1990. Interpretations on some Graph Theoretical Problems, Tallinn.
Tevet, John-Tagore, 2006. Graafide struktuurisemiootiline käsitlus. S.E.R.R., Tallinn, online: (http://tallinn.ester.ee/record=b2266686~S1*est )
Martin, Jüri and Tevet, John-Tagore, 2007. The Second Estonian Conference on Graphs and Applications. – Baltic Horizons, No 8 (107) (Special issue Dedicated to 270 years of Graph Theory),5-8, December 2007.
Tevet, John-Tagore, 2007. Valik graafide struktuure. S.E.R.R., Tallinn, ISBN 9789949153763, online: (http://tallinn.ester.ee/record=b2287285~S1*est )
Dharwadker, Ashay and Tevet, John-Tagore, 2009. The Graph Isomorphism Algorithm. S.E.R.R., Tallinn, ISBN 9781466394377, online: (http://www.dharwadker.org/tevet/isomorphism )
Tevet, John-Tagore, 2009. Graafi semiootiliste invariantide müsteerium. S.E.R.R., Tallinn, ISBN 9789949185108, online: (http://tallinn.ester.ee/record=b2490321~S1*est )
Tevet, John-Tagore, 2010. Semiotic Mystery of Canonical Presentation, Isomorphism and Reconstruction. – Baltic Horizons No 14 (111), pp 51-73.

Välislingid

[1] Rieger, Burghard B. 1998. A Systems Theoretical View on Computational Semiotics. Modeling text understanding as meaning constitution by SCIPS, in: Proceedings of the Joint IEEE Conference on the Science and Technology of Intelligent Systems (ISIC/CIRA/ISAS-98), Piscataway, NJ (IEEE/Omnipress) 1998, pp. 840-845

[2] Y. Gurevich. From Invariants to Canonization. – The Bull. of Euro. Assoc. for Comp. Sci., No. 63, 1997

[3] Schmidt, Henrik, 1991. Philosophisches Wörterbuch. Stuttgard. ISBN 5250017940

[4] Новая философская энциклопедия. 2001, Москва. ISBN 9785244011159

[5] John-Tagore Tevet, 1990. Interpretations on some Graph Theoretical Problems, Estonian Acad. of Sciences.

[6] Tevet, John-Tagore. 2002. Isomorphism and Reconstruction of the Graphs: A constructive approach and development. S.E.R.R. Talinn.

[7] Tevet, John-Tagore, 2010. Graafide varjatud külgi. S.E.R.R,. Tallinn, ISBN 9789949213108

[8] Tevet, John-Tagore, 2007. Bisümmeetrilise struktuuri semiootika. S.E.R.R,. Tallinn

[9] Tevet, John-Tagore, 2007. System analysis of the graphs. Tallinn, online: (http://tallinn.ester.ee/record=b2297694~S1*est )

[10] Harary, Frank. 1964. On the reconstruction of a graph from a collection of subgraphs. – Theory of Graphs and its Applications - Proc. Sympos. Smolenice, 1963). Publ. House Czechoslovak Acad. Sci., Prague, 1964, pp. 47–52

[11] Tutte. W. T. 1998. Graph Theory As I Have Known It. Clarendon Press, Oxford.

[12] The Penguin Dictionary of Philosophy. 1997, London. ISBN 0140512500

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

@@ 41. rida: / 41. rida: @@
 Rekonstrueerimisprobleemi puhul võib rääkida suurimatest alamgraafidest nii tippude G/v kui ka servade G/e eemaldamise mõttes <ref>  Harary, Frank. 1964. On the reconstruction of a graph from a collection of subgraphs. – Theory of Graphs and its Applications - ''Proc. Sympos. Smolenice, 1963). Publ. House Czechoslovak Acad. Sci., Prague, 1964, pp. 47–52'' </ref>. Servade puhul saab rääkida ka väikseimatest ülemgraafidest.
-[[File:Tevetlattice.jpg|thumb|Example: Kuueelemendiliste struktuuride konstruktiivse süsteemi võre esimene pool.]]
+[[File:Tevetlattice.jpg|thumb|Näide 3: Kuueelemendiliste struktuuride konstruktiivse süsteemi võre esimene pool.]]
 Vanameistri W. T. Tutte järgi peaks rekonstruktsiooniprobleemi lahenduse otsingud baseeruma ''isomorfismiklassidel'', mis loob täiesti uue pildi sellest probleemist. <ref> Tutte. W. T. 1998. Graph Theory As I Have Known It. ''Clarendon Press, Oxford.'' </ref>
@@ 49. rida: / 49. rida: @@
 Kommentaarid näitele: a) Iga graaf selles kuueelemendilise struktuuride võres esindab oma isomorfismiklassi ehk struktuuri, mis on esitet maatriksi '''''S''''' näol. b) Iga struktuur selles võres on mõne(de) teise (teiste) struktuuri(de) suurim alamstruktuur või väikseim ülemstruktuur. c) Iga struktuur on '''''dekomponeeritav''''' oma suurimateks alamstruktuurideks või '''''komponeeritav''''' oma väikseimateks ülemstruktuurideks. d) Iga struktuur on '''''rekonstrueeritav (taastatav)''''' oma nii oma suurimate alamstruktuuride kui ka väikseimate ülemstruktuuride baasil. e) Eelmises näites esitatud struktuur kannab siin järjekorranumbrit 22. f) Esitatud struktuuride täiendid asuvad sümmeetriliselt selle võre teises pooles. g) Kuueelemendiliste struktuuride (mitteisomorfsete graafide) arv on 156.
-Kõik struktuurid (graafid) kuuluvad niisugustesse võredesse. ''Naaberstruktuurideks'' on siin nii suurimaid alam- kui ka väiksemaid ülemstruktuure. Rekonstruktsiooniprobleem seisneb vaid küsimuses: Kas erinevad struktuurid saavad omada täpselt ühesuguseid naaberstruktuure. Sellele probleemile üksikute graafiklasside pidi lähenemine oleks absurdne.
+Kõik struktuurid (graafid) kuuluvad niisugustesse võredesse. ''Naaberstruktuurideks'' on siin nii suurimaid alam- kui ka väiksemaid ülemstruktuure. Rekonstruktsiooniprobleem seisneb vaid küsimuses: Kas erinevad struktuurid saavad omada täpselt ühesuguseid naaberstruktuure. Sellele probleemile üksikute graafiklasside pidi lähenemine ei ole mõttekas.
 ==Kokkuvõte==