อนาโทล สลิสเซนโก
อนาตอล สลิสเซนโก (สลิเซนโก) (รัสเซีย: Анатоль Олесьевич Слисенко) | |
|---|---|
 | |
| เกิด | 15 สิงหาคม พ.ศ. 2484 |
| อัลมา มัธยฐาน | มหาวิทยาลัยรัฐเซนต์ปีเตอร์สเบิร์ก |
| เส้นทางอาชีพด้านวิทยาศาสตร์ | |
| ฟิลด์ | คณิตศาสตร์วิทยาการคอมพิวเตอร์ |
| สถาบันต่างๆ | สถาบันคณิตศาสตร์สเตคลอฟมหาวิทยาลัยรัฐเซนต์ปีเตอร์สเบิร์ก สถาบันสารสนเทศและระบบอัตโนมัติแห่งเลนินกราด สังกัดสถาบันวิทยาศาสตร์แห่งสหภาพโซเวียต มหาวิทยาลัยปารีส-เอสต์ เครเตล วาล-เดอ-มาร์นสถาบันโพลีเทคนิคเลนินกราด |
| นิโคไล อเล็กซานโดรวิช ชานิน | |
นักศึกษาปริญญาเอก | ดมิทรี กริกอริเยฟ |
อนาตอล สลิสเซนโก (การถอดเสียงเดิม: สลิเซนโก ; รัสเซีย: Анатоль Олесьевич Слисенко ) นักคณิตศาสตร์และนักวิทยาศาสตร์คอมพิวเตอร์ชาวโซเวียต รัสเซีย และฝรั่งเศส เกิดเมื่อวันที่ 15 สิงหาคม พ.ศ. 2484 ในไซบีเรีย ซึ่งบิดาของเขา[ 1 ]ดำรงตำแหน่งผู้บัญชาการกองทหารสำรวจภูมิประเทศ ในปี พ.ศ. 2493 บิดามารดาของเขาย้ายไปอยู่ที่เลนินกราด
วิจัย
แหล่งที่มา: [ 2 ]
ในปี พ.ศ. 2491 AO Slissenko เข้าศึกษาที่คณะคณิตศาสตร์และกลศาสตร์ มหาวิทยาลัยแห่งรัฐเลนินกราด (ปัจจุบันคือเซนต์ปีเตอร์สเบิร์ก) [ 3 ]ที่นั่นเขาเริ่มทำการวิจัย[ 4 ]ในสาขาคณิตศาสตร์เชิงสร้างสรรค์ (การวิเคราะห์แบบเวียนเกิด) [ 5 ] ภายใต้การดูแลของ Nikolai Shaninหลังจากสำเร็จการศึกษาจากมหาวิทยาลัยในปี พ.ศ. 2506 เขากลายเป็นนักวิจัยที่แผนกเลนินกราดของสถาบันคณิตศาสตร์ Steklov แห่งสถาบันวิทยาศาสตร์แห่งสหภาพโซเวียต (ปัจจุบันมีชื่อเรียกที่แตกต่างออกไปเล็กน้อย) [ 6 ]เขาป้องกันวิทยานิพนธ์ปริญญาเอกในสาขาคณิตศาสตร์เชิงสร้างสรรค์ในปี พ.ศ. 2510 โดยมี Nikolai Shanin เป็นอาจารย์ที่ปรึกษา ในปี พ.ศ. 2524 เขาป้องกันวิทยานิพนธ์ปริญญาเอกที่สถาบันคณิตศาสตร์ Steklov ในมอสโก
ในช่วงปี พ.ศ. 2506–2509 เขายังคงทำการวิจัยด้านคณิตศาสตร์เชิงสร้างสรรค์ต่อไป และในขณะเดียวกันเขาก็มีส่วนร่วมในการพัฒนาและนำอัลกอริทึมของ Shanin มาใช้สำหรับการพิสูจน์ทฤษฎีบทอัตโนมัติในตรรกศาสตร์ประพจน์แบบคลาสสิก[ 7 ]
จากนั้นเขาจึงเริ่มทำการวิจัยเกี่ยวกับอัลกอริทึมและความซับซ้อนในการคำนวณอย่างค่อยเป็นค่อยไป
ในเอกสาร[ 8 ]เขาได้อภิปรายถึงวิธีการกำหนดความซับซ้อนของ 'การคำนวณ' ของปัญหาแต่ละปัญหา ซึ่งเป็นหัวข้อที่มีอิทธิพลต่อเอกสารต่อมาของเขาเกี่ยวกับการบรรจบกันของเอนโทรปี
ใน[ 9 ]เขาได้เสนอวิธีแก้ปัญหาที่ไม่คาดคิดสำหรับปัญหาการจดจำพาลินโดรมโดยเครื่องจักรทัวริงแบบหลายหัว กล่าวคือ เขาพิสูจน์ว่าเครื่องจักรทัวริง 6 หัวที่มีเทปเพียงม้วนเดียวสามารถจดจำพาลินโดรมได้แบบเรียลไทม์ ซึ่งความคาดหวังที่แพร่หลายคือเป็นไปไม่ได้ การพิสูจน์ที่ยาวมากของเขาได้รับการทำให้ง่ายขึ้นในภายหลังโดย Zvi Galilซึ่งใช้ผลลัพธ์ใหม่บางอย่างที่ไม่เป็นที่รู้จักในขณะที่[ 9 ]กำลังถูกเขียน (ดูเพิ่มเติมที่[ 10 ])
ผลลัพธ์สำคัญอีกประการหนึ่งของ Slissenko คืออัลกอริทึมแบบเรียลไทม์ที่แก้ปัญหาการจับคู่สตริงได้หลากหลาย (รวมถึงการค้นหาคาบทั้งหมดในรูปแบบที่กระชับ) [ 11 ]อัลกอริทึมนี้สามารถกำหนดเป็น LRAM (เครื่องแอดเดรส) ซึ่งเป็นเครื่องเข้าถึงแบบสุ่มที่มีรีจิสเตอร์ซึ่งความยาวถูกจำกัดด้วยลอการิทึมของความซับซ้อนของเวลา ซึ่งแนะนำใน[ 12 ] และยังอธิบายไว้ใน[ 13 ] [ 11 ]โมเดลนี้อนุญาตให้ใช้การดำเนินการต่างๆ รวมถึงการคูณ ซึ่งหากไม่มีข้อจำกัดเรื่องความยาวนี้ จะทำให้ได้อัลกอริทึมที่เร็วเกินจริง นอกจากนั้น LRAM ยังมีลำดับชั้นความซับซ้อนของเวลาที่หนาแน่นมาก
ในช่วงปี พ.ศ. 2524–2535 สลิสเซนโกดำรงตำแหน่งหัวหน้าห้องปฏิบัติการในสถาบันสารสนเทศและระบบอัตโนมัติแห่งเซนต์ปีเตอร์สเบิร์กของสถาบันวิทยาศาสตร์แห่งรัสเซีย[ 14 ]เขาทำงานเกี่ยวกับการประยุกต์ใช้งานที่นั่น อย่างไรก็ตาม เป็นช่วงเวลาที่สหภาพโซเวียตกำลังประสบความยากลำบาก และไม่มีผลงานตีพิมพ์ที่น่าสนใจในสาขานี้
ใน[ 15 ]เขาได้แนะนำคลาสของไวยากรณ์กราฟ (เรียกว่าไวยากรณ์ Slisenko (Slissenko) ใน[ 16 ] ) ที่สร้างกราฟซึ่งสามารถตัดสินการมีอยู่ของวงจรแฮมิลโทเนียนได้ในเวลาพหุนาม กราฟที่สร้างโดยไวยากรณ์เหล่านี้มีความกว้างของต้นไม้ที่จำกัด
เอกสาร[ 17 ]เป็นเอกสารฉบับแรกของเขาซึ่งเขาได้นำเอนโทรปีมาใช้ในการประเมินคุณภาพของระบบอนุมาน
ตั้งแต่ปี พ.ศ. 2536 จนถึงปี พ.ศ. 2552 เขาเป็นศาสตราจารย์ที่มหาวิทยาลัยปารีส-อีสต์เครเตล[ 18 ] (UPEC: Université Paris-Est-Créteil; ชื่อเดิมคือมหาวิทยาลัยปารีส-12) คณะวิทยาศาสตร์และเทคโนโลยี ภาควิชาสารสนเทศ เขาทำงานเกี่ยวกับความซับซ้อนของกระบวนการตัดสินใจแบบมาร์คอฟ[ 19 ]เกี่ยวกับอัลกอริธึมในการสร้างเส้นทางที่สั้นที่สุดท่ามกลางอุปสรรคกึ่งพีชคณิตและอุปสรรคอื่นๆ และเกี่ยวกับการตรวจสอบระบบแบบกำหนดเวลา
เอกสาร[ 20 ]อธิบายอัลกอริทึม polytime สำหรับการสร้างเส้นทางที่สั้นที่สุดที่สัมผัสเส้นตรงเฉียงในพื้นที่ 3 มิติ ซึ่งแก้ปัญหาเปิดที่ทราบแล้ว
อั ลกอริทึม การตรวจสอบแบบจำลองสำหรับตรรกะที่มีประสิทธิภาพพอสมควรที่มีตัวดำเนินการความน่าจะเป็นได้รับการพัฒนาใน[ 21 ]ซึ่งเป็นผลลัพธ์แรกสำหรับตรรกะประเภทนี้
มีการตรวจสอบหัวข้อต่างๆ ของการตรวจสอบสำหรับโมเดลแบบกำหนดเวลา ใน[ 22 ]ได้มีการนำเสนอตรรกะที่มีประสิทธิภาพสำหรับการกำหนดระบบเรียลไทม์แบบแข็ง ซึ่งเรียกว่า FOTL (First Order Timed Logic) และมีการนำเสนอคลาสที่ตัดสินได้ คลาสที่ตัดสินได้ทั่วไปมากขึ้นได้รับการตรวจสอบใน[ 23 ]
การบรรจบกันของเอนโทรปีของอัลกอริทึมได้รับการแนะนำใน[ 24 ]และถูกนำไปใช้ในการประเมินฐานความรู้[ 25 ]
ใน[ 26 ]เขาสังเกตเห็นว่าเราสามารถปรับเปลี่ยนปัญหา P≠NP เล็กน้อยในลักษณะที่ยังคงน่าสนใจในทางปฏิบัติ แต่ความเป็นอิสระจากเลขคณิตหมายความว่า P≠NP
Slissenko ได้รับเชิญให้เป็นวิทยากรในการประชุมหลายครั้ง โดยเฉพาะอย่างยิ่งในการประชุมนานาชาติของนักคณิตศาสตร์ในปี 1983 ที่กรุงวอร์ซอ ประเทศโปแลนด์[ 27 ]
เขาร่วมมือกับNikolai Shanin , S.Maslov, G.Mintsและ V.Orevkov [ 28 ]ในการพิสูจน์ทฤษฎีบทอัตโนมัติ ร่วมกับ D.Beauquier, Dima Grigoriev , D.Burago , A.Rabinovich [ 29 ]และคนอื่นๆ ในหัวข้อต่างๆ ที่เกี่ยวข้องกับอัลกอริธึม[ 30 ] [ 31 ]
กิจกรรมการสอนและการจัดการองค์กร
AOSlissenko เป็นศาสตราจารย์นอกเวลาที่สถาบันโพลีเทคนิคเลนินกราด[ 32 ]ในปี 1981–1987 และในปี 1988–1992 เขาเป็นศาสตราจารย์นอกเวลาในคณะคณิตศาสตร์และกลศาสตร์ของมหาวิทยาลัยแห่งรัฐเลนินกราด[ 3 ]ซึ่งเขาเป็นหัวหน้าภาควิชาวิทยาการคอมพิวเตอร์ที่เขาริเริ่มสร้างขึ้น (ทีมของนักศึกษาในภาควิชานี้เป็นแชมป์โลกของการแข่งขัน ACM International Collegiate Programming Contest ถึงสี่ครั้ง) ในปี 1993–2009 เขาเป็นศาสตราจารย์เต็มเวลาที่มหาวิทยาลัยปารีส-อีสต์ เครเตล[ 18 ]ที่คณะวิทยาศาสตร์และเทคโนโลยี ภาควิชาสารสนเทศ ตั้งแต่ปี 2009 เขายังคงดำรงตำแหน่งศาสตราจารย์กิตติคุณที่มหาวิทยาลัยแห่งนี้
เขายังดำรงตำแหน่งหัวหน้า (และในแง่หนึ่งเป็นผู้ก่อตั้ง) ของห้องปฏิบัติการด้านความซับซ้อนของอัลกอริทึมและตรรกะ (LACL) ตั้งแต่ปี 1997 จนถึงปี 2007 ในทุกตำแหน่งที่ผ่านมา เขาได้มีส่วนร่วมในการปรับปรุงหลักสูตรและการวิจัยให้ทันสมัยยิ่งขึ้น
ในปี พ.ศ. 2510 Slissenko ได้ร่วมกับ Grigori Tseitin (1936–2022) และ Robert I.Freidson (1942–2018) จัดตั้งสัมมนา Leningrad Seminar on Computational Complexity [ 26 ]ซึ่งเริ่มแรกมีการประชุมที่มหาวิทยาลัยแห่งรัฐเลนินกราด จากนั้นจึงย้ายไปที่แผนกเลนินกราดของสถาบันคณิตศาสตร์ Steklov (ในเวลานั้น Slissenko ได้ดำรงตำแหน่งหัวหน้าอย่างเป็นทางการ) สัมมนานี้มีบทบาทสำคัญในการพัฒนาสาขานี้ในสหภาพโซเวียต สัมมนานี้ดำเนินงานจนถึงปี พ.ศ. 2535 ซึ่งหลังจากสหภาพโซเวียตล่มสลาย (และระบบการวิจัยของสหภาพโซเวียต) ผู้เข้าร่วมส่วนใหญ่ได้ออกจากประเทศและหางานทำในสหรัฐอเมริกา ฝรั่งเศส และสหราชอาณาจักร
ข้อมูลทางประวัติศาสตร์เกี่ยวกับวิทยาศาสตร์คอมพิวเตอร์ของโซเวียตสามารถพบได้ใน[ 26 ] [ 33 ]และข้อสังเกตบางประการอยู่ใน[ 34 ]
ลิงก์ภายนอก
- อนาโทล สลิสเซนโกจากโครงการลำดับวงศ์ตระกูลคณิตศาสตร์
- หน้าหลักของอนาโทล สลิสเซนโก
- ผลงานตีพิมพ์ของอนาโทล สลิสเซนโก
- ผลงานตีพิมพ์ของอนาโทล สลิสเซนโกในภาษารัสเซีย