東華大學圖書館 |

語系: 繁體中文

說明(常見問題)

回圖書館首頁

手機版館藏查詢

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

Algorithmic Foundations of Self-Orga...

Derakhshandeh, Zahra.

FindBook

Google Book

Amazon

博客來

Algorithmic Foundations of Self-Organizing Programmable Matter.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Algorithmic Foundations of Self-Organizing Programmable Matter./
作者:	Derakhshandeh, Zahra.
出版者:	Ann Arbor : ProQuest Dissertations & Theses, : 2017,
面頁冊數:	136 p.
附註:	Source: Dissertations Abstracts International, Volume: 79-01, Section: B.
Contained By:	Dissertations Abstracts International79-01B.
標題:	Computer Engineering. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10285238
ISBN:	9781369825855

Algorithmic Foundations of Self-Organizing Programmable Matter.
Derakhshandeh, Zahra.

Algorithmic Foundations of Self-Organizing Programmable Matter. - Ann Arbor : ProQuest Dissertations & Theses, 2017 - 136 p.

Source: Dissertations Abstracts International, Volume: 79-01, Section: B.

Thesis (Ph.D.)--Arizona State University, 2017.

This item must not be sold to any third party vendors.

Imagine that we have a piece of matter that can change its physical properties like its shape, density, conductivity, or color in a programmable fashion based on either user input or autonomous sensing. This is the vision behind what is commonly known as programmable matter. Envisioning systems of nano-sensors devices, programmable matter consists of systems of simple computational elements, called particles, that can establish and release bonds, compute, and can actively move in a self-organized way. In this dissertation the feasibility of solving fundamental problems relevant for programmable matter is investigated. As a model for such self-organizing particle systems (SOPS), the geometric amoebot model is introduced. In this model, particles only have local information and have modest computational power. They achieve locomotion by expanding and contracting, which resembles the behavior of amoeba. Under this model, efficient local-control algorithms for the leader election problem in SOPS are presented. As a central problem for programmable matter, shape formation problems are then studied. The limitations of solving the leader election problem and the shape formation problem on a more general version of the amoebot model are also discussed. The \\smart paint" problem is also studied which aims at having the particles self-organize in order to uniformly coat the surface of an object of arbitrary shape and size, forming multiple coating layers if necessary. A Universal Coating algorithm is presented and shown to be asymptotically worst-case optimal both in terms of time with high probability and work. In particular, the algorithm always terminates within a linear number of rounds with high probability. A linear lower bound on the competitive gap between fully local coating algorithms and coating algorithms that rely on global information is presented, which implies that the proposed algorithm is also optimal in a competitive sense. Simulation results show that the competitive ratio of the proposed algorithm may be better than linear in practice. Developed algorithms utilize only local control, require only constant-size memory particles, and are asymptotically optimal in terms of the total number of particle movements needed to reach the desired shape configuration.

ISBN: 9781369825855Subjects--Topical Terms:

1567821
Computer Engineering.

Algorithmic Foundations of Self-Organizing Programmable Matter.
LDR:03397nmm a2200337 4500 001 2207481
005 20190920131235.5
008 201008s2017 ||||||||||||||||| ||eng d
020 $a 9781369825855
035 $a (MiAaPQ)AAI10285238
035 $a (MiAaPQ)asu:17149
035 $a AAI10285238
040 $a MiAaPQ $c MiAaPQ
100 1 $a Derakhshandeh, Zahra. $3 3434469
245 1 0 $a Algorithmic Foundations of Self-Organizing Programmable Matter.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2017
300 $a 136 p.
500 $a Source: Dissertations Abstracts International, Volume: 79-01, Section: B.
500 $a Publisher info.: Dissertation/Thesis.
500 $a Advisor: Richa, Andrea;Sen, Arunabha.
502 $a Thesis (Ph.D.)--Arizona State University, 2017.
506 $a This item must not be sold to any third party vendors.
520 $a Imagine that we have a piece of matter that can change its physical properties like its shape, density, conductivity, or color in a programmable fashion based on either user input or autonomous sensing. This is the vision behind what is commonly known as programmable matter. Envisioning systems of nano-sensors devices, programmable matter consists of systems of simple computational elements, called particles, that can establish and release bonds, compute, and can actively move in a self-organized way. In this dissertation the feasibility of solving fundamental problems relevant for programmable matter is investigated. As a model for such self-organizing particle systems (SOPS), the geometric amoebot model is introduced. In this model, particles only have local information and have modest computational power. They achieve locomotion by expanding and contracting, which resembles the behavior of amoeba. Under this model, efficient local-control algorithms for the leader election problem in SOPS are presented. As a central problem for programmable matter, shape formation problems are then studied. The limitations of solving the leader election problem and the shape formation problem on a more general version of the amoebot model are also discussed. The \\smart paint" problem is also studied which aims at having the particles self-organize in order to uniformly coat the surface of an object of arbitrary shape and size, forming multiple coating layers if necessary. A Universal Coating algorithm is presented and shown to be asymptotically worst-case optimal both in terms of time with high probability and work. In particular, the algorithm always terminates within a linear number of rounds with high probability. A linear lower bound on the competitive gap between fully local coating algorithms and coating algorithms that rely on global information is presented, which implies that the proposed algorithm is also optimal in a competitive sense. Simulation results show that the competitive ratio of the proposed algorithm may be better than linear in practice. Developed algorithms utilize only local control, require only constant-size memory particles, and are asymptotically optimal in terms of the total number of particle movements needed to reach the desired shape configuration.
590 $a School code: 0010.
650 4 $a Computer Engineering. $3 1567821
650 4 $a Information Technology. $3 1030799
650 4 $a Computer science. $3 523869
690 $a 0464
690 $a 0489
690 $a 0984
710 2 $a Arizona State University. $b Computer Science. $3 1676136
773 0 $t Dissertations Abstracts International $g 79-01B.
790 $a 0010
791 $a Ph.D.
792 $a 2017
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10285238