Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Натюрморт — клас конфігурацій у «Житті» — створеного Конвеєм моделі клітинного автомата.
Опис
Натюрморти — конфігурації «Життя» або іншого клітинного автомата, які не змінюються в процесі еволюції. Іншими словами, натюрморт є періоду 1.
Термінологія: натюрморти і псевдонатюрморти
Існує декілька близьких за змістом термінів, що означають конфігурації, які не змінюються в процесі еволюції (конфігурації, що є власними батьками). Відмінності між ними пов'язані з відповіддю на наступні питання:
- Чи вважається натюрмортом конфігурація, що складається з двох незалежних натюрмортів (наприклад, двох на досить великій відстані один від одного)?
- Чи вважається натюрмортом конфігурація, яка складається з двох частин, будь-яку з яких можна видалити так, що друга частина залишиться батьком собі?
В існуючих словниках і онлайн-енциклопедіях наводяться наступні визначення:
- Стійкий зразок (англ. stable pattern) — об'єкт, який є власним батьком;
- Натюрморт (англ. still life, strict still life) — стійкий об'єкт, що є і непорожнім, який не може бути розділений на дві стійкі частини;
- Псевдонатюрморт (англ. pseudo still life) — стійкий об'єкт, що не є натюрмортом, в якому присутня хоч би одна мертва клітина, що має більше трьох сусідів всього, але менше трьох сусідів у кожному із складових об'єкт-натюрмортів.
Точне визначення «стійкості» представляє інтерес в контексті перерахування натюрмортів: наприклад, згідно з приведеними визначеннями, кількість стійких конфігурацій розміру 8 (тобто таких, що складаються з 8 живих клітин) в «Житті» нескінченно, оскільки пара на будь-якій відстані один від одного є стійким; проте, кількість натюрмортів обмеженого розміру вважається кінцевою.
 | Псевдонатюрморт у «Житті». Віддаленість одного з островів не впливає на стабільність другого острова. |
 | «Строгий» натюрморт. Стабільність кожного з островів залежить від наявності другого острова. |
Відоме число натюрмортів і псевдонатюрмортів розміру не вище 24 клітин.
Задача визначення типу стійкості конфігурації (натюрморт, псевдонатюрморт) вирішується за поліноміальний час шляхом пошуку циклів у зв'язаному кососиметричному графі.
Натюрморти у «Житті»
У «Житті» існує множина природних натюрмортів.
Прості приклади
Блок
Найбільш поширений натюрморт — блок — конфігурація у формі квадрата 2 × 2. Два блоки, розміщені в прямокутнику 2 × 5, утворюють бі-блок — простий псевдонатюрморт. Блоки використовуються як складові частини у безлічі складних пристроїв, наприклад, до .
 |  |
Вулик
Другий за поширенням натюрморт — вулик (англ. hive, beehive). Вулики часто виникають четвірками в конфігурації, що називається пасікою (англ. honey farm).
 |  |
Коровай
Третій по поширеностті натюрморт — коровай (англ. loaf). Короваї нерідко з'являються парами (англ. bi-loaf). В свою чергу, подвійні короваї також з'являються в парах, званих пекарнями (англ. bakery).
 |  |  |
Ящики, баржі, човни, кораблі
Ящик (англ. tub) складається з чотирьох живих клітин в околиці фон Неймана центральної мертвої клітини. Додавання однієї живої клітини по діагоналі до центральної клітини перетворює ящик на човен (англ. boat), а додавання симетрично ще однієї клітини — на корабель (англ. ship). Природне подовження цих трьох конфігурацій дає баржу (англ. barge), довгий човен (англ. long-boat) і довгий корабель (англ. long-ship) відповідно. Подовження можна продовжувати скільки завгодно довго.
 |
 |
 |
З двох човнів можна скласти ще один натюрморт — човниковий бант (англ. boat tie), а з двох кораблів — корабельний бант (англ. ship tie).
 |  |
Інші натюрморти
|
Пожирачі і відбивачі
Натюрморти можливо використати для модифікації або руйнування інших об'єктів. Пожирач (англ. eater) здатний знищити і відновитися після реакції. (англ. reflector) замість знищення космічного корабля змінює його курс.
Відбивачі і пожирачі не обов'язково повинні бути натюрмортами.
| Пожирачі | ||||
|---|---|---|---|---|
|
Максимальна щільність
Задача розміщення в області n × n натюрморта з максимальним числом клітин привертала до себе увагу програмістів як задача Програмування в обмеженнях. При спрямування розміру області до нескінченності, живими можуть бути не більше 50 % клітин. На обмежених квадратних областях можливо досягти більших щільностей. Так, максимальна щільність натюрморта в квадраті 8 × 8 дорівнює 36/64 = 0.5625 — цю щільність забезпечує зразок, що складається з дев'яти блоків Для квадратів до 20 × 20 відомі оптимальні рішення.
| Натюрморти максимальної щільності у «Житті» | ||||
|---|---|---|---|---|
|
Число натюрмортів
Число натюрмортів і псевдонатюрмортів в «Житті» відомо до розміра в 24 клітини.
| Число живих клітин | Число натюрмортів | Приклади |
|---|---|---|
| 1 | 0 | |
| 2 | 0 | |
| 3 | 0 | |
| 4 | 2 | блок, ящик |
| 5 | 1 | човен |
| 6 | 5 | баржа, авіаносець, вулик, корабель, змія |
| 7 | 4 | риболовний гачок, коровай, довгий човен |
| 8 | 9 | каное, манго, довга баржа, ставок |
| 9 | 10 | знак інтегралу |
| 10 | 25 | човниковий бант |
| 11 | 46 | |
| 12 | 121 | корабельний бант |
| 13 | 240 | |
| 14 | 619 | подвійний коровай |
| 15 | 1353 | |
| 16 | 3286 | |
| 17 | 7773 | |
| 18 | 19044 | |
| 19 | 45759 | пожирач-2 |
| 20 | 112243 | |
| 21 | 273188 | |
| 22 | 672172 | |
| 23 | 1646147 | |
| 24 | 4051711 |
Ресурси Інтернету
- Николай Белюченко. Словарь Жизни. оригіналу за 10 жовтня 2012. Процитовано 4 серпня 2017.
- Stephen A. Silver. . Архів оригіналу за 26 травня 2013. Процитовано 4 серпня 2017.
Примітки
- Більш строгі визначення див. у розділі «Термінологія».
- Устойчивый. Словарь Жизни.
- . Life Lexicon. Архів оригіналу за 20 лютого 2009. Процитовано 4 серпня 2017.
- Eric Weisstein. Still Life. Treasure Trove of Life C.A. Процитовано 11 серпня 2013.
{{}}: Обслуговування CS1: Сторінки з параметром url-status, але без параметра archive-url () - Якщо відповідь на це питання позитивна, то кількість натюрмортів з обмеженим числом клітин нескінченна.
- Николай Белюченко. Словарь Жизни (рос.). оригіналу за 10 жовтня 2012. Процитовано 4 серпня 2017.
- Stephen A. Silver. (англ.). Архів оригіналу за 26 травня 2013. Процитовано 4 серпня 2017.
- Still life. ConwayLife.com. Процитовано 11 серпня 2013.
- Натюрморт. Словарь Жизни.
- . Life Lexicon. Архів оригіналу за 20 лютого 2009. Процитовано 4 серпня 2017.
- Псевдонатюрморт. Словарь Жизни.
- . Life Lexicon. Архів оригіналу за 3 грудня 2014. Процитовано 4 серпня 2017.
- Cook, Matthew (2003). Still life theory. New Constructions in Cellular Automata. Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press. с. 93—118.
- Природний зразок — об'єкт, який відносно часто виникає в процесі розвитку випадкової конфігурації.
- Achim Flammenkamp. Top 100 of Game-of-Life Ash Objects. Процитовано 5 листопада 2008.
- Игра Жизнь (обзор Гарднера). оригіналу за 18 жовтня 2012. Процитовано 11 серпня 2013.
- Клумова И. Н. Игра «Жизнь» // Квант. — 1974. — № 9. — С. 26—30.
- Пекарня. Словарь Жизни.
- Не плутати з .
- Bosch, R. A. (1999). Integer programming and Conway’s game of Life. SIAM Review. 41 (3): 594—604. doi:10.1137/S0036144598338252..
- Bosch, R. A. (2000). Maximum density stable patterns in variants of Conway’s game of Life. Operations Research Letters. 27 (1): 7—11. doi:10.1016/S0167-6377(00)00016-X..
- Smith, Barbara M. (2002). Principles and Practice of Constraint Programming - CP 2002. Lecture Notes in Computer Science. 2470. Springer-Verlag: 89—94. doi:10.1007/3-540-46135-3_27.
{{}}: Проігноровано|contribution=(). - Bosch, Robert; Trick, Michael (2004). Constraint programming and hybrid formulations for three Life designs. Annals of Operations Research. 130 (1–4): 41—56. doi:10.1023/B:ANOR.0000032569.86938.2f..
- Cheng, Kenil C. K.; Yap, Roland H. C. (2006). Applying ad-hoc global constraints with the case constraint to still-life. Constraints. 11 (2–3): 91—114. doi:10.1007/s10601-006-8058-9..
- Elkies, Noam D. (1998). The still life density problem and its generalizations. Voronoi's Impact on Modern Science, Book I. Proc. Inst. Math. Nat. Acad. Sci. Ukraine, vol. 21. с. 228—253. arXiv:math.CO/9905194.
- J. Larrosa, E. Morancho and D. Niso (2005). . Journal of Artificial Intelligence Research. 23: 421—440. Архів оригіналу за 16 липня 2011.
- Neil Yorke-Smith. Maximum Density Still Life. Artificial Intelligence Center. SRI International.
- Number of stable n-celled patterns («still lifes») in Conway's game of Life
- Number of n-celled pseudo-still-lifes in Conway's game of Life
- Niemiec, Mark D. . Архів оригіналу за 21 січня 2013. Процитовано 4 серпня 2017.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Natyurmort klas konfiguracij u Zhitti stvorenogo Konveyem modeli klitinnogo avtomata OpisNatyurmorti konfiguraciyi Zhittya abo inshogo klitinnogo avtomata yaki ne zminyuyutsya v procesi evolyuciyi Inshimi slovami natyurmort ye periodu 1 Terminologiya natyurmorti i psevdonatyurmortiIsnuye dekilka blizkih za zmistom terminiv sho oznachayut konfiguraciyi yaki ne zminyuyutsya v procesi evolyuciyi konfiguraciyi sho ye vlasnimi batkami Vidminnosti mizh nimi pov yazani z vidpoviddyu na nastupni pitannya Chi vvazhayetsya natyurmortom konfiguraciya sho skladayetsya z dvoh nezalezhnih natyurmortiv napriklad dvoh na dosit velikij vidstani odin vid odnogo Chi vvazhayetsya natyurmortom konfiguraciya yaka skladayetsya z dvoh chastin bud yaku z yakih mozhna vidaliti tak sho druga chastina zalishitsya batkom sobi V isnuyuchih slovnikah i onlajn enciklopediyah navodyatsya nastupni viznachennya Stijkij zrazok angl stable pattern ob yekt yakij ye vlasnim batkom Natyurmort angl still life strict still life stijkij ob yekt sho ye i neporozhnim yakij ne mozhe buti rozdilenij na dvi stijki chastini Psevdonatyurmort angl pseudo still life stijkij ob yekt sho ne ye natyurmortom v yakomu prisutnya hoch bi odna mertva klitina sho maye bilshe troh susidiv vsogo ale menshe troh susidiv u kozhnomu iz skladovih ob yekt natyurmortiv Tochne viznachennya stijkosti predstavlyaye interes v konteksti pererahuvannya natyurmortiv napriklad zgidno z privedenimi viznachennyami kilkist stijkih konfiguracij rozmiru 8 tobto takih sho skladayutsya z 8 zhivih klitin v Zhitti neskinchenno oskilki para na bud yakij vidstani odin vid odnogo ye stijkim prote kilkist natyurmortiv obmezhenogo rozmiru vvazhayetsya kincevoyu Psevdonatyurmort u Zhitti Viddalenist odnogo z ostroviv ne vplivaye na stabilnist drugogo ostrova Strogij natyurmort Stabilnist kozhnogo z ostroviv zalezhit vid nayavnosti drugogo ostrova Vidome chislo natyurmortiv i psevdonatyurmortiv rozmiru ne vishe 24 klitin Zadacha viznachennya tipu stijkosti konfiguraciyi natyurmort psevdonatyurmort virishuyetsya za polinomialnij chas shlyahom poshuku cikliv u zv yazanomu kososimetrichnomu grafi Natyurmorti u Zhitti U Zhitti isnuye mnozhina prirodnih natyurmortiv Prosti prikladi Blok Najbilsh poshirenij natyurmort blok konfiguraciya u formi kvadrata 2 2 Dva bloki rozmisheni v pryamokutniku 2 5 utvoryuyut bi blok prostij psevdonatyurmort Bloki vikoristovuyutsya yak skladovi chastini u bezlichi skladnih pristroyiv napriklad do Blok Bi blok Vulik Drugij za poshirennyam natyurmort vulik angl hive beehive Vuliki chasto vinikayut chetvirkami v konfiguraciyi sho nazivayetsya pasikoyu angl honey farm Vulik Pasika Korovaj Tretij po poshirenostti natyurmort korovaj angl loaf Korovayi neridko z yavlyayutsya parami angl bi loaf V svoyu chergu podvijni korovayi takozh z yavlyayutsya v parah zvanih pekarnyami angl bakery Korovaj Podvijnij korovaj Pekarnya Yashiki barzhi chovni korabli Yashik angl tub skladayetsya z chotiroh zhivih klitin v okolici fon Nejmana centralnoyi mertvoyi klitini Dodavannya odniyeyi zhivoyi klitini po diagonali do centralnoyi klitini peretvoryuye yashik na choven angl boat a dodavannya simetrichno she odniyeyi klitini na korabel angl ship Prirodne podovzhennya cih troh konfiguracij daye barzhu angl barge dovgij choven angl long boat i dovgij korabel angl long ship vidpovidno Podovzhennya mozhna prodovzhuvati skilki zavgodno dovgo Zliva napravo yashik barzha dovga barzha Zliva napravo choven dovgij choven Zliva napravo korabel dovgij korabel Z dvoh chovniv mozhna sklasti she odin natyurmort chovnikovij bant angl boat tie a z dvoh korabliv korabelnij bant angl ship tie Chovnikovij bant Korabelnij bant Inshi natyurmorti KanoeKanoe AvianosecAvianosec Znak integraluZnak integralu Mango SigaraMango Sigara StavokStavok ZmiyaZmiya Pozhirachi i vidbivachi Div takozh Natyurmorti mozhlivo vikoristati dlya modifikaciyi abo rujnuvannya inshih ob yektiv Pozhirach angl eater zdatnij znishiti i vidnovitisya pislya reakciyi angl reflector zamist znishennya kosmichnogo korablya zminyuye jogo kurs Vidbivachi i pozhirachi ne obov yazkovo povinni buti natyurmortami PozhirachiRibolovnij gachok pozhirach 1Ribolovnij gachok pozhirach 1 Pozhirach 2Pozhirach 2 Maksimalna shilnist Zadacha rozmishennya v oblasti n n natyurmorta z maksimalnim chislom klitin privertala do sebe uvagu programistiv yak zadacha Programuvannya v obmezhennyah Pri spryamuvannya rozmiru oblasti do neskinchennosti zhivimi mozhut buti ne bilshe 50 klitin Na obmezhenih kvadratnih oblastyah mozhlivo dosyagti bilshih shilnostej Tak maksimalna shilnist natyurmorta v kvadrati 8 8 dorivnyuye 36 64 0 5625 cyu shilnist zabezpechuye zrazok sho skladayetsya z dev yati blokiv Dlya kvadrativ do 20 20 vidomi optimalni rishennya Natyurmorti maksimalnoyi shilnosti u Zhitti 19x1919x19 20x2020x20 Chislo natyurmortivChislo natyurmortiv i psevdonatyurmortiv v Zhitti vidomo do rozmira v 24 klitini Chislo zhivih klitin Chislo natyurmortiv Prikladi1 02 03 04 2 blok yashik5 1 choven6 5 barzha avianosec vulik korabel zmiya7 4 ribolovnij gachok korovaj dovgij choven8 9 kanoe mango dovga barzha stavok9 10 znak integralu10 25 chovnikovij bant11 4612 121 korabelnij bant13 24014 619 podvijnij korovaj15 135316 328617 777318 1904419 45759 pozhirach 220 11224321 27318822 67217223 164614724 4051711Resursi InternetuNikolaj Belyuchenko Slovar Zhizni originalu za 10 zhovtnya 2012 Procitovano 4 serpnya 2017 Stephen A Silver Arhiv originalu za 26 travnya 2013 Procitovano 4 serpnya 2017 PrimitkiBilsh strogi viznachennya div u rozdili Terminologiya Ustojchivyj Slovar Zhizni Life Lexicon Arhiv originalu za 20 lyutogo 2009 Procitovano 4 serpnya 2017 Eric Weisstein Still Life Treasure Trove of Life C A Procitovano 11 serpnya 2013 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite web title Shablon Cite web cite web a Obslugovuvannya CS1 Storinki z parametrom url status ale bez parametra archive url posilannya Yaksho vidpovid na ce pitannya pozitivna to kilkist natyurmortiv z obmezhenim chislom klitin neskinchenna Nikolaj Belyuchenko Slovar Zhizni ros originalu za 10 zhovtnya 2012 Procitovano 4 serpnya 2017 Stephen A Silver angl Arhiv originalu za 26 travnya 2013 Procitovano 4 serpnya 2017 Still life ConwayLife com Procitovano 11 serpnya 2013 Natyurmort Slovar Zhizni Life Lexicon Arhiv originalu za 20 lyutogo 2009 Procitovano 4 serpnya 2017 Psevdonatyurmort Slovar Zhizni Life Lexicon Arhiv originalu za 3 grudnya 2014 Procitovano 4 serpnya 2017 Cook Matthew 2003 Still life theory New Constructions in Cellular Automata Santa Fe Institute Studies in the Sciences of Complexity Oxford University Press s 93 118 Prirodnij zrazok ob yekt yakij vidnosno chasto vinikaye v procesi rozvitku vipadkovoyi konfiguraciyi Achim Flammenkamp Top 100 of Game of Life Ash Objects Procitovano 5 listopada 2008 Igra Zhizn obzor Gardnera originalu za 18 zhovtnya 2012 Procitovano 11 serpnya 2013 Klumova I N Igra Zhizn Kvant 1974 9 S 26 30 Pekarnya Slovar Zhizni Ne plutati z Bosch R A 1999 Integer programming and Conway s game of Life SIAM Review 41 3 594 604 doi 10 1137 S0036144598338252 Bosch R A 2000 Maximum density stable patterns in variants of Conway s game of Life Operations Research Letters 27 1 7 11 doi 10 1016 S0167 6377 00 00016 X Smith Barbara M 2002 Principles and Practice of Constraint Programming CP 2002 Lecture Notes in Computer Science 2470 Springer Verlag 89 94 doi 10 1007 3 540 46135 3 27 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite journal title Shablon Cite journal cite journal a Proignorovano contribution dovidka Bosch Robert Trick Michael 2004 Constraint programming and hybrid formulations for three Life designs Annals of Operations Research 130 1 4 41 56 doi 10 1023 B ANOR 0000032569 86938 2f Cheng Kenil C K Yap Roland H C 2006 Applying ad hoc global constraints with the case constraint to still life Constraints 11 2 3 91 114 doi 10 1007 s10601 006 8058 9 Elkies Noam D 1998 The still life density problem and its generalizations Voronoi s Impact on Modern Science Book I Proc Inst Math Nat Acad Sci Ukraine vol 21 s 228 253 arXiv math CO 9905194 J Larrosa E Morancho and D Niso 2005 Journal of Artificial Intelligence Research 23 421 440 Arhiv originalu za 16 lipnya 2011 Neil Yorke Smith Maximum Density Still Life Artificial Intelligence Center SRI International Number of stable n celled patterns still lifes in Conway s game of Life Number of n celled pseudo still lifes in Conway s game of Life Niemiec Mark D Arhiv originalu za 21 sichnya 2013 Procitovano 4 serpnya 2017