Keresés

Részletes keresés

Nautilus_ Creative Commons License 2011-01-25 14:53:33 81

"A komplexitáselmélet hasznos ugyan, de kb. csak annyira, mint számelméletben az alternatív logikai rendszerek."

 

Ezt a mondatot sajnos nem értem.

 

Azért örülök, hogy Szerinted az algoritmusok komplexitáselméletének is van valami hasznossága, mondjuk a P?=NP-problémának.

 

Nautilus_ Creative Commons License 2011-01-25 14:50:42 80

 

Abba meg végképp nem szertnék belemenni, hogy mit értünk formális nyelvészet alatt.

 

 

?? Hát, az elég nagy pech, ugyanis a topik címe "Formális nyelvek", én nyilván releváns, azaz ontopik arról beszélgetni, hogy mit is értünk formális nyelvek alatt. És milyen általános tételek vonatkoznak rájuk (Bar-Hillel-puffasztás, Myhill-Nerode, eldönthetetlenségi eredmények, és eldönthetőségiek).

 

Érdekes és lehetőleg minél általánosabb feladatosztályokra keresek konkrét algoritmusokat.

Te meg érdekes és minél általánosabb állításokra hozol konkrét bizonyításokat.

 

 

Ez a topik - ne haragudj, de - nem a tiéd. A fórum szabályzata nem ismeri azt a kitételt, hogy az alapító határozza meg a hozzászólások témáját, mert a témát a cím határozza meg; miért nem választottál más címet?

A topik éveken keresztül inaktív volt.

Másképp: ne haragudj, de abszurd, hogy ebben a topikban nem lehet beszélgetni a "Formális nyelvek" elméletéről, hanem csakis algoritmusokat beírni!

Még az sem tetszett Neked, hogy a CS-nyelvek PSPACE-teljességéről tájékoztattalak, mert az túl általános, pedig mi ontopik, ha nem ez, ráadásul az összes lehetséges algoritmusok szerkezetéről szól?

 

 

Továbbá a konkrét algoritmusok cikkek témái, nem fórumos hozzászólásoké, mivel ha adsz egy algoritmust, mindig kell bizonyítanod, hogy például lineáris idejű, logaritmikus tárigényű, tehát van értelme, stb., ami nagyon nehéz szinte mindig. Nem is nagyon írtak be ide algoritmusokat (ha jól emlékszem), legfeljebb linkeket tudok elképzelni publikációkhoz.

 

Na jó, hagyjuk.

 

A hozzászólás:
buki92 Creative Commons License 2011-01-25 09:45:53 79

[Akkor nekifutok mégegyszer:]

Érdekes és lehetőleg minél általánosabb feladatosztályokra keresek konkrét algoritmusokat.

Te meg érdekes és minél általánosabb állításokra hozol konkrét bizonyításokat.

 

Ez két teljesen különböző hozzáállás. Még akkor ha a vizsgált területben vannak is fogalmi átfedések.

Az algoritmusokról szóló tételek sem játszanak. A komplexitáselmélet hasznos ugyan, de kb. csak annyira, mint számelméletben az alternatív logikai rendszerek.

 

(Megjegyzem, hogy az algoritmusok keresése kb. olyan viszonyban van a programozással, mint a matematika a számolással. Csak persze jóval fejletlenebb terület.)

 

Abba meg végképp nem szertnék belemenni, hogy mit értünk formális nyelvészet alatt. A tételeidet meg a bizonyításaidat nyolvancanhat másik topikba írhatod; ide algoritmusokat please.

Előzmény:
Nautilus_ Creative Commons License 2011-01-25 00:14:55 77

Szerintem:

(1.) az érdekes lenne, ha 0-ás nyelvtanokhoz találsz olyan algoritmust, amely a mondatok nagy részére, elfogadható idő alatt talál levezetést.

(Mondjuk a 'mondatok nagy része' kifejezést te nem fogod érteni, mert azt mondod, hogy végtelen mondat van, ha ebből végesről nem dönti el, akkor ..., egyébként meg végtelen/végtelen. )

 (2.) az is érdekes lenne, ha tudnál mondani a 0-ás nyelvtanokhoz egy olyan normálformát, amiről egyszerű eldönteni, hogy készíthető-e hozzájuk hatékony algoritmus a tartalmazás probléma eldöntésére.

 

 

 

Ha jól értem, Te komplexitáselméleti problémákat kötsz össze formális nyelvelméleti problémákkal.

A megközelítésed alkalmazás-jellegű, ez nem baj, csak nem legyen kizárólagos. Túl biztos vagy magadban.

 

Persze, nagyon érdekes, ha igazoljuk (ZFC-ben:)), hogy P-ben van mondjuk egy kanonikusan PSPACE-beli eldöntési algoritmust használó nyelv. Ez erős eredmény. Vagy lineáris idejű algoritmussal oldható meg egy 0-adrendű grammatikával generált, de rekurzív nyelv szóproblémája.

 

Ugyanígy ez a témakör az approximáció, közelítő algoritmusok kérdése. Ez nem klasszikus formális nyelvelmélet.

 

Én nagyon szeretem a komplexitáselméletet, a P?=NP-problémát, és hasonlókat. Ezekre külön van topik.

 

Valójában MINDEN komplexitáselméleti probléma átfogalmazható nyelvészetivé, hiszen automaták különböző tárral, és időben döntenek el (ha eldöntenek) nyelveket.

 

Ez azonban már két matematikai ág, az algoritmikus komplexitáselmélet, és a formális nyelvészet összekapcsolódása.

 

A formális nyelvészet azonban ennél több.

 

Az, hogy létezik-e algoritmus az ABC problémára, nem érdekes

 

 

Ha tudod, hogy nem létezik algoritmus, keresel lineáris idejűt?:)

 

Az egzisztenciális bizonyítások alapvetően nem érdekesek

 

Jó, hogy ezt Te így tudod. Jó konstruktivista matematikus lennél: ott ugyanis egy egzisztencia-bizonyításhoz mindig van konstruktív is.:)

 

Ha kedveled azért, ha nem azért nyomj egy lájkot a Fórumért!