語系:
繁體中文
English
說明(常見問題)
回圖書館首頁
手機版館藏查詢
登入
回首頁
切換:
標籤
|
MARC模式
|
ISBD
Tropical circuit complexity = limits...
~
Jukna, Stasys.
FindBook
Google Book
Amazon
博客來
Tropical circuit complexity = limits of pure dynamic programming /
紀錄類型:
書目-電子資源 : Monograph/item
正題名/作者:
Tropical circuit complexity/ by Stasys Jukna.
其他題名:
limits of pure dynamic programming /
作者:
Jukna, Stasys.
出版者:
Cham :Springer International Publishing : : 2023.,
面頁冊數:
ix, 129 p. :ill., digital ;24 cm.
內容註:
Chapter. 1. Basics -- Chapter. 2. Combinatorial Bounds -- Chapter. 3. Rectangle Bounds -- Chapter. 4. Bounds for Approximating Circuits -- Chapter. 5. Tropical Branching Programs -- Chapter. 6. Extended Tropical Circuits.
Contained By:
Springer Nature eBook
標題:
Dynamic programming. -
電子資源:
https://doi.org/10.1007/978-3-031-42354-3
ISBN:
9783031423543
Tropical circuit complexity = limits of pure dynamic programming /
Jukna, Stasys.
Tropical circuit complexity
limits of pure dynamic programming /[electronic resource] :by Stasys Jukna. - Cham :Springer International Publishing :2023. - ix, 129 p. :ill., digital ;24 cm. - SpringerBriefs in mathematics,2191-8201. - SpringerBriefs in mathematics..
Chapter. 1. Basics -- Chapter. 2. Combinatorial Bounds -- Chapter. 3. Rectangle Bounds -- Chapter. 4. Bounds for Approximating Circuits -- Chapter. 5. Tropical Branching Programs -- Chapter. 6. Extended Tropical Circuits.
This book presents an enticing introduction to tropical circuits and their use as a rigorous mathematical model for dynamic programming (DP), which is one of the most fundamental algorithmic paradigms for solving combinatorial, discrete optimization problems. In DP, an optimization problem is broken up into smaller subproblems that are solved recursively. Many classical DP algorithms are pure in that they only use the basic (min,+) or (max,+) operations in their recursion equations. In tropical circuits, these operations are used as gates. Thanks to the rigorous combinatorial nature of tropical circuits, elements from the Boolean and arithmetic circuit complexity can be used to obtain lower bounds for tropical circuits, which play a crucial role in understanding the limitations and capabilities of these computational models. This book aims to offer a toolbox for proving lower bounds on the size of tropical circuits. In this work, the reader will find lower-bound ideas and methods that have emerged in the last few years, with detailed proofs. Largely self-contained, this book is meant to be approachable by graduate students in mathematics and computer science with a special interest in circuit complexity.
ISBN: 9783031423543
Standard No.: 10.1007/978-3-031-42354-3doiSubjects--Topical Terms:
641303
Dynamic programming.
LC Class. No.: T57.83
Dewey Class. No.: 519.703
Tropical circuit complexity = limits of pure dynamic programming /
LDR
:02480nmm a2200337 a 4500
001
2335615
003
DE-He213
005
20231106213708.0
006
m d
007
cr nn 008maaau
008
240402s2023 sz s 0 eng d
020
$a
9783031423543
$q
(electronic bk.)
020
$a
9783031423536
$q
(paper)
024
7
$a
10.1007/978-3-031-42354-3
$2
doi
035
$a
978-3-031-42354-3
040
$a
GP
$c
GP
041
0
$a
eng
050
4
$a
T57.83
072
7
$a
PBD
$2
bicssc
072
7
$a
MAT008000
$2
bisacsh
072
7
$a
PBD
$2
thema
082
0 4
$a
519.703
$2
23
090
$a
T57.83
$b
.J93 2023
100
1
$a
Jukna, Stasys.
$3
3668163
245
1 0
$a
Tropical circuit complexity
$h
[electronic resource] :
$b
limits of pure dynamic programming /
$c
by Stasys Jukna.
260
$a
Cham :
$b
Springer International Publishing :
$b
Imprint: Springer,
$c
2023.
300
$a
ix, 129 p. :
$b
ill., digital ;
$c
24 cm.
490
1
$a
SpringerBriefs in mathematics,
$x
2191-8201
505
0
$a
Chapter. 1. Basics -- Chapter. 2. Combinatorial Bounds -- Chapter. 3. Rectangle Bounds -- Chapter. 4. Bounds for Approximating Circuits -- Chapter. 5. Tropical Branching Programs -- Chapter. 6. Extended Tropical Circuits.
520
$a
This book presents an enticing introduction to tropical circuits and their use as a rigorous mathematical model for dynamic programming (DP), which is one of the most fundamental algorithmic paradigms for solving combinatorial, discrete optimization problems. In DP, an optimization problem is broken up into smaller subproblems that are solved recursively. Many classical DP algorithms are pure in that they only use the basic (min,+) or (max,+) operations in their recursion equations. In tropical circuits, these operations are used as gates. Thanks to the rigorous combinatorial nature of tropical circuits, elements from the Boolean and arithmetic circuit complexity can be used to obtain lower bounds for tropical circuits, which play a crucial role in understanding the limitations and capabilities of these computational models. This book aims to offer a toolbox for proving lower bounds on the size of tropical circuits. In this work, the reader will find lower-bound ideas and methods that have emerged in the last few years, with detailed proofs. Largely self-contained, this book is meant to be approachable by graduate students in mathematics and computer science with a special interest in circuit complexity.
650
0
$a
Dynamic programming.
$3
641303
650
0
$a
Logic circuits.
$3
527270
650
1 4
$a
Discrete Mathematics.
$3
1569938
650
2 4
$a
Computational Complexity.
$3
3538876
650
2 4
$a
Discrete Optimization.
$3
2054320
650
2 4
$a
Mathematical Applications in Computer Science.
$3
1567978
710
2
$a
SpringerLink (Online service)
$3
836513
773
0
$t
Springer Nature eBook
830
0
$a
SpringerBriefs in mathematics.
$3
1566700
856
4 0
$u
https://doi.org/10.1007/978-3-031-42354-3
950
$a
Mathematics and Statistics (SpringerNature-11649)
筆 0 讀者評論
館藏地:
全部
電子資源
出版年:
卷號:
館藏
1 筆 • 頁數 1 •
1
條碼號
典藏地名稱
館藏流通類別
資料類型
索書號
使用類型
借閱狀態
預約狀態
備註欄
附件
W9461820
電子資源
11.線上閱覽_V
電子書
EB T57.83
一般使用(Normal)
在架
0
1 筆 • 頁數 1 •
1
多媒體
評論
新增評論
分享你的心得
Export
取書館
處理中
...
變更密碼
登入