Алгоритм Бога

Алгори́тм Бо́га — термін, який з'явився у зв'язку з обговоренням способів вирішення кубика Рубіка. Термін може також бути використаний у відношенні до інших перестановочних головоломок. Під алгоритмом Бога головоломки розуміється будь-який алгоритм, котрий дозволяє отримати рішення головоломки, яке містить мінімально можливе число ходів (оптимальне рішення), починаючи з будь-якої заданної конфігурації.

Один із піонерів математичної теорії кубика Рубіка Девід Сінгмастер^[1] описує появу терміну таким чином:

Джон Конвей, один з найбільших спеціалістів по теорії груп у світі, відмітив, що Кубик Рубіка підпорядковується так званим законам збереження (або парності), а це означає, що деякі рухи просто неможливі. Конвей або один із його колег в Кембриджі визначив найкоротший шлях з будь-якого даного стану назад до початкового стану як «Алгоритм Бога».

[

— Девид Сінгмастер

Визначення

Алгоритм Бога може існувати для головоломок з кінцевим числом можливих конфігурацій і з кінцевим набором «ходів», які допускаються у кожній конфігурації і які переводять поточну конфігурацію в іншу. Термін «розв'язати головоломку» означає — вказати послідовність ходів, що переводять деяку початкову конфігурацію в деяку кінцеву конфігурацію. Оптимально вирішити головоломку — вказати найкоротшу послідовність ходів для вирішення головоломки. Оптимальних рішень може бути декілька.

До відомих головоломок, які підпадають під це визначення, належать кубик Рубіка, Ханойська вежа, П'ятнашки, Солітер з фішками (англ.), різні завдання про переливання та перевезення («Вовк, коза і капуста»). Спільним для всіх цих головоломок є те, що вони можуть бути описані у вигляді графа, вершинами якого є всілякі конфігурації головоломки, а ребрами — допустимі переходи між ними («ходи»).

У багатьох подібних головоломках кінцева конфігурація негласно передбачається, наприклад, в «п'ятнашках» — впорядковане розташування кісточок, для кубика Рубіка — однокольоровість граней. У цих випадках «зібрати головоломку» означає, що потрібно для довільної початковій конфігурації вказати послідовність ходів, що приводять у фіксовану кінцеву конфігурацію.

Алгоритм вирішує головоломку, якщо він приймає в якості вихідних даних довільну пару початкової та кінцевої конфігурацій (або тільки початкову конфігурацію, якщо кінцева конфігурація зафіксована) і повертає в якості результату послідовність ходів, що переводять початкову конфігурацію в кінцеву (якщо така послідовність існує, в іншому випадку, алгоритм повідомляє про неможливість рішення). Оптимальне рішення містить мінімально можливу кількість ходів.

Тоді алгоритм Бога (для даної головоломки)  — це алгоритм, який вирішує головоломку і знаходить для довільної пари конфігурацій хоча б одне оптимальне рішення.

Деякі автори вважають, що алгоритм Бога повинен також бути практичним, тобто використовувати розумний обсяг пам'яті і завершуватися в розумний час.

Нехай G — група перестановочної головоломки (із заданою породжуючою множиною), v — вершина графа Келі групи G. Знайти ефектнивний, практичний алгоритм для визначення шляху із v до вершини v₀, пов'язану з нейтральним елементом, довжина якого дорівнює відстані від v до v₀. […] Цей алгоритм називається алгоритмом Бога.

[розгорнути]

Оригінальний текст (англ.)

— Девід Джойнер^[2]

Приктичність можна розуміти по-різному. Так, існують комп'ютерні програми, які дозволяють за прийнятний час знайти оптимальне рішення для довільної конфігурації кубика Рубіка^[3]. Водночас аналогічна задача для кубика 4 × 4 × 4 на даний момент залишається практично нездійсненною^[4][5][6]. Для деяких головоломок існує стратегія, що дозволяє відповідно до простих правил визначити оптимальне рішення вручну, без допомоги комп'ютера.

Альтернативне визначення алгоритму Бога: від алгоритму не потрібно знаходження всієї послідовності ходів; замість цього достатньо знайти перший хід оптимального рішення, що наближує до мети і переводить в нову конфігурацію. Два визначення є еквівалентними: повторне застосування алгоритму до нової пари конфігурацій знову знаходить хід оптимального рішення, що дозволяє отримати всю послідовність ходів оптимального рішення.

Число Бога

Числом Бога даної головоломки називається число n, таке, що існує хоча б одна конфігурація головоломки, оптимальне рішення якої складається з n ходів, і не існує жодної конфігурації, довжина оптимального вирішення якої перевищує n. Іншими словами, число Бога — це точна верхня грань множини довжин оптимальних рішень конфігурацій головоломки.

Число Бога для кубика Рубіка дорівнює 20 — це діаметр графа Келі групи кубика Рубіка^[7].

У загальному випадку (для довільної перестановною головоломки), число Бога дорівнює не діаметру графа Келі групи головоломки, а ексцентриситету вершини, відповідної «зібраному» стану головоломки.

Приклади

• Кубик Рубіка 3×3×3 завжди може бути вирішене не більше ніж в 20 ходів^[8]. Відомі конфігурації(англ.), вимагають для збірки не менше 20 ходів. Таким чином, «число Бога» кубика Рубіка дорівнює 20.

• Число Бога кубика Рубіка 2 × 2 × 2 дорівнює 11 ходам, якщо поворот грані на 180° вважається за 1 хід, або 14 ходам, якщо поворот грані на 180° вважається за 2 ходи. Невелика (3674160) кількість конфігурацій кубика Рубіка 2 × 2 × 2 дозволило обчислити алгоритм Бога (у вигляді оптимального рішення для кожної конфігурації) ще в 80-х роках^[9].

• Число Бога пірамідки Мефферта дорівнює 11^[10].

• Триколірний кубик — кубик Рубіка, протилежні грані якого пофарбовані однаково. Число конфігурацій триколірного кубика дорівнює

У березні-квітні 2012 року було встановлено, що число Бога триколірного кубика дорівнює 15 FTM, 17 QTM або 14 STM (згідно метриці STM, поворот будь-якого середнього шару також вважається за 1 хід)^[11].

• П'ятнашки можуть бути вирішені в 80 «коротких»^[12] або 43 «довгих»^[13] ходів в гіршому випадку (під «короткими» ходами маються на увазі переміщення окремих кісточок, а під «довгими» — переміщення цілих рядів з 1, 2 або 3 кісточок). Для узагальнених пятнашек (з більшим, ніж 15, кількістю кісточок) завдання пошукунайкоротшого рішення є NP-повної^[14].

• Для Ханойської вежі алгоритм Бога існує при будь-якій кількості дисків, але з додаванням дисків число ходів зростає експоненціально^[15].

Див. також

• Алгоритм Судного дня
• Кубик Рубіка
• Пірамідка Мефферта

Тренувальний тест: «Системи управління базами даних»

Тренувальний  тест: «Системи управління базами даних»

           База даних призначена для:

а) зберігання і впорядкування інформації;

б)  ведення розрахунково-обчислювальних операцій;

в)  обробки текстової інформації;

г)  обробки графічної інформації.
------------------------------

     Звіти БД створюються для:

а)  введення даних;

б) виводу даних на друк;

в) вибірки інформації;

г)  копіювання даних.
------------------------------------------

 Складіть тестове завдання з теми БД (4 варіанти вибору, правильну підкресліть).

Який тип має поле, в якому задається номер за порядком записів?
------------------------------------------------

--------------------------------------------------------
 Вкажіть порядок записів після сортування використовуючи команду по спаданню :

1.      Горбатюк

2.      Гірченко

3.      Губко

4.      Гурко

5.      Ганзюк
------------------------------------------

 Дано таблицю даних:

№	Область	Населення (млн. чол.)	Площа (тис. км2)
1.	Вінницька	1,83	26,5
2.	Волинська	1,06	20,2
3.	Дніпропетровська	3,74	31,9
4.	Донецька	5,00	26,5
5.	Житомирська	14,4	29,9

А) Яка кількість полів?

Б) Яка кількість записів?

В) Вкажіть атрибути поля №

Г) Яка кількість цілих числових полів?
------------------------------------------------------------
 Складіть структуру і тип даних до бази даних «Магазини» із трьох звязаних таблиць. 

--------------------------------------------------

  Який вид БД існує насправді?

А) Музикологічний.

Б) Фактографічний.

В) Симпатичний.

Г) Кінологічний.

Д) Специфічний.
--------------------------------------
Для чого потрібні форми при роботі з БД?

А) Для відбору інформації з БД за певною умовою.

Б) Для сортування інформації в БД.

В) Для пошуку інформації в БД.

Г) Для більш зручного та ефективного виведення інформації БД.
---------------------------------------

Складіть тестове завдання (4 варіанти вибору, правильну підкресліть).

Як називається програма для створення та роботи з БД?
-------------------------------------------------------

Дайте відповідь на питання. Що таке сортування? Які види сортування вам відомі?
--------------------------------------------------------------

Вкажіть порядок записів після сортування використовуючи команду зростання :

1.      Деркач

2.      Дірченко

3.      Дубко

4.      Дурко

5.      Данилюк
-----------------------------------------------------

 Дано таблицю даних:

А) Яка кількість полів?

Б) Яка кількість записів?

В) Вкажіть атрибути поля Прізвище.

Г) Яка кількість не цілих числових і текстових полів?

Дата	Прізвище	Товар	Цінаодного товару	Кількість	Загальна сума
3.04.2004	Семенова І.І.	Плащ	400	200	80000
15.06.2005	Петренко А.Н.	Пальто	600	122	73200
22.03.2006	Костенко О.Р.	Колготи	50	333	1665
2.02.2006	Іванов К.Т.	Плаття	350	656	229600
5.07.2007	Коршун В.В.	Чобітки	500	200	100000

--------------------------------------------------------------------
 Складіть структуру і тип даних до бази даних «Пісні» з трьох звязаних таблиць
-----------------------------------------------------------

Який тип має поле, в якому задається номер за порядком записів?

А) Текстовий.

Б) Лічильник.

В) Числовий.

Г) Грошовий.
-----------------------------------------------------------
Як називається стовбець таблиці БД?

А) Форма.

Б) Запис.

В) Запит.

Г) Поле.
-----------------------------------------------------------

 Складіть тестове завдання (4 варіанти вибору, правильну підкресліть).

Перерахуйте основні типи (моделі) баз даних.
------------------------------------------------------------------------------

 Дайте відповідь на питання. Поясніть призначення програми Access?
-----------------------------------------------------------------------------------

Вкажіть порядок записів після сортування використовуючи команду зростання :

1.      Яштюк

2.      Ярченко

3.      Яблуня

4.      Ягель

5.      Янзюк
-----------------------------------------------------------

 Дано таблицю даних:

Дата	Хто відповідав	З якого предмету	Тривалість відповіді у таблицях	Оцінка оголошена вчителем	Чи дізналися ви з відповіді про що-небудь нове (Так/ні)
5.04 5.04 5.04 6.04 6.04 6.04	Носова А. Базь Н. Стоян Ф. Кіяшко Б. Базь Н. Лешко Л.	Хімія Фізика Фізика Література Література Географія	4 3 5 6 5 3	3 5 4 4 4 3	Ні Ні Так Ні Так Так

А) Яка кількість полів?

Б) Яка кількість записів?

В) Вкажіть атрибути поля Дата

Г) Яка кількість цілих числових полів?

--------------------------------------------------------------
Складіть структуру і тип даних до бази даних «Предмет в школі» з чотирьох таблиць.
-------------------------------------------------------------------------------------------

Поле в базі даних це:

a)    рядочок;

b)   стовпчик;

c)    комірка;

d)   таблиця
-----------------------------------------------

Бази даних використовуються для:

a)    збереження даних;

b)   знищення даних;

c)    оновлення даних;

d)   розподілу даних.
-----------------------------------------

Складіть тестове завдання (4 варіанти вибору, правильну підкресліть).

Для чого потрібні звіти в БД?
----------------------------------------
Дайте відповідь на питання. Яку інформацію розміщують в полях типу "лічильник"?
---------------------------------------------

 Вкажіть порядок записів після сортування використовуючи команду спадання :

1.      Юрчик

2.      Юрин

3.      Юнюк

4.      Юлель

5.      Юнзюк
--------------------------------------------

 Дано таблицю даних:

Дата	Хто відповідав	З якого предмету	Тривалість відповіді у таблицях	Оцінка оголошена вчителем	Чи дізналися ви з відповіді про що-небудь нове (Так/ні)
5.04 5.04 5.04 6.04 6.04 6.04	Носова А. Базь Н. Стоян Ф. Кіяшко Б. Базь Н. Лешко Л.	Хімія Фізика Фізика Література Література Географія	4 3 5 6 5 3	3 5 4 4 4 3	Ні Ні Так Ні Так Так

А) Яка кількість полів?

Б) Яка кількість записів?

В) Вкажіть атрибути поля Оцінка оголошена вчителем

Г) Яка кількість цілих числових полів?
------------------------------------------------------

 Складіть структуру і тип даних до бази даних «Країни Східної Європи» з трьох таблиць.
---------------------------------------------------

Запис в базі даних це:

A.    рядочок;

B.     стовпчик;

C.     комірка;

D.    таблиця
---------------------------------------------

Програма Microsoft Access запускається так:

a)    Пуск/Програми/Стандартные/Microsoft Access;

b)   Пуск/Програми/Microsoft Access;

c)    ПКМ/ Microsoft Access;

d)   Пуск/ Microsoft Access.
--------------------------------------

Складіть тестове завдання (4 варіанти вибору, правильну підкресліть).

Що таке форма?
--------------------------------------------------------

Дайте відповідь на питання. Що означає розробити структуру бази даних?
-------------------------------------------------

Вкажіть порядок записів після сортування використовуючи команду зростання :

1.      Урчик

2.      Урин

3.      Угнюк

4.      Уздель

5.      Учнюк
--------------------------------------

Дано таблицю даних:

Дата	Номер магазину	Прізвище товарознавця	Найменування товару	Ціна одиниці товару	Кількість товару (одиниць)	Загальна сума товару
3/04/97 3/04/97 4/04/97 4/04/97 5/04/97 6/04/97	245 101 91 105 91 77	Семенова І.І. Петренко А.Н. Чебик Ф.А. Огурцов П.Н. Чебик Ф.А. Семенова І.І.	Плащ жіночий Пальто чоловіче Зонт дамський Туфлі чоловічі Плаття жіноче Дитячі колготки	70 150 20 80 50 5	120 50 90 75 100 150	8400 7550 1800 6000 5000 750

А) Яка кількість полів?

Б) Яка кількість записів?

В) Вкажіть атрибути поля Ціна одиниці товару

Г) Яка кількість цілих числових полів?
---------------------------------------------

Складіть структуру і тип даних до бази даних «Паспорт»
----------------------------------------------

Яке розширення мають файли в БД?

А) .xls

Б) .doc

В) .mbd

Г) .mpp

Д) .sys
----------------------------------------

До якого виду можна віднести БД учнів в класному журналі?

А) До документальної.

Б) До ієрархічної.

В) До фактографічної.

Г) До монументальної.
------------------------------------------

Складіть тестове завдання (4 варіанти вибору, правильну підкресліть). Призначення програми Access?
-----------------------------------

Дайте відповідь на питання. Яке поле може бути ключовим? Для чого використовують ключові поля?
-----------------------------------------------------

Вкажіть порядок записів після сортування використовуючи команду  зростання:

1.      Антонюк

2.      Антошкін

3.      Антонов

4.      Аннеков

5.      Антипчук
------------------------------------------

Дано таблицю даних:

Дата	Хто відповідав	З якого предмету	Тривалість відповіді у таблицях	Оцінка оголошена вчителем	Чи дізналися ви з відповіді про що-небудь нове (Так/ні)
5.04 5.04 5.04 6.04 6.04 6.04	Носова А. Базь Н. Стоян Ф. Кіяшко Б. Базь Н. Лешко Л.	Хімія Фізика Фізика Література Література Географія	4 3 5 6 5 3	3 5 4 4 4 3	Ні Ні Так Ні Так Так

А) Яка кількість полів?

Б) Яка кількість записів?

В) Вкажіть атрибути поля Хто відповідав.

Г) Яка кількість логічних полів?
------------------------------

Складіть структуру і тип даних до бази даних «Державна підсумкова атестація у 9 класі»
-------------------------------
 База даних призначена для:

а) зберігання і впорядкування інформації;

б)  ведення розрахунково-обчислювальних операцій;

в)  обробки текстової інформації;

г)  обробки графічної інформації.
-------------------------------------

Звіти створюються для:

а)  введення даних;

б) виводу даних на друк;

в) вибірки інформації;

г)  копіювання даних.
----------------------------------------

Складіть тестове завдання (4 варіанти вибору, правильну підкресліть).

Який тип має поле, в якому задається номер за порядком записів?
-----------------------------------
 Дайте відповідь на питання. Для чого призначені таблиці в Access?
--------------------------------------------------

Вкажіть порядок записів після сортування використовуючи команду спадання :

1)      Горбатюк

2)      Гірченко

3)      Губко

4)      Гурко

5)      Ганзюк
-------------------------------

Дано таблицю даних:

№	Область	Населення (млн. чол.)	Площа (тис. км2)
6.	Вінницька	1,83	26,5
7.	Волинська	1,06	20,2
8.	Дніпропетровська	3,74	31,9
9.	Донецька	5,00	26,5
10.	Житомирська	14,4	29,9

А) Яка кількість полів?

Б) Яка кількість записів?

В) Вкажіть атрибути поля №

Г) Яка кількість цілих числових полів?

----------------------------------------------------

 Складіть структуру і тип даних до бази даних «Супермаркети Вінниці»
----------------------------------------------

Для чого потрібні звіти в БД?

А) Для зручного введення інформації в БД.

Б) Для посилання потрібної інформації БД по мережі.

В) Для відбирання інформації з БД за умовою.

Г) Для сортування інформації в БД.

Д) Для зручного згрупування та виведення інформації БД на друк.
------------------------------------------------

Яких типів баз даних не буває:

a)      ієрархічної;

b)      мережної;

c)      структурної;

d)     реляційної.
---------------------------------------------

Складіть тестове завдання (4 варіанти вибору, правильну підкресліть). Яку інформацію розміщують в полях логічного типу?
-------------------------------------------------------

Дайте відповідь на питання. Для чого призначені запити в Access?
-------------------------------------------------------------

Вкажіть порядок записів після сортування використовуючи команду :

1.      Джміль

2.      Джусюк

3.      Джон

4.      Джек

5.      Джок
------------------------------

Дано таблицю даних:

Код гуртка	Назва	Опис	Вартість
Ш-1	Інтеграл	Математичний	10,00
М-2	Нотка	Хор	7,50
П-4	Юний  технік	Радіотехнічний	15,00

А) Яка кількість полів?

Б) Яка кількість записів?

В) Вкажіть атрибути поля Вартість.

Г) Яка кількість тексових полів?
-----------------------------------------------
Складіть структуру і тип даних до бази даних «Вокзали Вінниці»
------------------------------------------------

    Запис в базі даних це:

A.    рядочок;

B.     стовпчик;

C.     комірка;

D.    таблиця
-------------------------------

Як називаються інформаційні структуровані одиниці, які складаються з полів:

а)  файли даних;

б)  бази даних;

в)  поля;

г)  записи.
-----------------------------------------

Складіть тестове завдання (4 варіанти вибору, правильну підкресліть). Для чого призначені форми в Access?

 Дайте відповідь на питання. Назвіть відомі вам види фільтрів в Access.
------------------------------------------------------

5. Вкажіть порядок записів після сортування використовуючи команду зростання :

1.      Ірчик

2.      Ірин

3.      Інюк

4.      Ілюк

5.      Індюк
--------------------------------------

 Дано таблицю даних:

Успішність : таблиця
Шифр	Код Оцінки	Код Учня	КодПред	Дата	Оцінка
Ф	1	Бондаренко	Фізика	02.09.2004	5
К	2	Бондаренко	Фізика	12.09.2004	6
П	3	Бондаренко	Фізика	12.10.2004	10
Р	4	Бондаренко	Хімія	23.10.2004	9
В	5	Бондаренко	Хімія	03.10.2004	11

А) Яка кількість полів?

Б) Яка кількість записів?

В) Вкажіть атрибути поля Оцінка

Г) Яка кількість нечислових полів?
-----------------------------------------
 Складіть структуру і тип даних до бази даних «Музеї Вінниці»
--------------------------------------------------------

 Текстове поле дозволяє занести інформацію до:

а)  20 символів;

б)  1 символу;

в)  256 символів;

г)  65536 символів.
---------------------------------------------

Кнопка „Конструктор" відкриває:

а)  вміст таблиці;

б)  структуру об'єкта;

в)  панель елементів;

г)  файл доповнення бази даних.
---------------------------------------

 Складіть тестове завдання (4 варіанти вибору, правильну підкресліть). Які типи даних вам відомі?
---------------------------------------

Дайте відповідь на питання. Що спільного і відмінного у текстовому полі і полі МЕМО?
-------------------------------------------------------------------------------

Вкажіть порядок записів після сортування використовуючи команду спадання :

1.    Катя

2. Катерина

3. Кет

4. Катруся

5. Катеринка
---------------------------------------

Дано таблицю даних:

Успішність : таблиця
Шифр	Код Оцінки	Код Учня	КодПред	Дата	Оцінка
Ф	1	Бондаренко	Фізика	02.09.2004	5
К	2	Бондаренко	Фізика	12.09.2004	6
П	3	Бондаренко	Фізика	12.10.2004	10
Р	4	Бондаренко	Хімія	23.10.2004	9
В	5	Бондаренко	Хімія	03.10.2004	11

А) Яка кількість полів?

Б) Яка кількість записів?

В) Вкажіть атрибути поля Шифр

Г) Яка кількість цілих полів?
---------------------------------------------
 Складіть структуру і тип даних до бази даних «Телефона книга»

-----------------------------------------------

Таблиці служать для:

а)  ведення розрахунків;

б)  збереження інформації

в)   вибірки інформації;

г)  виводу на друк.
--------------------------------------------

Для оформлення потрібних даних з бази даних згідно з вимогами стандартів чи замовника і виведення їх на папір призначені:

а)  форми;

б)  звіти;

в)  запити;

г)  фільтри.
--------------------------------------------------------------

Складіть тестове завдання (4 варіанти вибору, правильну підкресліть). Що таке файл бази даних?
---------------------------------------------------

 Дайте відповідь на питання. Що означає грошове поле бази даних?
-------------------------------------------------

 Вкажіть порядок записів після сортування використовуючи команду :

1)      Василь

2)      Василько

3)      Вася

4)      Васько

5)      Васька
--------------------------------------

 Складіть структуру і тип даних до бази даних «Атестат про освіту»
----------------------------------------------------------------

 Структура таблиці в БД Ассеss – це...

а)  сукупність полів;

б)  структура запису;

в)  сукупність типів;

г)  сукупність властивостей.
---------------------------------------------

Що треба зробити для створення БД в першу чергу?

а)  створити її на папері;

б)  визначити вхідні дані;

в)  визначити тип даних;

г)  перелічити всі типи даних.
------------------------------------------

 Складіть тестове завдання (4 варіанти вибору, правильну підкресліть). Що називають рядком бази даних?
---------------------------------------------------------

Дайте відповідь на питання. Як називається режим роботи, в якому задається структура таблиці?
----------------------------------------

Вкажіть порядок записів після сортування використовуючи команду :

1)      Іванов

2)      Івасюк

3)      Іванюк

4)      Іванчук

5)      Іваськіна
-----------------------------------------------

----------------------------------------

 Складіть структуру і тип даних до бази даних «Програма передач на TV»
----------------------------------------------