plu komenco

Enkonduko en la aŭtomatan daten-prilaboradon (2)

1 Hierarkiaj strukturoj

1.1 Hierarkioj kaj arboj

En la unua parto de la kurso "Enkonduko al la aŭtomata daten-prilaborado" (leciono 11) ni konatiĝis kun dosieraj sistemoj. Tiaj dosieraj sistemoj tre ofte estas aranĝitaj en hierarkio, kiu konsistas el du specoj de objektoj:

La fakto, ke dosierujo povas enhavi pliajn dosierujojn, ebligas la konstruadon de grandaj hierarkiaj strukturoj, kies partoj estas konstruitaj same kiel la tuto (dosierujo en dosierujo en dosierujo…).

La vorto "hierarkia" signifas, ke la elementoj de la strukturoj estas sur pluraj ŝtupoj, kaj iuj elementoj estas "superaj" al aliaj. Ekzemple dosierujo estas supera al ĉiuj dosier(uj)oj, kiujn ĝi enhavas.

Hierarkioj ekzistas sur multaj kampoj. La malgranda ekzemplo el la antaŭa kurso eblas klarigi kelkajn aspektojn. Temas pri la (fantazia) hierarkio de dungitoj en entrepreno, prezentata en la formo de arbo, foje nomata struktur-bildo:

Oni rimarkas, ke en informadiko la arboj kreskas malsupren! Arbo estas ĝenerala formo por reprezenti hierarkion; oni povas diri, ke (en informadiko) arbo kaj hierarkio estas la sama afero: Ĉiuj hierarkioj estas reprezenteblaj kiel arboj, kaj ĉiuj arboj reprezentas hierarkion. La ekzempla stukturo montras kelkajn ĝeneralajn ecojn de hierarkioj:

1.2 Rikuro

Ni vidis, ke la priskribo (aŭ difino) de dosierujoj mem uzis la vorton "dosierujo": Dosierujo povas enhavi dosierujojn. Tiaj strukturoj, kies partoj sekvas la samajn regulojn kiel la tuto, nomiĝas rikuraj. La priskribo de "dosierujo" estas rikura priskribo", ĉar ĝi mem uzas la (priskribatan) vorton "dosierujo".

Rikuro estas tre grava principo en informadiko, ĉar ĝi permesas redukti strukturojn al pli simplaj strukturoj. Se, ekzemple, oni diras, ke arbo konsistas el radiko, de kiu povas "dependi" aliaj arboj, oni difinis arbon per arboj, sed tiuj sub-arboj estas malpli grandaj, do pli simplaj.

Tiaj rikuraj difinoj utilas ĉe la prilaborado de strukturoj. Ekzemple oni povas utiligi la rikuran difinon de arbo por nombri la elementojn (verticojn) de arbo laŭ jenaj reguloj:

Tiuj reguloj funkcias, ĉar la nombrataj arboj iĝas pli kaj pli malgrandaj; kiam oni alvenas ĉe la folioj, ili konsistas nur el unu vertico, kaj eblas apliki la unuan regulon. Ĉiu sistemo de reguloj bezonas almenaŭ unu ne-rikuran regulon; alie la rikuro ne povus finiĝi.

La principo de rikuro estas konata ankaŭ en matematiko, kiu difinas rikurajn funkciojn. Konata ekzemplo estas la faktorialo, funkcio ofte esprimata per krisigno (!) kaj neformale difinata per tri punktoj:

n! = 1 · 2 · 3 · … (n−1) · n

Oni facile kalkulas, ke 1!=1, 2!=2, 3!=6, 4!=24 ktp.; sed la tri punktoj ne estas ekzakta esprimilo. Rikura difino de la faktorialo estas jena:


Specimenaj demandoj