Мультимедіа, крос-медіа, трансмедіа

Практична робота  

«Мультимедіа, крос-медіа, трансмедіа»

Завдання. Самостійно створити презентацію згідно сценарію.

СЦЕНАРІЙ УЧНІВСЬКОЇ  ПРЕЗЕНТАЦІЇ  

«Мультимедіа, крос-медіа, трансмедіа»

Слайд 1. Заголовок(розмір: 44 пт): Що таке  медіа? Підзаголовок(розмір: 32) пт): П.І.Б учня, котрий створює презентацію, клас, дата створення. Ілюстрації: анімовані фото зразків медіа: газет, книг, ЗМІ, ТВ. Анімація для переходу на другий слайд. Налаштувати кнопки для переходу на слайди

Слайд 2. Заголовок: Яке означення мультимедіа, яка їх класифікація? Текст(розмір: 22 пт): Означення.  Фактично поняття «мультимедіа» вживали задовго до появи Інтернету, адже мультимедійними є телебачення (поєднує звук і відео), традиційні газети та журнали (поєднують текст і зображення) тощо. Мережа стала своєрідним технічним середовищем для об’єднання різних способів комунікації і надала поняттю «мультимедіа» нового семантичного значення. Як слушно зазначає Р. Крейг, «не все, що блимає і гуде, є мультимедіа». Термін «мультимедіа» означає не лише технічне об’єднання різних видів контенту (текстового, звукового, графічного, фото- й відеоконтенту) в єдиному цифровому представленні з використанням відповідного програмного забезпечення, а й характеризує створення єдиного інтегрованого медіапродукту (мультимедійної презентації, мультимедійної книги, мультимедійних газети чи журналу, мультимедійного електронного ресурсу), в якому одні способи комунікації (аудіо, відеоматеріали, анімація) логічно продовжують інші (текст, зображення).  Ілюстрації: схема класифікацій мультимедіа(без анімації). Анімація для переходу на третій слайд.

Слайд 3. Заголовок: Яке означення терміну крос-медіа? Текст: Означення.  Крос-медіа — це просування  інтелектуальної власності, сервісу, історії або досвіду через різноманітні медіаплатформи з використанням різних медіаформатів. Отже, термін «крос-медіа», на відміну від «мультимедіа», позначає не конкретний медіапродукт, а здатність поширювати інформацію у переконливому, корисному та візуально привабливому вигляді за допомогою різних засобів комунікації. Такий розподіл медіаконтенту між кількома платформами фактично є використанням медіакомпаніями стратегії диверсифікації для отримання більших прибутків.  Ілюстрації: схема класифікації крос-медіа. Анімація для переходу на четвертий слайд.

Слайд 4. Заголовок: Які є крос-медійні стратегії? Текст: В епоху мережевих ЗМІ та інтерактивності розвиваються і стають складнішими кросмедійні стратегії, кросмедійне виробництво та кросмедійні комунікації. Геррі Гейс виокремлював чотири рівні кросмедіа: Сrossmedia 1.0, Сrossmedia 2.0, Сross - media 3.0 та Сrossmedia 4.0 [8]. Сrossmedia 1.0 — Pushed (висувати, штовхати). Однаковий або із незначними варіаціями контент розміщується («виштовхується», просувається) на різні медіаплатформи у різних форматах.

. Ілюстрації: послідовна швидка зміна трьох різних  скріншотів з різними сайтами новин. Анімація для переходу на п’ятий слайд.

Слайд 5. Заголовок: Як просувають медіа-контент для масового використання? Текст: Автор контенту спеціально структурує деяку  історію для передачі через різні медіаплатформи для підсилення впливу на аудиторію. Контент, розміщений на одній платформі, є своєрідним «містком», «подразником», який спонукає споживача перейти на іншу медіаплатформу. Наприклад, у статті в друкованому ЗМІ подають лише коротку інформацію та посилання на сайт, де можна ознайомитися з повною версією матеріалу. Crossmedia 4.0 — Experiences (досвід)  передбачає нелінійний розподіл контенту між багатьма платформами, створення умов своєрідної гри, коли учасник живе «всередині», обираючи власний шлях розвитку історії. Ілюстрації: послідовна швидка зміна трьох різних ефектів освітлення палітурки деякого видання. Анімація для переходу на 6 слайд.

Слайд 6. Заголовок: Які є рівні крос-медіа? Текст: Оскільки автор кросмедійного проекту повинен жити в історії разом зі своєю аудиторією і грати з аудиторією на її умовах. Норвезький вчений Івар Джон Ердал пропонує розрізняти кросмедійне виробництво та кросмедійну комунікацію, які відповідають внутрішньому (організаційному) і зовнішньому (аудиторному) вимірам кросмедіа. Внутрішній вимір крос-медіа описує виробничі процеси, режими організації та співпраці в медіаорганізації, яка працює для декількох платформ, а зовнішній вимір — процес комунікації з аудиторією, внаслідок якої створюються медіапродукти, орієнтовані на кроспросування, інтертекстуальність і повторне використання контенту. Різні значення, на думку Івара Джона Ердала, мають і поняття крос-медіа та мультиплатформність: мультиплатформність вказує на використання понад однієї медіаплатформи без комунікативних відносин чи взаємозв’язків між цими платформами, крос-медіа ж є розширенням мультиплатформності, коли різні медіаплатформи мають комунікативний зв’язок, «спілкуючись одна з одною».  Ілюстрації: швидке мигтіння реклами, як сигналізації про щось. Анімація для переходу на 7 слайд.

Слайд 7. Заголовок: Рівні реалізації крос-медіа. Текст: Перші два рівні відповідають мультиплатформному виробництву контенту, третій рівень описує внутрішній (організаційний) вимір кросмедіа — кросмедійне виробництво, а четвертий — зовнішній (аудиторний) вимір кросмедіа — кросмедійну комунікацію з споживачами контенту. Американський вчений Дрю Девідсон розглядає кросмедійну комунікацію як розповідь інтерактивної інтегративної історії із залученням різних ЗМІ, різних авторів та з використанням різних стилів. Ілюстрації: швидке мигтіння лампочки з написом «Вимкніть мене!» тобто робота смарттелевізора в кімнаті (це декілька послідовних анімаційних ефектів). Анімація для переходу на 8 слайд.

Слайд 8. Заголовок(з анімацією):  Яке означення терміну трансмедіа? Текст:  Дослідники медіа іноді ототожнює термін «крос-медіа» («крос-медійна комунікація») із терміном «трансмедіа», вперше використаним Генрі Дженкінсом на позначення розповіді певної історії за допомогою різноманітних медіаплатформ та медіаформатів, які дозволяють користувачу брати активну участь у створенні історії. Єдиною відмінністю трансмедіа від крос-медіа, на думку Дрю Девідсона, є акцент на інтерактивності. Більш слушною вбачається думка Індрека Ібруса та Карлоса А. Сколарі, які розрізняють поняття «крос-медіа» і «трансмедіа», пропонуючи формулу: «крос-медіа + наратив = транс - медіа».  Ілюстрації: анімоване зображення Smart-медіа, на якому змінюється показання пульсу користувача або спожиивача контенту: від 75 до 125 ударів за хвилину. Анімація для переходу на 9 слайд.

Слайд 9. Заголовок(з анімацією):  Smart-технології. Які функції розумного годинника? Текст:  Трансмедіа відображає єдину логіку мислення про потік контенту через різні засоби масової комунікації. Дослідниця Н. Соколова зазначає, що трансмедіа, які передбачають просування продукту чи бренду різноманітними каналами, на перший погляд схожі з інтегрованими маркетинговими комунікаціями та нагадують сучасну рекламну практику доставки рекламного контенту споживачам різними каналами (радіо, телебачення, мультфільми, Інтернет, мобільні телефони то - що), доповнення основного контенту «вірусним» тощо, проте, від маркетингових практик доставки мультимедійного контенту трансмедіа відрізняє існування особливого тематичного універсуму, цілісного вигаданого світу, «всесвіту», який створюється виразними засобами різних видів медіа. Ілюстрації: Схема організації трансмедіа. Анімація для переходу на 10 слайд.

Слайд 10. Заголовок(з анімацією):  Smart-гра з медіа контентом. Текст: Трансмедійне передбачає не просто розповідь за допомогою кількох ЗМІ, а й створення кількох пов’язаних тематично медіапродуктів, що забезпечує різні точки контакту з брендом. Наприклад, до написання романів «Метро 2033» та «Метро 2034» Дмитро Глухов ський залучав читачів, які мали змогу коментувати книжки, прогнозувати розвиток сюжету, допомагали з редактурою. Цей проект — яскравий приклад трансмедійного storytellinga, коли гра продовжує сюжет книжки, а наступна книжка буде продовжувати сюжет гри. Як слушно наголошує Генрі Дженкінс, трансмедіа виникає як наслідок об’єднання корпоративної та «низової» (grassroots) конвергенції. Медіакомпанії вчаться, як просувати медіаконтент за допомогою багатьох каналів для того, щоб максимально використати нові можливості та розширити ринок. Ілюстрації:  Титулка медіа-роману «Метро 2033». Анімація для переходу на 11 слайд.

Слайд 11. Заголовок: Яка різниця між крос-медіа і трансмедіа? Текст: Трансмедіа відрізняє від кросмедіа створення тематично цілісної історії та активна співучасть у творенні контенту так званих «інтерпретативних товариств» (визначення Н. Соколової), організованих авторами, медіа продюсерами, або утвореними стихійно. Трансмедійні проекти створюють за активної участі читачів.  Ілюстрації: бренди медіа-проект. Анімація для переходу на 12 слайд.

Слайд 12. Заголовок(з анімацією): Контроль над медійними проектами. Текст: Медіакомпанії уміють просувати медіаконтент за допомогою багатьох каналів для того, щоб максимально використати нові можливості та розширити ринок. Споживачі вчаться, як використовувати різні медіатехнології, щоб посилити свій контроль над медіа та взаємодіяти з іншими споживачами. Ілюстрації: бренди медіа компаній. Анімація для переходу на 13 слайд.

Слайд 13. Заголовок(з анімацією): Використані джерела. Текст: Інтернет портали з медіа сервісом. Ілюстрації: скріншот медіа сервісів.

Слайд 14. Заголовок(з анімацією): Як використати смартфон для медіа проекту? Текст: Інтернет портали з медіа сервісом. Ілюстрації: скріншот медіа сервісів.

Основні етапи створення моделі в програмуванні

http://www.ipai.net.ua/shevchenko-publishing

Задача 1. Козак Вус подарував вам набiр з n цифр (тобто чисел вiд 0 до 9 включно). I хоче дiзнатися у вас: яку максимальну кiлькiсть чисел з них можна скласти так, щоб кожне з них дiлилося на 3 та кожна цифра з набору була використана не бiльше 1 разу. Щоб скласти число, вам потрiбно вибрати будь-які цифри з набору, вибрати їхнiй порядок та скласти число з цих цифр. Звернiть увагу, що ви не зобов’язанi використати всi цифри. Ви ж не можете вiдмовити Вусу? :)

Маленька пiдказка вiд Математичної Сови:

Остача (залишок) вiд дiлення x на число 3 дорiвнює остачi вiд дiлення суми цифр числа x на число 3.

Число a є кратним числу b (тобто a дiлиться на b) лише, якщо остача вiд дiлення числа a на число b дорiвнює 0.

Технічні умови Програма Newnumbers читає з пристрою стандартного введення у першому рядку мiстить одне цiле число n (1 ⩽ n⩽5 · 105) — кiлькiсть цифр. У другому рядку записано n цiлих чисел, кожне з яких має значення вiд 0 до 9 включно. Програма виводить на пристрій стандартного виведення одне ціле число — максимальну кількість чисел кратних 3, що можна скласти з цього набору.

Приклади

Введення	Виведення
1 0	1
14 8 8 4 8 1 1 0 0 2 1 9 3 4 1	8

Зауваження до прикладів

У першому прикладі ми можемо скласти лише одне число 0.

У другому прикладі з цього набору ми можемо скласти максимум 8 чисел. Один iз можливих способів — це скласти такі числа: 0, 0, 48, 9, 3, 21, 81, 84. Невикористаними у нас залишаться цифри 1, 1.

Задача 2. Дано набiр з n цифр вiд 0 до 9 включно. Потрібно дiзнатися, яку максимальну кiлькiсть чисел з них можна скласти так, щоб кожне з них дiлилося на 3 та кожна цифра з набору була використана не бiльше 1 разу. Щоб скласти число, вам потрiбно вибрати будь-які цифри з набору, вибрати їх порядок та скласти число з цих цифр. Звернiть увагу, що ви не зобов’язані використати всi цифри.

Математична підказка:

·         Остача (залишок) вiд дiлення x на число 3 дорiвнює остачi вiд дiлення суми цифр числа x на число 3.

·         Число a є кратним числу b (тобто a дiлиться на b) лише, якщо остача вiд дiлення числа a на число b дорiвнює 0.

Технічні умови. Програма  читає з пристрою стандартного введення у першому рядку одне цiле число n (1 ⩽ n⩽5 · 10⁵) — кiлькiсть цифр. У другому рядку записано n цiлих чисел, кожне з яких має значення вiд 0 до 9 включно. Програма виводить на пристрій стандартного виведення одне цiле число — максимальну кiлькiсть чисел кратних 3, що можна скласти з цього набору.

Приклади

Введення	Виведення
1 0	1
14 8 8 4 8 1 1 0 0 2 1 9 3 4 1	8

Зауваження до прикладів

У першому прикладi ми можемо скласти лише одне число 0.

У другому прикладi з цього набору ми можемо скласти максимум 8 чисел. Один iз можливих способiв — це скласти наступнi числа: 0, 0, 48, 9, 3, 21, 81, 84. Невикористаними у нас залишаться цифри 1, 1.

Математична модель до завдання:

Максимальна кількість чисел обчислюється за формулою

n =p(0=mod3)+min(k(1=mod3); m(2=mod3))+(1/3)*(max(k(1=mod3); m(2=mod3) -min(k(1=mod3); m(2=mod3))

де p(0=mod3) - це кількість цифр, що кратні 3.;

k(1=mod3) -це кількість цифр, що мають вигляд 3х+1;

m(2=mod3)) - це кількість цифр, що мають вигляд 3х+2;

Кодування алгоритму на СІ++

#include <iostream>

#include <cmath>

using namespace std;

int main(){

long long kol, tsifra, ost;

cin >> kol;

long long n = 0, L = 0, m = 0;

for (long long i = 0; i < kol; i++){

cin >> tsifra;

ost = tsifra % 3;

if (ost == 0)

n = n + 1;

else if (ost == 1)

L = L + 1;

else

m = m + 1;

}

long long rez = n + min(L, m) + (max(L, m) - min(L,m))/3;

cout << rez;

}

                Кодування алгоритму на мові Рython

var k,l,o,m,n,i,min,max,rez:longint;

begin

  readln(n);

  k:=0; l:=0; m:=0;

  for i:=1 to n do

    begin

       read(o);

       o:=(o mod 3);

       case o of

         0:k:=k+1;

         1:l:=l+1;

         2:m:=m+1;

       end;  

    end;

  if l>m then begin max:=l; min:=m; end

         else begin max:=m; min:=l; end;

  rez:=k+min+((max-min) div 3);

  write(rez);      

endA.

 Кодування алгоритму на мові Pascal

var k,l,o,m,n,i,min,max,rez:longint;

begin

  readln(n);

  k:=0; l:=0; m:=0;

  for i:=1 to n do

    begin

       read(o);

       o:=(o mod 3);

       case o of

         0:k:=k+1;

         1:l:=l+1;

         2:m:=m+1;

       end;  

    end;

  if l>m then begin max:=l; min:=m; end

         else begin max:=m; min:=l; end;

  rez:=k+min+((max-min) div 3);

  write(rez);      

end.

Кодування на мові Pascal генератора  перевірочних тестів(текстових файлів з даними) до алгоритму:

var f:text;

    n,p,i,k,l,m,min,max,a,o,rez,c:longint;

    pp:boolean;

begin

  read(n);

  read(p);

  assign(f,'figures.test.20');

  rewrite(f);

  writeln(f,n);

  for i:=1 to n do

  begin

   pp:=true;

   case p of

    1:begin while pp do begin a:=random(10); c:=(a mod 3); if c=0 then pp:=false; end; end;

    2:begin while pp do begin a:=random(10); c:=(a mod 3); if c=1 then pp:=false; end; end;

    3:begin while pp do begin a:=random(10); c:=(a mod 3); if c=2 then pp:=false; end; end;

    4:begin while pp do begin a:=random(10); c:=(a mod 3); if ((c=0) or (c=1)) then pp:=false; end; end;

    5:begin while pp do begin a:=random(10); c:=(a mod 3); if ((c=0) or (c=2)) then pp:=false; end; end;

    6:begin while pp do begin a:=random(10); c:=(a mod 3); if ((c=2) or (c=1)) then pp:=false; end; end;

    7:a:=random(10);

   end;

   write(f,a,' ');

   o:=(a mod 3);

    case o of

      0:k:=k+1;

      1:l:=l+1;

      2:m:=m+1;

     end;

   if l>m then begin max:=l; min:=m; end else begin max:=m; min:=l; end;

  end;

  rez:=k+min+((max-min) div 3);

  writeln(f,'');

  write(f,rez);

  close(f);

  write(rez);

end. 

Тести для перевірки алгоритму:

Тест 1.

Ввід    4

            5 5 8 8

Вивід  1

Тест 2.

Ввід     8

             5 5 7 8 8 5 8 4

Вивід   3

Тест 3.

Ввід     16

              5 5 7 8 6 8 5 8 4 6 6 3 4 2 8 0

Вивід   9

Тест 4.

Ввід      32

               5 5 7 8 8 5 8 4 4 2 8 2 4 7 8 5 4 5 8 8 7 1 8 8 4 7 8 4 5 7 1 7

Вивід    15

НОВА ІНФОРМАЦІЙНА ТЕХНОЛОГІЯ

Технологія обробки інформації та вирішення завдань за допомогою ЕОМ, що спирається на досягнення штучного інтелекту . Основною ідеєю, яка використовується в НІТ, є автоматизація процедури побудови програми, що цікавить користувача, на підставі введеного ним у систему опису постановки задачі на звичному для нього професійною мовою. Таким чином, Н.І.Т. забезпечує можливість спілкування з ЕОМ користувача, який не є професійним програмістом. Для того щоб була реалізована основна ідея Н.І.Т., необхідно, щоб ЕОМ мала інтелектуальним інтерфейсом , базою знань і вирішувачів , тобто була б інтелектуальною системою. Інший рисою Н.І.Т. є розподілений спосіб вирішення завдання, коли користувачі, зайняті вирішенням спільної справи, спілкуються між собою через мережу ЕОМ, електронну пошту та загальну базу знань. До мережі входять також бази даних , з яких користувачі черпають інформацію для вирішення свого завдання.

Всі етапи визначаються поставленим завданням і цілями моделювання. У загальному випадку процес побудови і дослідження моделі можна представити наступною схемою: Перший етап - постановка задачі включає в себе стадії: опис завдання, визначення мети моделювання, аналіз об'єкта.Опис задачі Задача формулюється на звичайній мові. За характером постановки всі завдання можна розділити на дві основні групи. До першої групи можна віднести завдання, в яких потрібно дослідити, як зміняться характеристики об'єкта при деякому впливі на нього, «що буде якщо?... ». Наприклад, що буде, якщо магнітний диск покласти поруч з магнітом? У завданнях, що відносяться до другої групи, потрібно визначити, яке треба зробити вплив на об'єкт, щоб його параметри задовольняли деякому заданому умові, «як зробити, щоб?.. ». Наприклад, як треба побудувати освітній процес в сучасній школі, щоб дітям було цікаво вчитися? Визначення мети моделювання

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

Наприклад, якщо ви будуєте модель яхти для участі в змаганнях моделей суден, то в першу чергу вас будуть цікавити її судноплавні характеристики. Ви будете вирішувати завдання «як зробити, щоб ...?»

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

У загальному сенсі формалізація - це приведення істотних властивостей і ознак об'єкта моделювання до обраної формі.

Третій етап - розробка комп'ютерної моделі починається з вибору інструменту моделювання, іншими словами, програмного середовища, в якій буде створюватися і досліджуватися модель.  Від цього вибору залежить алгоритм побудови комп'ютерної моделі, а також форма його подання. У середовищі програмування це програма, Написана на відповідній мові. У прикладних середовищах (електронні таблиці, СУБД, графічних редакторах і т. Д.) Це послідовність технологічних прийомів, Що призводять до вирішення завдання. Слід зазначити, що одну і ту ж задачу можна вирішити, використовуючи різні середовища. Вибір інструмента моделювання залежить, в першу чергу, від реальних можливостей, як технічних, так і матеріальних. Четвертий етап - комп'ютерний експеримент включає дві стадії: тестування моделі та проведення дослідження. тестування моделі Тестування моделі - процес перевірки правильності побудови моделі. На цій стадії перевіряється розроблений алгоритм побудови моделі і адекватність отриманої моделі об'єкту і мети моделювання. Тестування повинне бути цілеспрямованим і систематизованим, а ускладнення тестових даних має відбуватися поступово. Щоб переконатися, що побудована модель правильно відображає істотні для мети моделювання властивості оригіналу, тобто є адекватною, необхідно підбирати тестові дані, які відображають р е а л ь н у ю ситуацію. дослідження моделі  До цієї стадії комп'ютерного експерименту можна переходити тільки після того, як тестування моделі пройшло успішно, і ви впевнені, що створена саме та модель, яку необхідно досліджувати. П'ятий етап - аналіз результатів є ключовим для процесу моделювання. Саме за підсумками цього етапу приймається рішення: продовжувати дослідження або закінчити. Якщо результати не відповідають цілям поставленого завдання, значить, на попередніх етапах були допущені помилки. В цьому випадку необхідно коригувати модель, Тобто повертатися до одного з попередніх етапів. процес повторюється до тих пір, поки результати комп'ютерного експерименту не відповідатимуть цілям моделювання.

Моделювання обєктів, що утворюють множину Каталана  

Числа Каталана

• Математика для програмістів

• 
  

Розглянемо послідовність чисел: 1 , 1, 2 , 5 , 14 , 42 , 132 , 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 34305966540, 3430596, 3630, 3430596, 3630, 3430596, 3630, 3430596, 3430596, 3430596, 3430596, 3630, 3430596, 3630, 3430596, 3630, 3430596, 3630, 3430596, 3630594, 34305963640, 3430596364 4861946401452, ...

Це послідовність чисел Каталана, які дивним чином спливають в самих різних комбінаторних задачах. На жаль, вони випадають з розгляду типовий шкільної програми, але впевнений, що будь-який фахівець комп'ютерних наук повинен бути знайомий з ними.

Саме число Каталана виражається формулою C(n) = (2n)! / n!(n+1)!, де знак оклику, як зазвичай, позначає факторіал. Початок послідовності виглядає так: 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796 ...
Англійська Вікіпедія стверджує, що відомо, як мінімум 66 різних конструкцій, які призводять до появи чисел Каталана. Ось деякі з них:

• Правильні дужкові послідовності - набори відкриваються і закриваються дужок, в яких кожній відкривається скобці відповідає закривається. Число можливих послідовностей з фіксованим числом пар дужок виражається числом Каталана. Наприклад, 14 правильних послідовностей з чотирьох пар дужок:
  (((()))), ((() ())), ((()) ()), ((())) (), (() ( ())), (() () ()), (() ()) (),
  (()) (()), (()) () (), () ((())), () (() ()), () (()) (), () () (()), () () () ()
• Двійкові дерева - дерева, з кожного вузла яких (крім листя) виходить рівно дві гілки. Кількість бінарних дерев із заданим числом листя - число Каталана. На малюнку представлені п'ять дерев з 4 листям в кожному.
  
  Такі дерева вже обговорювалися на Хабре
• Будь-які дерева. Число неізоморфних дерев із заданим числом вершин також дорівнює числу Каталана. Такі дерева теж обговорювалися
• Монотонні шляху в квадраті - маршрути з лівого нижнього кута квадрата в правий верхній, які йдуть по лініях сітки вгору або вправо і не заходять вище діагоналі. На малюнку всі такі шляхи для квадрата 3x3.
  
• Тріангуляції багатокутника. Кількість різних тріангуляцій опуклого багатокутника діагоналями дорівнює числу Каталана.
  
• Розбиття вершин багатокутника на пари. Парне число точок на окружності можна об'єднати в пари непересічними хордами. Число способів таких об'єднань також дорівнює числу Каталана.
  
• Таблиця Юнга - прямокутник, заповнений послідовними числами так, щоб вони зростали у всіх рядках і шпальтах. Число таблиць Юнга розміром 2xn також виражається числом Каталана.
  

Для кожної з цих конструкцій можна або по індукції, або реккурентное співвідношеннями довести, що число відповідних об'єктів виражається числом Каталана. Не буду зупинятися на цих доказах - їх можна знайти в підручниках з дискретної математики. Також є деякі чудові співвідношення, які можна отримати, використовуючи деякі зі згаданих побудов. Але це вимагає написання громіздких формул, чого хотілося б уникнути. Зараз цікавіше інше - невже збіг всіх цих кількостей для абсолютно різних речей випадковість?
Звичайно ж ні. Зв'язок цих конструкцій набагато глибше. Можна побудувати взаимнооднозначное відповідність між цими об'єктами і деякі з таких відповідностей я спробую продемонструвати. Крім простої цікавості це має і деяку практичну цінність. Наприклад, завдання про генерацію всіх бінарних дерев (рішення якої в лоб неочевидно) можна звести до набагато більш простого завдання про генерацію дужкових послідовностей.

відповідність 1

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

відповідність 2

В якості другої задачі побудуємо відповідність між правильними Дужковий послідовностями і таблицями юнгам 2xn. Тут теж все просто. Пронумеруємо дужки зліва направо. Якщо дужка відкривається, то відповідне їй число пишемо в верхній рядок. Якщо закривається, то в - нижню. Так як i перша дужка завжди стоїть лівіше i-ой закривається, то число відповідне відкривається скобці буде менше числа, відповідного закриває. А значить, верхнє число в таблиці виявиться менше нижнього в тій же колонці, тобто з правильної скобочной послідовності ми отримали таблицю Юнга. Це побудова також можна зупинити, а значить отримано взаємно-однозначна відповідність.

відповідність 3

Тепер займемося бінарними деревами. Дуже легко побачити відповідність між бінарними деревами і розстановками дужок у виразі з однорідними операціями, але це дає дещо інші послідовності. Для прив'язки бінарних дерев до правильних Дужковий послідовностям треба скористатися дещо іншим підходом. Скористаємося стандартним обходом дерева і пронумеруємо вершини (корінь приймемо за 0) в порядку обходу. Тепер, якщо при переході до числа I ми спустилися від батьків до дитини, то на i-е місце ставимо відкривається дужку. В іншому випадку ставимо закривається.

Дерево - бінарне, тому у кожного вузла є сусід. А значить, спустившись до дитини і поставивши відкривається дужку, ми рано чи пізно доберемося до його сусіда і поставимо закривається дужку. Це гарантує правильність отриманої послідовності. Побудова легко звернути і взявши за основу дужкову послідовність отримати бінарне дерево.
Зауважимо, що якщо в скобочной послідовності n пар то відповідне дерево має n + 1 лист.

відповідність 4

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

Як можна помітити три сторони кожного трикутника в отриманому розбитті відповідають одному батьківському вузлу і двом його нащадкам. Тому, якщо взяти два різних дерева, то вийде два різних розбиття.

замість епілогу

Ну і на закінчення приведу табличку, в якому зображено відповідність об'єктів для третього числа Каталана.

Теги: