124 lines
5.9 KiB
Markdown
124 lines
5.9 KiB
Markdown
# Лабораторная работа: Клеточные автоматы
|
||
|
||
# Университет ИТМО
|
||
**Студент:** Владимиров Владислав Александрович
|
||
**Группа:** P3322\
|
||
**Дата:** 15.05.2026
|
||
|
||
## Цель работы
|
||
|
||
Изучение принципов функционирования и приобретение навыков программной реализации клеточных автоматов как дискретных вычислительных моделей.
|
||
|
||
## Диаграмма классов
|
||
|
||
```
|
||
AppState
|
||
|-- config: AppConfig
|
||
|-- action: UiAction?
|
||
|
||
AppConfig (serializable)
|
||
|-- mode: AutomatonMode
|
||
|-- gridWidth: Int
|
||
|-- gridHeight: Int
|
||
|-- simulationSpeed: Int
|
||
|-- probability: Double
|
||
|-- oneDimensionalRule: OneDimensionalRule
|
||
|-- killAtBoundary: Boolean
|
||
|
||
AutomatonMode: GAME_OF_LIFE | ONE_DIMENSIONAL
|
||
OneDimensionalRule: RULE_30 | RULE_90 | RULE_110 | RULE_184
|
||
|
||
GameOfLife
|
||
|-- width: Int
|
||
|-- height: Int
|
||
|-- killAtBoundary: Boolean
|
||
|-- initialize(probability): void
|
||
|-- step(): Int
|
||
|-- getGrid(): Array<Array<Boolean>>
|
||
|-- getLiveCellCount(): Int
|
||
|-- toggleCell(x, y): void
|
||
|
||
OneDimensionalCA
|
||
|-- width: Int
|
||
|-- rule: OneDimensionalRule
|
||
|-- initialize(centerPosition): void
|
||
|-- initializeRandom(probability): void
|
||
|-- step(): BooleanArray
|
||
|-- getGenerations(count): List<BooleanArray>
|
||
|
||
PatternClassifier
|
||
|-- classifyPatterns(Array<Array<Boolean>>): List<PatternInfo>
|
||
|
||
ExperimentRunner
|
||
|-- runExperiments(width, height): List<ExperimentResult>
|
||
|-- generateGraph(results, outputPath): void
|
||
```
|
||
|
||
Взаимодействие: `Main.kt` -> `MainScreen` -> `Sidebar` + `GameOfLifeView` | `OneDimensionalView`. Конфигурация сохраняется в `config.json` через `ConfigRepository`.
|
||
|
||
## Визуализация эволюции автоматов
|
||
|
||
### Одномерный клеточный автомат (Rule 30, 90, 110)
|
||
|
||
Правило 30 генерирует хаотичный паттерн. Правило 90 создаёт фрактальный треугольник Серпинского. Правило 110 демонстрирует универсальные вычислительные свойства.
|
||
|
||
#### Rule 30
|
||
|
||
#### Rule 90
|
||
|
||
#### Rule 110
|
||
|
||
|
||
### Game of Life (Двумерный клеточный автомат)
|
||
|
||
Начальное заполнение: случайное (p = 0.3), поле 50x50, 100 поколений.
|
||
|
||
#### Стабилизация за 429 поколений
|
||
|
||
**Выявленные паттерны:**
|
||
|
||
| Тип | Название | Классификация |
|
||
|-----|----------|---------------|
|
||
| Block (2x2) | Блок | Устойчивая фигура |
|
||
| Beehive (3x3, 6 клеток) | Улей | Устойчивая фигура |
|
||
| Loaf (3x3, 5 клеток) | Буханка | Устойчивая фигура |
|
||
| Boat (3x2, 5 клеток) | Лодка | Устойчивая фигура |
|
||
| Glider (5 клеток) | Глайдер | Движущаяся фигура |
|
||
|
||
Глайдер перемещается по диагонали со скоростью c/4 (один шаг по диагонали каждые 4 поколения). Блок, улей, буханка и лодка остаются неизменными во всех поколениях. Бликер (3 клетки в линию, периодичность 2) — пример периодической фигуры.
|
||
|
||
## Результаты экспериментов
|
||
|
||
### Таблица времени стабилизации
|
||
|
||
| Плотность (p) | Среднее время стабилизации (поколений) |
|
||
|---------------|----------------------------------------|
|
||
| 0.10 | 460 |
|
||
| 0.15 | 580 |
|
||
| 0.20 | 618 |
|
||
| 0.25 | 634 |
|
||
| 0.30 | 621 |
|
||
| 0.35 | 642 |
|
||
| 0.40 | 622 |
|
||
| 0.45 | 632 |
|
||
| 0.50 | 639 |
|
||
|
||
Количество запусков на каждую плотность: 100. Размер поля: 50x50. Условие стабилизации: 10 поколений без изменения популяции (или циклические изменения между двумя значениями).
|
||
|
||
### График
|
||
|
||
|
||
|
||
График сохранён в файл `stabilization_graph.png`.
|
||
|
||
## Анализ результатов
|
||
|
||
При низкой плотности (p = 0.10) система стабилизируется быстро (460 поколений) из-за вымирания изолированных клеток. Большинство конфигураций умирает в первые 100-200 поколений.
|
||
|
||
Хаотическая фаза наблюдается при плотности p = 0.25-0.35, где время стабилизации достигает 620-640 поколений. При этих плотностях образуется максимальное количество взаимодействующих структур (глайдеры, ружья, блоки), что затягивает стабилизацию.
|
||
|
||
При высокой плотности (p = 0.45-0.50) время стабилизации остаётся высоким (630-640), однако причина отличается: образуются крупные устойчивые и периодические структуры (улей, блоки), которые переходят в стабильную фазу без вымирания. Система не "вымирает", а кристаллизуется в насыщенный паттерн.
|
||
|
||
Максимальное время стабилизации: p = 0.35 (642 поколения) и 0.5. Минимальное: p = 0.10 (460 поколений).
|
||
|
||
Исходный код доступен тут вот -> https://git.illegalfiles.icu/vlad.os/systems-lab2 |