Procedural Content Generation innebär att spelinnehåll automatiskt genereras för att dels både öka variationen i spel dels och minska arbetsbelastningen hos designers. Ett användningsområde för detta är rumbaserad bangenerering. Målet med detta  här arbetet är var att jämföra två algoritmer som gör just detta:; Binary Space Partitioning och Delaunay Triangulation. De kriterier som algoritmerna utvärderades på var tidseffektivitet, variation, likhet och möjligheten att nå alla rum. Resultatet visade att Binary Space Partitioning hade snabbare genereringstid samtidigt som Delaunay Triangulation gav utvecklaren mer valmöjligheter. Vilken algoritm som var att föredra ifall tidsaspekten inte bar mest tyngd blev helt en en mestadels subjektiv fråga där varje enskild utvecklares önskemål kommer påverka svaret. Ifall arbetet skulle fortsättas i framtiden skulle det vara intressant att utföra fler tester med flera olika mätvärden samt använda algoritmerna i ett spel och sedan påta låta spelare testare bedöma kvalitén hos banorna som genereras.

A common type of problems that exist in both industrial and scientific spaces are optimization problems. These problems can be found in among other things manufacturing, pathfinding, network routing and more. Because of the wide area of application, optimization is well a studied area. One solution to these types of problems is the Ant Colony Optimization algorithm that has been around since 1991 and has undergone a lot of developments over the years. This algorithm draws inspiration from real ant colonies and their procedure for foraging. However, a common criticism of this algorithm is its poor scalability. To tackle the scalability problem this thesis will combine the concept of binary space partitioning with the Ant Colony Optimization algorithm. The goal is to examine the algorithms convergence times and lengths of the paths produced. The results are measured in intervals by calculating the best possible path found at every interval. The findings showed that given an unlimited execution time the original Ant Colony Optimization algorithm produced shorter paths. But when a limit on execution time was introduced and the problem sizes grew the performance began to favor the partitioned versions. These findings could be useful in areas where complex optimization problems need to be solved within a limited timeframe. / <p>The presentation took place via an online conference call using the software "Zoom"</p>

The recent growth in wireless communications presents a new challenge to multimedia communications. Digital image transmission is a very common form of multimedia communication. Due to limited bandwidth and broadcast nature of the wireless medium, it is necessary to compress and encrypt images before they are sent. On the other hand, it is important to efficiently utilize the limited energy in wireless devices. In a wireless device, two major sources of energy consumption are energy used for computation and energy used for transmission. Computation energy can be reduced by minimizing the time spent on compression and encryption. Transmission energy can be reduced by sending a smaller image file that is obtained by compressing the original highest quality image. Image quality is often sacrificed in the compression process. Therefore, users should have the flexibility to control the image quality to determine whether such a tradeoff is acceptable. It is also desirable for users to have control over image quality in different areas of the image so that less important areas can be compressed more, while retaining the details in important areas. To reduce computations for encryption, a partial encryption scheme can be employed to encrypt only the critical parts of an image file, without sacrificing security. This thesis proposes a scalable and secure image representation scheme that allows users to select different image quality and security levels. The binary space partitioning (BSP) tree presentation is selected because this representation allows convenient compression and scalable encryption. The Advanced Encryption Standard (AES) is chosen as the encryption algorithm because it is fast and secure. Our experimental result shows that our new tree construction method and our pruning formula reduces execution time, hence computation energy, by about 90%. Our image quality prediction model accurately predicts image quality to within 2-3dB of the actual image PSNR.

The recent growth in wireless communications presents a new challenge to multimedia communications. Digital image transmission is a very common form of multimedia communication. Due to limited bandwidth and broadcast nature of the wireless medium, it is necessary to compress and encrypt images before they are sent. On the other hand, it is important to efficiently utilize the limited energy in wireless devices. In a wireless device, two major sources of energy consumption are energy used for computation and energy used for transmission. Computation energy can be reduced by minimizing the time spent on compression and encryption. Transmission energy can be reduced by sending a smaller image file that is obtained by compressing the original highest quality image. Image quality is often sacrificed in the compression process. Therefore, users should have the flexibility to control the image quality to determine whether such a tradeoff is acceptable. It is also desirable for users to have control over image quality in different areas of the image so that less important areas can be compressed more, while retaining the details in important areas. To reduce computations for encryption, a partial encryption scheme can be employed to encrypt only the critical parts of an image file, without sacrificing security. This thesis proposes a scalable and secure image representation scheme that allows users to select different image quality and security levels. The binary space partitioning (BSP) tree presentation is selected because this representation allows convenient compression and scalable encryption. The Advanced Encryption Standard (AES) is chosen as the encryption algorithm because it is fast and secure. Our experimental result shows that our new tree construction method and our pruning formula reduces execution time, hence computation energy, by about 90%. Our image quality prediction model accurately predicts image quality to within 2-3dB of the actual image PSNR.

The purpose of this thesis is to present methods for visibility determination and to design and implement an application to demonstrate visibility determination in a 3D maze.

The fuel consumption of a seagoing vessel is, through a combination of Box-Cox transforms and principal component analysis, reduced to a univariatefunction of the primary principle component with mean model error −3.2%and error standard deviation 10.3%. In the process, a Latin-hypercube-inspired space partitioning sampling technique is developed and successfully used to produce a representative sampleused in determining the regression coefficients. Finally, a formal optimisation problem for minimising the fuel use is described. The problem is derived from a parametrised expression for the fuel consumption, and has only 3, or 2 if simplified, free variables at each timestep. Some information has been redacted in order to comply with NDA restrictions. Most redactions are either names (of vessels or otherwise), units, andin some cases (especially on figures) quantities. / <p>Presentation was performed remotely using Zoom.</p>

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Es besteht der Wunsch nach Indikatoren, deren Signaturen dem chemischen Verständnis entsprechen. Die Suche nach chemischen Signaturen im Realraum ist unter anderem deshalb ein so fruchtbares Arbeitsfeld, weil trotz der Fülle von Indikatoren (die alle einen unterschiedlichen Aspekt der Bindung beleuchten) die Frage nach dem Abbild der chemischen Bindung im Realraum immer noch auf Antwort wartet. Ein Teil von Indikatoren zerlegt den Raum in Bereiche, in denen sich Elektronenpopulationen berechnen lassen. Die Güte dieser Realrauminidkatoren wird daher in der Regel danach beurteilt, ob sie den Gesamtraum in genau solche Teile zerlegen, in denen sich die nach dem Aufbauprinzip erwartete Elektronenpopulation findet: das heißt bei Atomen in sphärische Schalen; bei Molekülen und Festkörpern in Rümpfe, Bindungen und freie Elektronenpaare mit jeweils ganzen, dem Aufbauprinzip entsprechenden Elektronenzahlen. Neben dem Wunsch nach chemischen Signaturen kann man bei der Arbeit mit Realraumindikatoren auch andere Ergebnisse erzielen, wenn man die Indikatoren auf derselben Basis entwickelt, das heißt, wenn man sie vergleichbar macht. Ein Satz vergleichbarer Indikatoren ermöglicht die Suche nach Gemeinsamkeiten und Unterschieden zwischen den einzelnen Indikatoren. Die gewonnenen Ergebnisse können dann auf die den Indikatoren zugrunde liegenden Eigenschaften übertragen werden und in anderen Bereichen der Theorie genutzt werden. Eine solche gemeinsame Basis bietet das Konzept der w-bestimmten Populationen. In der vorliegenden Arbeit wird am Beispiel der Realraumindikatoren Cp gezeigt, wie man anhand dieses Konzeptes eine ganze Schar von Funktionalen kreieren und deren Eigenschaften systematisch testen kann. Das Konzept der w-bestimmten Populationen besteht im Wesentlichen aus zwei Teilschritten. Im ersten Schritt, der w-bestimmten Partitionierung des Raumes (w-RSP), wird der Gesamtraum in kompakte, raumfüllende, nicht überlappende Zellen, sogenannte Mikrozellen, zerlegt, wobei die Summe der Volumina der Mikrozellen stets das Volumen des Gesamtraums ergibt. Die Forderung, dass die Mikrozellen kompakt sein müssen, gewährleistet eine lokale Beschreibung. Aus den möglichen Partitionierungen wählt man nun eine derjenigen aus, für die die Mikrozellen alle dieselbe Menge w einer bestimmten Kontrollgröße haben, das heißt, das Integral über die Kontrollfunktion soll in jeder Mikrozelle denselben Wert w haben. Dadurch erhält man Probenräume, die bezüglich der Kontrolleigenschaft gleich sind. Im zweiten Schritt wird dann in den so erhaltenen Mikrozellen der Wert einer zweiten Größe, der Probengröße, bestimmt. Die resultierende Verteilung der Pobengröße ist natürlich vom expliziten Wert der Kontrolleigenschaft abhängig. Um diese Abhängigkeit zu umgehen, wird die diskrete Verteilung der Probengröße durch eine geeignete Potenz von w geteilt. Nach diesem Reskalierungsprozess liegt eine quasi-kontinuierliche Verteilung vor. Sie ist diskret per Definition, kann jedoch an jedem beliebigen (endlichen) Set von Aufpunkten (und eventuell weiterer Aufpunkte) berechnet werden. Der Limes nach Reskalieren ergibt eine kontinuierliche Funktion. Je nach Wahl der Kontroll- und Probenfunktion können mit diesem Konzept ganze Klassen von Funktionalen erzeugt werden. Die Funktionale sind besonders dann leicht miteinander vergleichbar, wenn sie entweder die Kontroll- oder Probenfunktion gemeinsam haben. Dieser Weg wurde in der vorliegenden Doktorarbeit beschritten. Anhand des eben dargestellten Konzeptes wurden die Realraumindikatoren Cp hergeleitet. Wie auch bei ELI-D ist die Probenfunktion bei den Cp-Indikatoren die Elektronendichte, das heißt die in den Mikrozellen geprobte Größe ist die Elektronenpopulation. Während für ELI-D die Raumpartitionierung durch die Anzahl der Paare in den Mikrozellen bestimmt wird, wird bei den Cp-Indikatoren die Inhomogenität der Elektronendichte als Kontrollgröße gewählt. Die Inhomogenität der Elektronendichte wird anhand des Abstandes der Elektronendichte zu ihrem Mittelwert in der jeweiligen Mikrozelle definiert: Ip(i) = pvuutZmi |r (~r)−r¯i|p dV . (1) Die Inhomogenität ist für jeden positiven Parameter p definiert. Je nach Wahl des Inhomogenitätsparameters p kommen kleinen beziehungsweise großen Abständen mehr Bedeutung zu. Die anhand des Konzeptes der w-bestimmten Populierung hergeleitete Funktionalschar Cp berechnet sich näherungsweise aus der Dichte und dem Dichtegradienten an den Aufpunkten ~ai der Mikrozellen: Cp(~ai) r (~ai) \"[2p(p+1)] |~Ñr (~ai)|p #3/(p+3) r (~ai) VIp , (2) wobei die Volumenfunktion VIp proportional zum Volumen einer festen Größe an Elektronendichteinhomogenität ist. Cp beruht ausschließlich auf Einelektroneneigenschaften, die sich aus der Elektronendichte ableiten lassen. Daher ist es prinzipiell möglich, Cp direkt aus dem Experiment zu bestimmen. ELI-D hingegen beruht sowohl auf der Elektronendichte, als auch auf der Paardichte, einer Zweiteilcheneigenschaft: ¡D(~ai) r (~ai) 12 g(~ai)| 3/8 r (~ai) VD . (3) Zur Berechnung der Paarvolumenfunktion VD ist die Kenntnis der Krümmung des Fermiloches g an der Elektronenkoaleszenz von Nöten. Die freie Wahl des Inhomogenitätsparameters p erlaubt es, die Volumenfunktion VIp zu justieren. Gelänge es, für ein bestimmtes Inhomogenitätsmaß die Proportionalität von VD und VIp zu erzeugen, so hätte man mit der entsprechenden Inhomogenität den Raumanspruch eines Paares abgebildet. Letztlich hätte dies zu einem Ausdruck für die Fermilochkrümmung als Funktion der Dichte geführt. (Dieser Ausdruck wiederum wäre in vielen Bereichen der Theorie von großem Nutzen.) Im Rahmen dieser Doktorarabeit konnte gezeigt werden, dass eine direkte Anpassung der Volumenfunktionen jedoch nicht in befriedigendem Maße gelingt. Daher wurde die Forderung der Proportionalität beider Indikatoren ein wenig abgeschwächt und lediglich verlangt, dass die Kurvenverläufe von Cp und ELI-D ähnlich sind. Besonderer Fokus wurde hier auf die Lage der Extrema gelegt. Die Forderung der ähnlichen Verläufe kann man durch die Anpassung der logarithmischen Gradienten der Volumenfunktionen gewährleisten. Die Anpassung erfolgte durch die Methode der kleinsten Fehlerquadrate und wurde für die Atome Li bis Xe durchgeführt. Die nach diesen Gesichtspunkten idealen Inhomgenitätsparameter konzentrieren sich alle unabhängig vom berechneten System bei Werten um p = 0.6. Das erhaltene Funktional C0.6 ist somit unabhängig vom Atomtyp und kann daher auch bei Molekülen und Festkörpern angewandt werden. C0.6 zeigt bei Atomen eine ähnliche Schalenstruktur wie ELI-D. Insbesondere die Elektronenpopulationen in den inneren Schalen spiegeln recht gut das Aufbauprinzip wieder. Bei den Übergangselementen und den direkt nachfolgenden Elementen fehlt allerdings der erwartete Separator zwischen der Valenz- und der letzten Rumpfschale. Bei Molekülen verlaufen die Bassingrenzen der Rumpfregionen sehr ähnlich, sodass die Elektronenpopulationen bis auf eine Differenz von 0.1 Elektron gleich sind. Im Bereich der freien Elektronenpaare zeigen beide Indikatoren dieselbe Anzahl von Attraktoren, wobei die C0.6-Attraktoren im Vergleich zu denen der ELI-D etwas näher am Kernort liegen. In den Regionen der freien Elektronenpaare können die Bassinpopulationen beider Indikatoren durchaus voneinander abweichen. Hierbei liegen die Elektronenpopulation von C0.6 im Mittel näher an den nach dem Lewisbild erwarteten Elektronenzahlen. Im Bereich der Bindung können große Unterschiede zwischen den Indikatoren auftreten, da C0.6 hier hauptsächlich durch den Gradiententerm dominiert ist und an jedem bindungskritischen Punkt einen Attraktor aufweisen muss. Atomare Verbindunglinien werden durch C0.6 entweder einfach zweifach oder dreifach markiert, wobei einfach markierte Linien bei unpolaren Bindungen und zweifach markierte bei polaren Bindungen zu finden sind. Dreifach markierte Linien entsprechen ungebundenen Zuständen. ELI-D hingegen zeigt keine Mehrfachmarkierung bei Einfachbindungen. Die an Molekülen abgeleiteten Aussagen über die Bindungsmarkierung lassen sich bei Festkörpern auf die nächsten Nachbarn übertragen. Durch die Zweifachmarkierung bei polaren Bindungen kann man auf einfache Weise die Gesamtelektronenpopulation eines Elementes im Verbund bestimmen (es gibt in der Regel keine geteilten Bassins). Dadurch lassen sich Ladungen berechnen und eine Skala der topologischen Kenngröße (vergleichbar mit einer Elektronegativitätsskala) aufstellen. Letzlich ist zu konstatieren, dass C0.6 nicht in der Lage ist, ELI-D hinreichend gut abzubilden. In Molekülen und Festkörpern erreicht der Gradient der Elektronendichte den Wert Null. An diesen Stellen ist C0.6 nicht an ELI-D anpassbar, da C0.6 hier einen Attraktor ausbilden muss. Dennoch hat diese Arbeit gezeigt, wie man anhand des Konzeptes der w-bestimmten Populationen Funktionale generieren und systematisch vergleichen, sowie gegebenenfalls aneinander anpassen kann. Die so gewonnenen Ergebnisse lassen sich auch in anderen Bereichen der Theorie anwenden. So mag C0.6 nicht nur in der Bindungsanalyse - wo es im Gegensatz zu ELI-D direkt aus dem Experiment bestimmt werden kann - Verwendung finden, sondern kann möglicherweise auch hilfreich bei der Entwicklung von Funktionalen in der Dichtefunktionaltheorie sein, da hier Funktionaltypen Anwendung finden, deren ortsabhängige Mischung der Austauschanteile durch Funktionen des Typs ˜Cp geregelt werden.

Cette thèse propose d'étudier en détail une méthode générale de construction d'un réseaude pores interconnectés à partir d'une image 3D d'un matériau poreux afin de calculer laperméabilité absolue. Un squelette de l'espace poral est tout d'abord utilisé pour définir laposition des pores. Ce squelette est transformé en graphe, puis plusieurs étapes de fusiondes nœuds sont réalisées pour obtenir un réseau exploitable. Une ligne de partage des eauxprenant comme marqueurs les nœuds du graphe permet d'attribuer une géométrie auxpores. Le système d'équation linéaire à résoudre est construit en intégrant les équations deStokes sur des éléments de l'espace poral. Une méthode originale de calcul du coefficient deproportionnalité existant entre les pressions au centre de deux pores et le débit traversantla surface les séparant est proposée. Une application de l'intégralité de l'approche estégalement présentée sur un matériau réel. / A general method to build a pore network model from a 3D image of a porous material ispresented in this work in order to compute its permeability. A skeleton of the void spaceis first used to define pores position. This skeleton is converted to a first graph. Mergingsteps are necessary to obtain a relevant network. A volume is allocated to the pores using awatershed algorithm, starting with markers defined from the nodes of the graph. The linearsystem of equations to solve is deduced by integrating the Stokes equations on pore spacepartitioning elements. The proportionality coefficient linking the pressure drop betweentwo pore centers and the flow going through the surface separating them is calculated withan original method. Application of the complete process to a real material is presented.