“What is an algorithm?” is a fundamental question of computer science. Gurevich’s behavioural theory of sequential algorithms (aka the sequential ASM thesis) gives a partial answer by defining (non-deterministic) sequential algorithms axiomatically, without referring to a particular machine model or programming language, and showing that they are captured by (non-deterministic) sequential Abstract State Machines (nd-seq ASMs). However, recursive algorithms such as mergesort are not covered by this theory, as has been pointed out by Moschovakis, who had independently developed a different framework to mathematically characterize the concept of (in particular recursive) algorithm. In this article we propose an axiomatic definition of the notion of sequential recursive algorithm which extends Gurevich’s axioms for sequential algorithms by a Recursion Postulate and allows us to prove that sequential recursive algorithms are captured by recursive Abstract State Machines, an extension of nd-seq ASMs by a CALL rule. Applying this recursive ASM thesis yields a characterization of sequential recursive algorithms as finitely composed concurrent algorithms all of whose concurrent runs are partial-order runs.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
W artykule przedstawiono sposób organizacji algorytmów współbieżnych FDTD i dekompozycji LU oraz przedyskutowano podstawowe cechy obu algorytmów. Prezentowane pełne numeryczne sformułowanie algorytm FDTD pozwala na analizą zagadnień dwuwymiarowych. Omówiony w drugiej części algorytm LU stanowi fragment solvera stosowanego w przybliżonych metodach analizy pola elektromagnetycznego. Poniższe algorytmy zostały opracowane w Katedrze Elektrotechniki Teoretycznej i Metrologii Politechniki Białostockiej z wykorzystaniem komputera równoległego Alex AVX2 klasy MIMD.
EN
The mathematical background of electromagnetic field analysis and specification of the suitable numerical methods were presented in the paper. The detailed description of two sophisticated concurrent algorithms is given. The first one is the FDTD (finite difference time domain) algorithm, which was applied to the analysis of the propagation of high frequency electromagnetic wave. The parallel version of the LU decomposition, a part of the finite element method solver, is described as the second method. The properties of the FDTD and LU algorithms were discussed.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.