Tétel: Legyen S kompakt ponthalmaz a síkon és e egy irányított egyenes. Ekkor pontosan egy olyan f egyenes van, amely

• állása azonos e-ével,
• áthalad az adott ponthalmaz valamelyik elemén,
• az egész ponthalmaz az irányított egyenes jobb oldalára esõ zárt félsíkban van.

Megjegyzés: A fenti egyenest a ponthalmaz támaszegyenesének nevezzük.

Bizonyítás: Unicitás: Tegyük fel, hogy van egy f és egy f' azonos állású támaszegyenes. f-nek jobb oldalára esik P összes pontja. Speciálisan az is, amelyen f' áthalad. Így egész f' f jobb oldalán halad. f' és f különbözõ, így az egész f' az f egyenes szigoruan jobb oldalában halad. Ekkor f azon pontja ami P-nek is eleme az f' egyenesnek szigorú bal oldalára esik, ami ellentmond annak, hogy f' támaszegyenes.

Exisztencia: Legyen g egy olyan irányított egyenes, amelynek jobb oldalára esik teljes ponthalmazunk. Ilyen létezik, hiszen P korlátos, azaz egy körbe belefoglalható. Kör esetén a megfelelõ irányított egyenes létezik (szemlélet, vagy könnyû gondolatmenet alapján).

Definiáljuk a ponthalmaz elemein értelmezett függvényt, ami minden ponthoz hozzárendeli f-tõl vett távolságát. Ez egy kompakt halmazon értelmezett folytonos függvény, így felveszi minimumát. Legyen A egy olyan pont P-bõl, amelyre a fenti függvény értéke a minimális érték.

Legyen f az adott állású A-n áthaladó irányított egyenes. Ez ponthalmazunk támászegyenese lesz. Valóban, csak annak ellenõrzése okozhat problémát, hogy P az f irányított egyenes jobb oldalára esik. Ez abból következik, hogy f szigorú baloldalára esõ pontok a g jobb oldali pontjai közül pontosan azok, amelyek távolsága g-tõl szigorúan kisebb mint A távolsága g-tõl. Azaz A választása miatt ilyen pont nem lehet P-nek eleme.

Megjegyzés: Az exisztencia bizonyítás egyszerûsíthetõ. Nem szükséges olyan g-bõl kiindulni, amely jobb oldalára esik a teljes P halmaz. Tetszõleges g-t vehetünk,például az állást definiáló e egyenessel is dolgozhatunk. Ekkor azonban nem távolság függvényt kell néznünk, hanem elõjeles távolságot. Egy A pontnak egy e irányított egyenestõl vett elõjeles távolsága a következõ: Ha A az e jobb oldalára esik, akkor ez az A-nak távolsága e-tõl. Ha A az e bal oldalára esik, akkor ez az ellentetje az A-nak e-tõl vett távolságának.

A fenti geometriai tétel egy bizonyos egyenes létezését állítja. Ezek a támaszegyenesek geometriai szempontból fontosak. Így nem meglepõ, hogy konkrét esetekben a tétel által biztosított gyenest szeretnénk konkrétan meghatározni. Ezzel eljutottunk egy algoritmikus problémához:

Adott egy kompakt ponthalmaz a síkon és egy irámyított egyenes. Határozzuk meg az adott egyenessel azonos állású támaszegyenest.

Ami a számítógép számára adott, azaz amit közölnünk kell a géppel az úgynevezett input. Tehát az inputnak a számítógép számára érthetõnek kell lenni. Ez azt jelenti, hogy az input egy véges jelsorozat, amley elemei egy véges halmazból kerülnek ki (ez a szimbolumhalmazt ábc-nek nevezzük). Azt mondjuk, hogy a jelsorozat az input egy kódolása.

Példa: A természetes számok kódolására több lehetõség is van. A ``hatodik természetes szám" lehetséges kódolásai: öt, five, 5, 101_2, V, IIIII.

Amit az algoritmus (számítógép) kiszámít - az idegen szóval - az output. Az output is kódolva van, tehát mi egy jelsorozatot kapunk a géptõl, ami egy megállapodás (az ezt leíró függvény a kódolás) szerint értelmezhetõ számunkra.

Igazából az input és output fenti értelemben vett definíciója is része a számítási probléma matematikailag pontos definíciójának.

Példa: Legnagyobb köözs osztó problémája:
Input = két természetes szám, tízes számrendszerben felírva.
Output = egy természetes szám, tízes számrendszerben felírva, amely az inputban rejlõ két szám legnagyobb közös osztója.

Most nézzük mi is a mi problémánk pontosan megfogalmazva. A sík tetszõleges kompakt ponthalmazai túl sokan vannak (több mint megszámlálható a számosságuk), így nem azonosíthatók egy véges halmazból képezhetõ véges jelsorozatok halmazával. A továbbiakban mindig ha egy ponthalmazt kell közölnünk a géppel, akkor egy véges ponthalmazra gondolunk.

Tehát egy új (ebben a pillanatban egy nem teljesen jól leírt) számítási problémával állunk szemben: Adott véges ponthalmaz a síkon és egy irámyított egyenes. Határozzuk meg az adott egyenessel azonos állású támaszegyenest.

Hogy lehet egy ponthalmazt, vagy csak egy pontot kódolni?

Koordinátázással a pont kódja lehet egy valós számpár vagy egy komplex szám.

Példa: Euklideszi koordinátarendszer.

Példa: Polár koordinátarendszer.

Megjegyzés: A valós számoknak nem létezik véges kódolásuk (számossági okok). Mindig feltesszük, hogy a koordináták racionálisok, vagy egészek.

Ezekután elérkeztünk ahhoz a pillanathoz, hogy megfogalmazzuk a támaszegyenes meghatározásának problémáját.

Példa: Támaszegyenes meghatározása
Input = 2n darab természetes szám tízes számrendszerben felírva, kezdõ zárójel és csukózárójel, illetve vesszõ segítségével n darab számpárként vannak felsorolva (az input eddigi része n darab pontot írt le egy K koordinátarendszerben), illetve egy újabb számpár, amely az elõzõektõl (mondjuk) pontosvesszõvel van elválasztva (ez a számpár egy vektort, azaz egy irányítottegyenes állását írja le).
Output = Támaszegyenes egyenletének felírása a K koordinátarendszerben.

Példa: (1213,2312), (7765,4013), (26402,3640), (1326,4032), (8750,17501), (43750,1436), (7501,3946), (50134,6501), (3946,7509), (1347,50139), (47501,9347), (50913,4750), (9134,7509), (1347,5091), (34750,9143), (7509,12650), (42363,17520), (3465,7093), (4650,3146), (50134,67510), (37510,3567), (10345,4610), (3465,13065), (12065,71304), (6501,346510), (36501,3650), (134650,136501), 346501,34650), (13465,40367), (14650,8134), (65013,6501), (3465,9013), (46501,34650), 13650,13650), (13650,136501), (64501,36501), (36540,13675), (9015,9013), (46501,63450), (3165,40324), (6750,43275), (10347,50134), (6501,36501), (34650,13465),  (9013,46501), (3465,90136), (5031,46503), (14650,13624), (5032,64501), (3650,160561), (30561,9065), (9016,50136),  (5401,3265),  (4013,60561),  (3056,13056), (9017,52854), (2754,71257), (13751,43475), (13273,12751), (3751,35717); (35234,32542).

A szemlélet nem használható. Esetleg a miliméter papír sem segíthet. Arra kell gondolnunk milyen lépésekkel (jól leírható, ``számítógép számára is elmagyarázható '') lépéssorozat vezethet el válasz kiszámolásához.

Elérkeztünk az algoritmus elmélet egy újabb fontos alapfogalmához. Definiálnunk kellene az algoritmust. Ez egy nagyon nehéz (az 1930-as években elvégzett) feladat, amely több matematikus munkásságának lényeges része. A talán egyik legelfogadottab definíció Alan Turing által definiált úgy nevezett Turing-gép. Ennek definíciója nem szükséges számunkra.

A továbbiakban egy jóval egyszerûbb módszert követünk. A vizsgált problémától függõen definiálunk elemi lépéseket, és minden eljárásunkat ezekbõl az elemi lépésekbõl építjük fel.

Elõször is megjegyezzük, hogy minden általunk vizsgált problémában az input "szétszethetõ " lesz számokra. Számunkra az elemi lépések az inputban rejlõ számokkal és konstansokkal történõ alapmûveletek (összeadás, kivonás, szorzás, osztás) és összehasonlítások lesznek.

Hogyan írható le egy ilyen algoritmus? Amig számolunk egyszerû a dolgunk. Minden elemi lépésünket felsoroljuk. A leírás kezdete egy körbe írt START-tal kezdõdhet. Innen egy lefelé mutató nyíl vezethet az elsõ lépéshez, amirõl most feltesszük, hogy számítási lépés. Ezt egy téglalapba írjuk fel. Tehát ebbe a téglalapba felírjuk elsõ alapmûveletünket, az eredmény elnevezésével például y=x₁y₂. Majd egy nyíl vezet lefelé a következõ téglalapba, a következõ számítási lépeshez, például z=x₂y₁. És így tovább, például a következõ lépés lehet m=y-z. Az eljárás az összehasonlítási lépéseknél lesz bonyolultabb. Az ilyen lépéseket például rombuszokba írhatjuk. Ha például m elõjeléra van szükségünk,a kkor m és 0 összehasonlítását kell elvégeznünk, amit m?0 módon jelzünk. Az eredménytõl függõen eljárásunk szétágazik. A fentieknek megfelelõen kódolhatjuk eljárásunk további részét is. Az így kapott diagram egy faszerû strutúra lesz, amely szétágázasait az összehasonlító lépések adják, esetleges hosszú, szétágazás nélküli részein pedig számítások történnek. A fa alján - mondjuk alapjukon álló háromszögekben - az aktuális számítási ág végét jelezzük. A háromszög tartalma az output.

A fentiekben leírt számítási modell neve algbrai döntési fa. Egy konkrét input esetén az algebrai döntési fában egy a tetejérõl induló, aljában véget érõ, folyamatosan lefelé haladó utat járunk be. Ezt az adott inputhoz tartozó számítási útnak nevezzük. Különbözõ inputokhoz tartozhat különbözõ számítási út, de tartozhat azonos is. Persze azonos számítási út esetén az outputok szükségszerûen megegyeznek.

Megjegyzés: A fenti számítási modell leírását nem szakítottuk meg egy technikai kérdés tisztázásával. Ezt tettük annak reményében, hogy ezzel a tárgyalás átláthatóbb lesz. Most azonban kitérünk rá. Mi lesz egy összehasonlítás eredménye? Két lehetõség is van ennek tisztázására: az egyik szerint egy a?b összehasonlítás eredménye a-b elõjele, illetve 0 volta. Azaz egy összehasonlításnak három kimenetele lehetséges: a < b, a=b vagy a > b. Egy másik lehetõség szerint az összehasonlítás csak egy tesz ami eldönti, hogy a>b teljesül-e. Azaz az összehasonlításnak két kimenetele lehetséges a>b vagy a<=b. Ennek megfelelõen rombuszunkból kettõ vagy három felé ágazik szét a számítás. A két lehetõséget talán jobban megvilágítja a következõ sport hasonlat. A három kimeneteles összehasonlítás egy futball meccsre hasonlít: eredménye lehet döntetlen (=), illetve valamelyik csapat gyõzelme. Egy két kimeneteles összehasonlítás esetén gondolhatunk egy két személyes súlyemelõ versenyre (tudomásom szerint ilyen nem létezik). Kimentele lehet ``a nyer'' (a>b, a többet emelt), illetve ``b nyer'' (a<= b, b vagy többet emelt mint, vagy azonosat és könnyebb súlya révén nyert). Egy fontos szempont az algoritmus megtervezésénél, hogy két kimeneteles összehasonlítás esetén az a?b, illetve b?a kérdések nem ugyanazok. Három kimeneteles összehasonlítások esetén a két fajta kérdés közt nincs különbség.

Az alábiakban az alapfogalmakat az elsõ példa kidolgozásával világítjuk meg. Ebben a pillanatban az alapfogalmakról elegendõ, ha csak egy szemléletes képünk van. Ez és a további példák a szemléletes fogalmakat mélyítik el.

A példa kidolgozása két eset vizsgálatával történik. Az elsõ eset egyszerûbb, de a lényegre koncentrál. A lényeg már a támaszegyenes létezésének biazonyításánál kiderült: egy távolság függvényt kell minimalizálni. Esetünkben n szám közül kell kiválasztani a legkisebbet. A második eset tárgyalása csak alátámasztja korábbi megállapításunkat: az elsõ eset tartalmazza a lényeget.

Ekkor az adott ponthalmazunkhoz tartozó pontok x koordinátáik közül kell a minimálisat meghatározni. Természetesen ez a minimális érték csak egy szám (mondjuk a), de ebbõl a keersett támaszegyenes egyenlete könnyen felírható: ``x=a ''.

Igazából számunkra egy kissé módosított változat lesz hasznos: nem a minimális x koordináta értéket határozzuk meg, hanem egy olyan i indexet, hogy x_i értéke ez a minimum legyen. A geometriai interpretációja ennek a módosításnak, hogy nem a támaszegyenest határozzuk meg, hanem ponthalmazunk egy olyan pontját, ami ``megtámasztja '' egyenesünket.

A módosítás új kérdéseket vet fel. Ha a minimum nem csak egy x koordinátánál vevõdik fel, akkor mi legyen az output? Kérdésünkre több válasz is adható.

• Egyik lehetõség, hogy mindegy, csak a válasz korrekt legyen. Ez a legszabadabb megoldás számunkra tökéletesen elegendõ. Ezen megoldás esetén a feladat nem is egy függvény. Bizonyos inputokhoz egy többelemû megoldáshalmaz tartozik, amely egy tetszõleges elemét kell kiválasztanunk. Maga a feladat kitûzése nemdeterminisztikus.
• Más helyzetekben azonban szükségünk lehet többre is, például az összes olyan index halmazára, amelyre x_i minimális az összes x koordináta között.
• Lehet, hogy egyértelmûvé kell tennünk a megoldást egy ``döntetlen feloldó '' szabállyal. Erre egy lehetõség, hogy a minimumok koz;ül a legkisebb indexût határozzuk meg.
• Egy másik (a geometriai környezetben gyakran sokkal természetesebb) döntetlen feloldó szabály alapulhat az y koordinátákra. Az output a minimális számok köül legyen az, amelyikhez tartozó y koordináta minimális (vagy esetleg maximális).

Az olvasót arra kérjük, hogy a továbbiakban gondoljon a legszabadabb probléma kitûzésre. Ha azonban ezt jól átlátja akkor gondolja végig mit kell tennie az ``igényesebb'' output kiszámításához. Mi egy megjegyzésben térünk vissza erre a kérdésre.

Probléma: Adott n valós szám. Melyik (az egyik) minimális közülük?

Megjegyzés: Az eredmény csak az input elemei közötti rendezésen múlik. Összehasonlításokkal megoldható a probléma.

Definíció: Döntési fa fogalma: Az algebrai döntési fa fogalmának egy speciális esete: az elemi lépések között csak az összehasonlítás szerepel. Természetesen tisztázni kell, hogy az összehasonlítások két kimenetelûek vagy három kimenetelûek. Mi a szegényebb modellt vizsgáljuk, azaz két kimenetelû összehasonlításokat engedünk meg.

Megjegyzés: Analógia egy mérési feladattal. Analógia egy teniszversennyel.

Példa: n=4 eset. A megfelelõ döntési fa lerajzolása.

Lemma: n-1 összehasonlítással megoldható a probléma.

Megjegyzés: Az algoritmus terevezésénél nagyon nagy szabadsági fokunk van: Csak arra kell ügyelnünk, hogy egyik összehasonlításnál se szerepeljen ``vesztes'' elem.

Lemma: n-1-nél kevesebb összehasonlítással nem oldható meg a probléma.

1. Bizonyítás: Tegyük fel, hogy n-2 összehasonlítást végzünk és tudjuk az eredményt. Definiálunk egy gráfot: csúcsok az input számai, élek az összehasonlított párok. Ismert, hogy egy n pontú n-2 élû gráf nem lehet összefüggõ. A legnagyobb elemként az algoritmus által kihirdetett elem valamelyik komponensbõl jön, a másik komponenssel nincs összehasonlítva. Ellentmondás.

2. Bizonyítás: n-2 mérközés: n-2 vesztes. Azaz hatékony verseny végén lenne legalább két veretlen versenyzõ is. A versenyeredmény nem lehet fair.

Megjegyzés: A maximum meghatározás történhet duális módon.

Megjegyzés: Mi van, ha a minimális indexû minimális értékû x_i-t keressük. Ugyan ez a megoldás mûködik, de az összehasonlítások feltvésénél erre figyelnünk kell. Ha az összes minimális értékû x koordináta indexét megszeretnénk határozni, akkor egy kicsit bonyolultabb a helyzet. három kimenetelû összehasonlítások esetén tehetjük azt, hogy ***

• 1. lépés: Az adott pontok koordinátáit kódoljuk át egy új K' koordináta rendszerbe.
• 2. lépés: A korábbi algoritmus. Outputja a keresett támaszegyenes, de egyenlete az új koordináta rendszerben van felírva.
• 3. lépés: Az eredeti koordináta rendszerre való visszatérés.

• Eltolás.
• Elforgatás egy konkrét példán keresztül.

Az elsõ bevezetõ példa általános esetének analízise.

Definíció: Az f és g a természetes számokon értelmezett nem negatív függvények. g= O(f), ha van olyan c szám, hogy g(n)< c. f(n) teljesül elég nagy n-re.