0000000000289962
AUTHOR
Rihards Opmanis
Hierarhisku grafu zīmēšana ar ierobežojumiem
Darbā tiek apskatīta grafu hierarhiska zīmēšana ar ierobežojumiem un šo ierobežojumu iekļaušana hierarhiskā grafu zīmēšanas stila realizācijas metodēs. Darbs veltīts grafu zīmēšanas mērķim – attēlot grafu uzskatāmā, viegli uztveramā formā tā, lai grafa struktūra būtu viegli saprotama un attēlotu svarīgākās grafa īpašības. Darbā uzmanība pievērsta vienam no populārākajiem grafu izvietošanas stiliem – hierarhiskajam stilam, kurā virsotnes tiek novietotas horizontālos slāņos. Papildus ņemam vērā, ka ne vienmēr informāciju ir iespējams reprezentēt ar tīras grafu struktūras palīdzību, tāpēc lietotājam var būt nepieciešams definēt kādus īpašus ierobežojumus, kuru rezultātā iegūtais grafa attēls p…
Integer Complexity: Experimental and Analytical Results
We consider representing of natural numbers by arithmetical expressions using ones, addition, multiplication and parentheses. The (integer) complexity of n -- denoted by ||n|| -- is defined as the number of ones in the shortest expressions representing n. We arrive here very soon at the problems that are easy to formulate, but (it seems) extremely hard to solve. In this paper we represent our attempts to explore the field by means of experimental mathematics. Having computed the values of ||n|| up to 10^12 we present our observations. One of them (if true) implies that there is an infinite number of Sophie Germain primes, and even that there is an infinite number of Cunningham chains of len…
Integer Complexity: Experimental and Analytical Results II
We consider representing of natural numbers by expressions using 1's, addition, multiplication and parentheses. $\left\| n \right\|$ denotes the minimum number of 1's in the expressions representing $n$. The logarithmic complexity $\left\| n \right\|_{\log}$ is defined as $\left\| n \right\|/{\log_3 n}$. The values of $\left\| n \right\|_{\log}$ are located in the segment $[3, 4.755]$, but almost nothing is known with certainty about the structure of this "spectrum" (are the values dense somewhere in the segment etc.). We establish a connection between this problem and another difficult problem: the seemingly "almost random" behaviour of digits in the base 3 representations of the numbers $…
Determinēta vaicājoša algoritma sarežģītība un kombinatoriskas konstrukcijas
Šī darba ietvaros tiks aplūkotas Būla funkcijas un to, cik funkcijas argumentu vērtības jāzina sliktākajā gadījumā, lai varētu noteikt funkcijas vērtību. Tiek aplūkotas funkcijas, kam varētu uzbūvēt kvantu vaicājošo algoritmu, kas būtu ievērojami labāks par determinēto vaicājošo algoritmu. Tā kā viens no kvantu vaicājošo algoritmu sarežģītības apakšējiem novērtējumiem ir funkciju reprezentējošā polinoma pakāpe, tad darbā apskatītas funkcijas, kam raksturojošā polinoma pakāpe ir mazāka par determinētā vaicājošā algoritma sarežģītību. Darbā ir apkopotas atsevišķas iepriekš zināmas funkcijas ar šādām īpašībām. Darbā ir pētītas un vispārinātas jau zināmo funkciju īpašības ar mērķi izveidot funk…
Integer Complexity: Experimental and Analytical Results II
We consider representing natural numbers by expressions using only 1’s, addition, multiplication and parentheses. Let \( \left\| n \right\| \) denote the minimum number of 1’s in the expressions representing \(n\). The logarithmic complexity \( \left\| n \right\| _{\log } \) is defined to be \({ \left\| n \right\| }/{\log _3 n}\). The values of \( \left\| n \right\| _{\log } \) are located in the segment \([3, 4.755]\), but almost nothing is known with certainty about the structure of this “spectrum” (are the values dense somewhere in the segment?, etc.). We establish a connection between this problem and another difficult problem: the seemingly “almost random” behaviour of digits in the ba…