Some Opportunities3.1 Certifying Al

Some Opportunities
3.1 Certifying Algorithms
A very interesting trend in algorithm design is the idea of certifying algorithms,
those that produce a machine-checkable certicate of the validity of their output.
For example, a certifying planarity tester would not take a nite graph and
return a boolean, but rather would either produce an embedding of the graph
into the plane, or produce an embedding of a Kuratowski subgraph into the given
graph as proof that it is non-planar. This point of view is not only tremendously
practical as a means of ensuring code correctness, but it is also fundamentally
coherent with the emphasis on constructive mathematics in language research|
a certifying algorithm is a constructive proof that for every nite graph G either
there is an embedding of G into R2 or there is an embedding of K5 or K3;3 into
G. Constructively, one is required to produce a proof of one of the disjuncts
(not merely that both cannot be false), and in each case to explicitly exhibit
the embeddings (not merely that an embedding cannot fail to exist).
Certication provides a point of contact between existing work in languages
and algorithms that could well provide the basis for further coordination and
collaboration between the two areas. One possibility is to develop a construc-
tive formulation of the properties of algorithms that is, from a computational
viewpoint, sharper than the classical view. According to classical logic there is
no distinction between a graph being planar and the impossibility of a graph
being non-planar. But constructively there is all the dierence between the
mere existence" of an embedding in the plane (given by evidence that cannot
be used in a further computation) and the existence" of such an embedding
(which must be presented by an assignment of coordinates to the nodes, say, in
Rn). Mehlhorn's work shows that there is an important practical application
to drawing such a distinction, and demonstrates that in algorithms, as in other
settings [The Univalent Foundations Program, 2013], constructivity may be a
useful tool for obtaining practical results.

ผลลัพธ์ (ไทย) 1:

บางโอกาส3.1 อัลกอริทึมรับรองแนวโน้มที่น่าสนใจมากในการออกแบบขั้นตอนวิธีเป็นแนวคิดของอัลกอริทึมรับรองผู้ที่ cate certi เครื่อง checkable มีการแสดงผลของพวกเขาตัวอย่าง แบบทดสอบ planarity รับรองจะไม่มีกราฟไนท์ และกลับเป็นบูลีน แต่ค่อนข้าง จะใดผลิตฝังของกราฟเครื่องบิน หรือการฝัง subgraph Kuratowski เป็นผลิตที่กำหนดกราฟเป็นหลักฐานว่า จะไม่ใช่ระนาบ จุดของมุมมองนี้ไม่เพียงอย่างปฏิบัติ ตามวิธีมั่นใจความถูกต้องของรหัส แต่มันเป็นภาระกับการเน้นสร้างสรรค์คณิตศาสตร์ในภาษา research|อัลกอริทึมการรับรองเป็นหลักฐานสร้างสรรค์ว่า สำหรับไนท์ทุกกราฟ G อย่างใดอย่างหนึ่งมีการฝังตัวของ G เป็น R2 หรือมีการฝังตัวของ K5 K3; 3 เป็นกรัมสร้างสรรค์ หนึ่งจะต้องสร้างหลักฐาน disjuncts การอย่างใดอย่างหนึ่ง(ไม่เพียงแต่ว่า ทั้งสองไม่ผิด), และ ในแต่ละกรณีแสดงอย่างชัดเจนembeddings (ไม่เพียงที่ฝังตัวไม่อยู่)Certi cation มีจุดติดต่อระหว่างงานที่มีอยู่ในภาษาและอัลกอริทึมที่ดีให้ข้อมูลพื้นฐานสำหรับการประสานงานเพิ่มเติม และความร่วมมือระหว่างสองพื้นที่ ความเป็นไปได้ที่หนึ่งจะพัฒนา construc แบบtive กำหนดคุณสมบัติของอัลกอริทึมคือ จากการคำนวณจุดชมวิว คมกว่าดูคลาสสิก ตามตรรกะคลาสสิก มีไม่แบ่งแยกเป็นระนาบกราฟและเป็นไปได้ทำของกราฟการไม่มีระนาบ แต่สร้างสรรค์ erence ดิระหว่างการmere ดำรงอยู่"ของการฝังตัวในเครื่องบิน (กำหนด โดยหลักฐานที่ไม่ใช้ในการคำนวณเพิ่มเติม) และ existence การ "เช่นการฝัง(ซึ่งต้องแสดง โดยการกำหนดพิกัดการโหน พูด ในRn) ทำงานของ Mehlhorn แสดงว่า มีการประยุกต์ในทางปฏิบัติเป็นสำคัญการวาดภาพดังกล่าวแตกต่าง และแสดงให้เห็นถึงที่ในอัลกอริทึม ในอื่น ๆการตั้งค่า [Univalent รากฐานโปรแกรม 2013], constructivity อาจจะเป็นเครื่องมือที่มีประโยชน์สำหรับการได้รับผลทางปฏิบัติ

ผลลัพธ์ (ไทย) 2:

บางโอกาส
3.1
รับรองอัลกอริทึมแนวโน้มที่น่าสนใจมากในการออกแบบขั้นตอนวิธีการคือความคิดของการรับรองขั้นตอนวิธีการที่ผลิต
Cate รับรองเครื่อง checkable ของความถูกต้องของการส่งออกของพวกเขา.
ตัวอย่างเช่นการทดสอบ planarity รับรองจะไม่ใช้กราฟ Nite
และผลตอบแทนแบบบูล
แต่อาจจะผลิตการฝังของกราฟลงในเครื่องบินหรือผลิตการฝังของsubgraph Kuratowski
เข้าที่กำหนดกราฟเป็นข้อพิสูจน์ว่ามันไม่เป็นระนาบ มุมมองนี้ไม่เพียง
แต่อย่างมากในทางปฏิบัติเป็นวิธีการสร้างความมั่นใจในความถูกต้องรหัสแต่ก็ยังเป็นพื้นฐานที่สอดคล้องกันโดยเน้นการสร้างสรรค์คณิตศาสตร์ในการวิจัยภาษา | ขั้นตอนวิธีการรับรองเป็นหลักฐานที่สร้างสรรค์ว่าทุกกราฟ Nite G ทั้งมีคือฝังลงใน G R2 หรือมีการฝัง K5 หรือ K3 3 เข้ากรัม สร้างสรรค์อย่างใดอย่างหนึ่งจะต้องผลิตหลักฐานของหนึ่งใน disjuncts (ไม่ใช่แค่ว่าทั้งสองไม่สามารถเป็นเท็จ) และในแต่ละกรณีอย่างชัดเจนแสดงembeddings (ไม่เพียง แต่ที่ฝังไม่สามารถล้มเหลวจะมีชีวิตอยู่). ไอออนบวก Certi ให้จุด ของการติดต่อระหว่างการทำงานที่มีอยู่ในภาษาและขั้นตอนวิธีที่ดีสามารถให้พื้นฐานสำหรับการประสานงานต่อไปและการทำงานร่วมกันระหว่างสองพื้นที่ หนึ่งเป็นไปได้คือการพัฒนาสิ่งก่อสร้างสูตรเชิงคุณสมบัติของอัลกอริทึมที่จากการคำนวณมุมมองที่คมชัดกว่ามุมมองคลาสสิก ตามตรรกะคลาสสิกที่มีความแตกต่างระหว่างการเป็นกราฟระนาบและเป็นไปไม่ได้ของกราฟเป็นไม่เป็นระนาบ แต่สร้างสรรค์มีทั้งหมด di หรือไม่การตั้งระหว่างการดำรงอยู่เพียง "ของการฝังในเครื่องบิน (ที่ได้รับจากหลักฐานที่ไม่สามารถนำมาใช้ในการคำนวณต่อไป) และการดำรงอยู่ " ของเช่นการฝัง(ซึ่งจะต้องนำเสนอโดย การกำหนดพิกัดไปยังโหนดที่พูดในRn) ทำงาน Mehlhorn แสดงให้เห็นว่ามีการใช้งานจริงที่สำคัญในการวาดภาพเช่นความแตกต่างและแสดงให้เห็นว่าในขั้นตอนวิธีในขณะที่คนอื่นๆการตั้งค่า [โปรแกรมพื้นฐานความหมายเดียว 2013] constructivity อาจจะเป็นเครื่องมือที่มีประโยชน์สำหรับการได้รับผลในทางปฏิบัติ

ผลลัพธ์ (ไทย) 3:

โอกาส

รับรองขั้นตอนวิธี 3.1 แนวโน้มที่น่าสนใจมากในการออกแบบขั้นตอนวิธีคือความคิดของรับรองขั้นตอนวิธี
ที่ผลิตเครื่องเช็คเอาต์ certi  เคทของความถูกต้องของผลผลิต .
ตัวอย่างเช่น รับรองเครื่อง planarity จะไม่ใช้  ไนท์และกราฟ
กลับตรรกะ แต่จะผลิต มีการฝังตัวของกราฟ
เข้าไปในเครื่องบินหรือการผลิตการฝังตัวของ kuratowski subgraph ลงให้
กราฟพิสูจน์ว่ามันไม่ระนาบ . มุมมองนี้ไม่เพียงเป็นประโยชน์อย่างมาก
ความหมายของ ให้รหัส ความถูกต้อง แต่ก็ลึกซึ้ง
ติดต่อกันโดยเน้นสร้างสรรค์คณิตศาสตร์ใน | การวิจัยภาษา : รับรองวิธีสร้างสรรค์ พิสูจน์ได้ว่า ทุก  กราฟ G เหมือนกัน
ไนท์มีการฝังตัวของ G เป็น R2 หรือมีการฝังตัวของเสียใจหรือ K3
G ; 3 เป็นอย่างสร้างสรรค์ คือ ต้องสร้างหลักฐานของ disjuncts
( ไม่เพียง แต่ที่ทั้งสองไม่สามารถเป็นเท็จ ) และในแต่ละกรณี เพื่อแสดง embeddings อย่างชัดเจน
( ไม่เพียง แต่ที่ไม่ได้ฝัง ล้มเหลวที่จะอยู่ )
certi  บวกให้จุดของการติดต่อระหว่างการทำงานที่มีอยู่ในภาษา
และขั้นตอนวิธีที่ดีอาจให้พื้นฐานสำหรับการประสานงานและความร่วมมือต่อไป
ระหว่างสองพื้นที่ หนึ่งในความเป็นไปได้ที่จะพัฒนา Construc -
tive การกำหนดคุณสมบัติของอัลกอริทึมที่ได้จากการคำนวณมุมมอง
คมชัดกว่ามุมมองคลาสสิก ตามตรรกศาสตร์แบบฉบับมี
ไม่มีความแตกต่างระหว่างกราฟมีพื้นผิวเรียบและเป็นไปไม่ได้ของกราฟ
ถูกบนระนาบ . แต่อย่างสร้างสรรค์ มีทั้งหมด ดิ  erence ระหว่าง
N การดำรงอยู่เท่านั้น " ของการฝังตัวในเครื่อง ( โดยให้หลักฐานที่สามารถใช้ในการคำนวณต่อไป
) N การดำรงอยู่ " เช่นการฝัง
( ซึ่งต้องนำเสนอโดยการมอบหมายของพิกัดไปยังโหนด , พูด , ใน
Rn ) mehlhorn ทำงานแสดงให้เห็นว่ามี
ใบสมัครจริงสำคัญการวาด เช่น ความแตกต่าง และแสดงให้เห็นว่าในอัลกอริทึม ในการตั้งค่าอื่น ๆ
[ โปรแกรมฐานรากเดี่ยว 2013 ] ,
constructivity อาจจะเป็นเครื่องมือที่มีประโยชน์สำหรับการได้รับผลลัพธ์ในทางปฏิบัติ