Добірка наукової літератури з теми "Deterministic constant time algorithms"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "Deterministic constant time algorithms".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Статті в журналах з теми "Deterministic constant time algorithms"
Jayanti, Prasad, and Siddhartha Jayanti. "Deterministic Constant-Amortized-RMR Abortable Mutex for CC and DSM." ACM Transactions on Parallel Computing 8, no. 4 (December 31, 2021): 1–26. http://dx.doi.org/10.1145/3490559.
Повний текст джерелаSUEL, TORSTEN. "PERMUTATION ROUTING AND SORTING ON MESHES WITH ROW AND COLUMN BUSES." Parallel Processing Letters 05, no. 01 (March 1995): 63–80. http://dx.doi.org/10.1142/s0129626495000072.
Повний текст джерелаDAS, SAJAL K., and RANETTE H. HALVERSON. "SIMPLE DETERMINISTIC AND RANDOMIZED ALGORITHMS FOR LINKED LIST RANKING ON THE EREW PRAM MODEL." Parallel Processing Letters 04, no. 01n02 (June 1994): 15–27. http://dx.doi.org/10.1142/s012962649400003x.
Повний текст джерелаKhadiev, Kamil, and Vladislav Remidovskii. "Classical and Quantum Algorithms for Assembling a Text from a Dictionary." Nonlinear Phenomena in Complex Systems 24, no. 3 (October 12, 2021): 207–21. http://dx.doi.org/10.33581/1561-4085-2021-24-3-207-221.
Повний текст джерелаAllender, Eric, V. Arvind, Rahul Santhanam, and Fengming Wang. "Uniform derandomization from pathetic lower bounds." Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 370, no. 1971 (July 28, 2012): 3512–35. http://dx.doi.org/10.1098/rsta.2011.0318.
Повний текст джерелаRajasekaran, Sanguthevar. "On the Euclidean Minimum Spanning Tree Problem." Computing Letters 1, no. 1 (March 6, 2005): 11–14. http://dx.doi.org/10.1163/1574040053326325.
Повний текст джерелаEfthymiou, Charilaos. "Deterministic counting of graph colourings using sequences of subgraphs." Combinatorics, Probability and Computing 29, no. 4 (June 22, 2020): 555–86. http://dx.doi.org/10.1017/s0963548320000255.
Повний текст джерелаTarnawski, Jakub. "New graph algorithms via polyhedral techniques." it - Information Technology 63, no. 3 (April 15, 2021): 177–82. http://dx.doi.org/10.1515/itit-2021-0014.
Повний текст джерелаHu, Xiao-Bing, Ming Wang, Mark S. Leeson, Ezequiel A. Di Paolo, and Hao Liu. "Deterministic Agent-Based Path Optimization by Mimicking the Spreading of Ripples." Evolutionary Computation 24, no. 2 (June 2016): 319–46. http://dx.doi.org/10.1162/evco_a_00156.
Повний текст джерелаMehta, Dinesh P., Carl Shetters, and Donald W. Bouldin. "Meta-Algorithms for Scheduling a Chain of Coarse-Grained Tasks on an Array of Reconfigurable FPGAs." VLSI Design 2013 (December 25, 2013): 1–13. http://dx.doi.org/10.1155/2013/249592.
Повний текст джерелаДисертації з теми "Deterministic constant time algorithms"
Талмач, Дмитро Павлович. "Детерміновані методи відображення повідомлення в точку еліптичної кривої, заданої у різних формах". Bachelor's thesis, КПІ ім. Ігоря Сікорського, 2021. https://ela.kpi.ua/handle/123456789/44276.
Повний текст джерелаThe work is devoted to constructing deterministic polynomial algorithm for encoding sequences of bits into points of Elliptic Curves represented in different forms. The work presents basic information related to the topic of Elliptic Curves, especially in the Edwards form, that is necessary for understanding further mathematical calculations. Next, the problem of encoding underlying field elements, over which the curve is defined, into points of the curve for using this encoding in cryptographic protocols, which are based on hashing or key encapsulation schemes, is considered in more detail. In the last section new algorithms are presented and compared.
Nguyen, Huy Ngoc Ph D. Massachusetts Institute of Technology. "Constant time algorithms in sparse graph model." Thesis, Massachusetts Institute of Technology, 2010. http://hdl.handle.net/1721.1/62426.
Повний текст джерелаCataloged from PDF version of thesis.
Includes bibliographical references (p. 87-91).
We focus on constant-time algorithms for graph problems in bounded degree model. We introduce several techniques to design constant-time approximation algorithms for problems such as Vertex Cover, Maximum Matching, Maximum Weighted Matching, Maximum Independent Set and Set Cover. Some of our techniques can also be applied to design constant-time testers for minor-closed properties. In Chapter 1, we show how to construct a simple oracle that provides query access to a fixed Maximal Independent Set (MIS) of the input graph. More specifically, the oracle gives answers to queries of the form "Is v in the MIS?" for any vertex v in the graph. The oracle runs in constant-time, i.e., the running time for the oracle to answer a single query, is independent to the size of the input graph. Combining this oracle with a simple sampling scheme immediately implies an approximation algorithm for size of the minimum vertex cover. The second technique, called oracle hierarchy, transforms classical approximation algorithms into constant-time algorithms that approximate the size of the optimal solution. The technique is applicable to a certain subclass of algorithms that compute a solution in a constant number of phases. In the transformation, oracle hierarchy uses the MIS oracle to simulates each phase. The problems amenable to these techniques include Maximum Matching, Maximum Weight Matching, Set Cover, and Minimum Dominating Set. For example, for Maximum Matching, we give the first constant-time algorithm that for the class of graphs of degree bounded by d, computes the maximum matching size to within en, for any e > 0, where n is the number of vertices in the graph. The running time of the algorithm is independent of n, and only depends on d and e. In Chapter 2, we introduce a new tool called partitioning oracle which provides query access to a fixed partition of the input graph. In particular, the oracle gives answers to queries of the form "Which part in the fixed partition contains v?" for any vertex v in the graph. We develop methods for constructing a partitioning oracle for any class of bounded-degree graphs with an excluded minor. For any e > 0, our partitioning oracle provides query access to a fixed partition of the input constant-degree minor-free graph, in which every part has size 0(1/ 2 ), and the number of edges removed is at most en. We illustrate the power of this technique by using it to extend and simplify a number of previous approximation and testing results for sparse graphs, as well as to provide new results that were unachievable with existing techniques. For instance: " We give constant-time approximation algorithms for the size of the minimum vertex cover, the minimum dominating set, and the maximum independent set for any class of graphs with an excluded minor. * We show a simple proof that any minor-closed graph property is testable in constant time in the bounded degree model. Finally, in Chapter 3, we construct a more efficient partitioning oracle for graphs with constant treewidth. Although the partitioning oracle in Chapter 2 runs in time independent of the size of the input graph, it has to make 2POlY(1/E)) queries to the input graph to answer a query about the partition. Our new partitioning oracle improves this query complexity to poly(1/E) for graphs with constant treewidth. The new oracle can be used to test constant treewidth in poly(1/E) time in the bounded-degree model. Another application is a poly(1/E)-time algorithm that approximates the maximum matching size, the minimum vertex cover size, and the minimum dominating set size up to an additive en in bounded treewidth graphs.
by Huy Ngoc Nguyen.
Ph.D.
Domingues, Riaal. "A polynomial time algorithm for prime recognition." Diss., Pretoria : [s.n.], 2006. http://upetd.up.ac.za/thesis/available/etd-08212007-100529.
Повний текст джерелаYoshida, Yuichi. "Studies on Constant-Time Algorithms for Bounded-Degree Graphs and Constraint Satisfaction Problems." 京都大学 (Kyoto University), 2012. http://hdl.handle.net/2433/157487.
Повний текст джерелаAnderson, Robert Lawrence. "An Exposition of the Deterministic Polynomial-Time Primality Testing Algorithm of Agrawal-Kayal-Saxena." Diss., CLICK HERE for online access, 2005. http://contentdm.lib.byu.edu/ETD/image/etd869.pdf.
Повний текст джерелаJasanský, Michal. "Využití prostředků umělé inteligence pro podporu na kapitálových trzích." Master's thesis, Vysoké učení technické v Brně. Fakulta podnikatelská, 2013. http://www.nusl.cz/ntk/nusl-224231.
Повний текст джерелаVestin, Albin, and Gustav Strandberg. "Evaluation of Target Tracking Using Multiple Sensors and Non-Causal Algorithms." Thesis, Linköpings universitet, Reglerteknik, 2019. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-160020.
Повний текст джерелаHunter, Brandon. "Channel Probing for an Indoor Wireless Communications Channel." BYU ScholarsArchive, 2003. https://scholarsarchive.byu.edu/etd/64.
Повний текст джерелаYEO, HUI-LING, and 楊惠玲. "Constant-time Algorithms for Some Digraph Problems on RMESH." Thesis, 2001. http://ndltd.ncl.edu.tw/handle/06439018185264732057.
Повний текст джерела國立臺灣師範大學
資訊教育研究所
89
A directed reconfigurable mesh(abbreviated to DRM) is a parallel computation model, which consists of a 3-dimensional array with n^3 processors and a reconfigurable bus system. In this 3-D model, each processor has six direction’s switches and there is one input port and one output port for each direction. We can dynamically setup the configurations of all processors in order to form different and independent sub-buses in the processor array. In each sub-buses the data can be broadcasted in fixed units of time. There are a lot of researchers that develop efficient or constant-time algorithms based on this parallel computation model in order to solve many complicated problems. In this thesis, we propose a new O(1)-time algorithm for computing the transitive closure of digraph. Our algorithm is designed on a 3-dimensional nxnxn DRM, where n is the number of vertices in the graph. Using the O(1)-time transitive closure algorithms and the properties of digraph, we are able to develop many other related digraph algorithms that take O(1) time on a 3-dimensional nxnxn DRM. These problems include strongly connected component testing, finding the strongly connected component, topological sort, and the single source shortest path of acyclic digraph.
Megow, Nicole, and Andreas S. Schulz. "Scheduling to Minimize Average Completion Time Revisited: Deterministic On-line Algorithms." 2004. http://hdl.handle.net/1721.1/4048.
Повний текст джерелаКниги з теми "Deterministic constant time algorithms"
Allen, Michael P., and Dominic J. Tildesley. Molecular dynamics. Oxford University Press, 2017. http://dx.doi.org/10.1093/oso/9780198803195.003.0003.
Повний текст джерелаA, Dukeman G., and United States. National Aeronautics and Space Administration., eds. Examination of a practical aerobraking guidance algorithm. Washington, DC: American Institute of Aeronautics and Astronautics, 1995.
Знайти повний текст джерелаЧастини книг з теми "Deterministic constant time algorithms"
Grandoni, Fabrizio, Stefano Leonardi, Piotr Sankowski, Chris Schwiegelshohn,, and Shay Solomon. "(1 + ∊)-Approximate Incremental Matching in Constant Deterministic Amortized Time." In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 1886–98. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2019. http://dx.doi.org/10.1137/1.9781611975482.114.
Повний текст джерелаAlbers, Susanne, and Alexander Eckl. "Explorable Uncertainty in Scheduling with Non-uniform Testing Times." In Approximation and Online Algorithms, 127–42. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-80879-2_9.
Повний текст джерелаKarpinski, Marek, and Yakov Nekrich. "Predecessor Queries in Constant Time?" In Algorithms – ESA 2005, 238–48. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11561071_23.
Повний текст джерелаHoffmann, Michael, Vincent Kusters, and Tillmann Miltzow. "Halving Balls in Deterministic Linear Time." In Algorithms - ESA 2014, 566–78. Berlin, Heidelberg: Springer Berlin Heidelberg, 2014. http://dx.doi.org/10.1007/978-3-662-44777-2_47.
Повний текст джерелаItkis, Gene, Chengdian Lin, and Janos Simon. "Deterministic, constant space, self-stabilizing leader election on uniform rings." In Distributed Algorithms, 288–302. Berlin, Heidelberg: Springer Berlin Heidelberg, 1995. http://dx.doi.org/10.1007/bfb0022154.
Повний текст джерелаPietracaprina, Andrea, and Geppino Pucci. "Tight bounds on deterministic PRAM emulations with constant redundancy." In Algorithms — ESA '94, 391–400. Berlin, Heidelberg: Springer Berlin Heidelberg, 1994. http://dx.doi.org/10.1007/bfb0049425.
Повний текст джерелаMansour, Yishay, Boaz Patt-Shamir, and Shai Vardi. "Constant-Time Local Computation Algorithms." In Approximation and Online Algorithms, 110–21. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-28684-6_10.
Повний текст джерелаKonyagin, Sergei, and Carl Pomerance. "On Primes Recognizable in Deterministic Polynomial Time." In Algorithms and Combinatorics, 176–98. Berlin, Heidelberg: Springer Berlin Heidelberg, 1997. http://dx.doi.org/10.1007/978-3-642-60408-9_15.
Повний текст джерелаLenz, Tobias. "Deterministic Splitter Finding in a Stream with Constant Storage and Guarantees." In Algorithms and Computation, 26–35. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. http://dx.doi.org/10.1007/11940128_5.
Повний текст джерелаBrodnik, Andrej, and J. Ian Munro. "Membership in constant time and minimum space." In Algorithms — ESA '94, 72–81. Berlin, Heidelberg: Springer Berlin Heidelberg, 1994. http://dx.doi.org/10.1007/bfb0049398.
Повний текст джерелаТези доповідей конференцій з теми "Deterministic constant time algorithms"
Marchiori, Dúnia, Ricardo Custódio, Daniel Panario, and Lucia Moura. "Towards constant-time probabilistic root finding for code-based cryptography." In Simpósio Brasileiro de Segurança da Informação e de Sistemas Computacionais. Sociedade Brasileira de Computação - SBC, 2021. http://dx.doi.org/10.5753/sbseg.2021.17313.
Повний текст джерелаMarchiori, Dúnia, Ricardo Custódio, Daniel Panario, and Lucia Moura. "Towards constant-time probabilistic root finding for code-based cryptography." In Simpósio Brasileiro de Segurança da Informação e de Sistemas Computacionais. Sociedade Brasileira de Computação - SBC, 2021. http://dx.doi.org/10.5753/sbseg.2021.17313.
Повний текст джерелаKhonji, Majid, Ashkan Jasour, and Brian Williams. "Approximability of Constant-horizon Constrained POMDP." In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. California: International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/775.
Повний текст джерелаPatankar, Ravindra, and Asok Ray. "Fatigue Crack Propagation Under Variable-Amplitude Load: Part I — A Deterministic State-Space Model." In ASME 1998 International Mechanical Engineering Congress and Exposition. American Society of Mechanical Engineers, 1998. http://dx.doi.org/10.1115/imece1998-0228.
Повний текст джерелаAndrade de Melo, Alexsander, and Mateus De Oliveira Oliveira. "Symbolic Solutions for Symbolic Constraint Satisfaction Problems." In 17th International Conference on Principles of Knowledge Representation and Reasoning {KR-2020}. California: International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/kr.2020/6.
Повний текст джерелаEllen, Faith, Barun Gorain, Avery Miller, and Andrzej Pelc. "Constant-Length Labeling Schemes for Deterministic Radio Broadcast." In SPAA '19: 31st ACM Symposium on Parallelism in Algorithms and Architectures. New York, NY, USA: ACM, 2019. http://dx.doi.org/10.1145/3323165.3323194.
Повний текст джерелаEllen, Faith, and Seth Gilbert. "Constant-Length Labelling Schemes for Faster Deterministic Radio Broadcast." In SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures. New York, NY, USA: ACM, 2020. http://dx.doi.org/10.1145/3350755.3400238.
Повний текст джерелаIto, Hiro. "Constant-Time Algorithms for Complex Networks." In 2016 3rd Asia-Pacific World Congress on Computer Science and Engineering (APWC on CSE). IEEE, 2016. http://dx.doi.org/10.1109/apwc-on-cse.2016.014.
Повний текст джерелаDuPont, Bryony L., Jonathan Cagan, and Patrick Moriarty. "Optimization of Wind Farm Layout and Wind Turbine Geometry Using a Multi-Level Extended Pattern Search Algorithm That Accounts for Variation in Wind Shear Profile Shape." In ASME 2012 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2012. http://dx.doi.org/10.1115/detc2012-70290.
Повний текст джерелаNguyen, Huy N., and Krzysztof Onak. "Constant-Time Approximation Algorithms via Local Improvements." In 2008 IEEE 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, 2008. http://dx.doi.org/10.1109/focs.2008.81.
Повний текст джерелаЗвіти організацій з теми "Deterministic constant time algorithms"
Miles, Gaines E., Yael Edan, F. Tom Turpin, Avshalom Grinstein, Thomas N. Jordan, Amots Hetzroni, Stephen C. Weller, Marvin M. Schreiber, and Okan K. Ersoy. Expert Sensor for Site Specification Application of Agricultural Chemicals. United States Department of Agriculture, August 1995. http://dx.doi.org/10.32747/1995.7570567.bard.
Повний текст джерела