Коледж алгоритмічного програмування

    Лекція Десята (Сезон Другий)

    Десята лекція другого сезону відбудеться 2 грудня о 17 годині у конференц-залі на третьому поверсі.

    Лекцію веде: Shef.

    Тема: Теорія ігор.

    На порядку денному:

    • Загальні підходи до розв’язання ігрових задач.
    • Ігри на графах.
    • Числа Шпрага-Гранді.
    25.11.2010 | Shef | 15 коментарів

    15 коментарів to “Лекція Десята (Сезон Другий)”

    1. Shef каже:
      01.12.2010 о 22:59

      Домашнє завдання:

      ACM Контестер 1104 – Цікава гра.
      ACM Контестер 1251 – The unfair game.
      ACM Контестер 1259 – The card game.
      ACM Контестер 1295 – Гра.
      ACM Контестер 1319 – Хто ж переміг?
      SGU 328 – A Coloring Game.
      SGU 335 – Thiefs And Cops.

    2. Shef каже:
      01.12.2010 о 23:00

      Тренувальне змагання

      Algorithmic Programming College Season Two Practice Contest 10
      Сервер – ACM Контестер.
      Початок – субота, 4 грудня 2010 року о 18:00.
      Тривалість – 4 години.
      Задачі – Shefs Contest 6.

    3. CUPIDON каже:
      01.12.2010 о 23:32

      А…. А чого так рано? Лекція ж тільки завтра…

    4. CUPIDON каже:
      01.12.2010 о 23:35

      Хоча, дуже хороша ідея – дати домашнє наперед, шоб люди знали на шо їм очікувати, плюс підготувати питання по задачках.

      Ем. А мене цікавить… Задачки на контесті будуть НОВІ, чи з бази?

    5. Witaliy каже:
      02.12.2010 о 00:02

      CUPIDON: читай другий пост:
      Задачі – Shefs Contest 6.

    6. Patlatus каже:
      02.12.2010 о 20:46

      3 грудня буде інтернет-олімпіада з алгебри на цьому сайті:
      http://mech.math.msu.su/department/algebra/Olympiad
      Для участі там треба реєструватися тут
      http://lomonosov-msu.ru/rus/event/423/
      14 грудня буде інша інтернет-олімпіада на цьому сайті
      http://www.i-olymp.net/, реєстрація там же, 5-12 грудня.
      Можна зібрати студентів і загітувати їх виступити на цій олімпіаді або виступати аспірантам – там ніхто не перевіряє, чи ти ще студент, чи вже ні. Трохи незручно, правда, коли ти їм втовкмачуєш, що ти постґрадюейт стюдент, а вони тобі присилають медальку з листом, де пишуть your student participated in this competition…

    7. Patlatus каже:
      02.12.2010 о 21:01

      До речі, про гру Банаха-Мазура.

      Коли двом математикам Банаху і Мазуру стало нудно, вони стали грати в таку гру. Вони визначили для себе деяку множину A на відрізку [0, 1]. Після цього Банах узяв якийсь відрізок, Мазур всередині цього відрізка ще відрізок, потім Банах взяв ще відрізок і т. д. При цьому вони відразу домовилися, що довжина відрізків буде прямувати до нуля і тому в перетині буде виходити точка. Так от, якщо ця точка міститься в A, то виграв перший гравець, а якщо не міститься, то виграв другий (можете на дозвіллі пограти. Тільки грати потрібно з шаховими годинниками і ходи робити швидко).
      Легко зрозуміти, що якщо A зліченна, то у другого є виграшна стратегія. Він може за перший свій хід позбутися від першої точки, взявши відрізок, що не містить її, за другий хід – від другого, і т. д. Якщо A ніде не щільна, то другий може виграти взагалі за один хід. Першим же ходом потрібно просто взяти відрізок, що не перетинається з A (таких існує величезна кількість, просто за означенням). Якщо A – зліченне об’єднання ніде не щільних множин (такі множини Бер називав множинами першої категорії), то другий також може виграти: на першому кроці він позбавляється від першої ніде не щільної множини, на другому – від другої, і т. д.
      Банах із Мазуром задумалися, чи для будь-якого A в одного з гравців є виграшна стратегія. Це цілком природне твердження: або для будь-якого ходу першого є такий хід другого, що для будь-якого ходу першого є такий хід другого, що … і т. д., або існує хід першого, такий що для будь-якого ходу другого існує хід першого, такий що для будь-якого ходу друге існує хід першого … і т. д.
      Множина A називається детермінованою, якщо для неї в одного з гравців є виграшна стратегія. Твердження про те, що всі А з [0, 1] детерміновані, називається аксіомою детермінованості.
      З нею проблема навіть не в тому, що її не вміють доводити. На відміну від аксіоми вибору ще навіть невідомо, чи дійсно вона несуперечлива з аксіоматикою Цермело-Френкеля. Зате відомо, що з аксіоми вибору миттєво випливає заперечення аксіоми детермінованості, але з аксіоми детермінованості випливає аксіома вибору для зліченного числа множин (завдяки чому у нас зберігається весь математичний аналіз).
      Якщо прийняти аксіому детермінованості, можна отримати багато цікавих і дивовижних фактів:
      1) всі множини з [0, 1] вимірні за Лебегом;
      2) будь-яка обмежена функція інтегровна за Лебегом;
      3) немає вільних максимальних ідеалів;
      4) базис є тільки в скінченновимірних лінійних просторах.
      Загальна ідея аксіоми детермінованості в тому, що об’єкт існує, тільки якщо його можна побудувати «руками», взяти і пояснити, як його будувати. А якщо не виходить пояснити, то об’єкт не існує зовсім.
      Детальніше про аксіому вибору і аксіому детермінованості див. книгу
      В. Г. Кановей. Аксиома выбора и аксиома детерминированности. — М.: Физматгиз, 1984.

    8. Shef каже:
      02.12.2010 о 22:09

      Мене дуже цікавить хто скільки задач з домашнього завдання зможе зробити.

    9. CUPIDON каже:
      03.12.2010 о 01:41

      Ем… Шеф? А до чого в д/з 1319 задачка?!)

    10. LeBron каже:
      03.12.2010 о 20:07

      http://acm.tju.edu.cn/toj/showp3300.html – Ось задачка на Ейлерову функцію. Я її успішно здав) Використав розклад на множники і решето Ератосфена. Але після того випадково в асі розмові з одним хлопаком з Росії згадав про ту задачу, і він сказав, що у них на районній (по району міста) олімпіаді школярів на днях була така ж сама, тільки дається кількість тестів (до 100), і знайти не від а до б, а від 1 до а суму. Але обмеження – 50 мільйонів!
      Час 2 секунди.

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

      Певно, це логічніше до теорії чисел писати, але нема бажання старі теми рухати.

    11. Patlatus каже:
      04.12.2010 о 18:02

      “Тренувальне змагання

      Algorithmic Programming College Season Two Practice Contest 10
      Сервер – ACM Контестер.
      Початок – субота, 4 грудня 2010 року о 18:00.
      Тривалість – 4 години.
      Задачі – Shefs Contest 6.”

      Де це змагання?
      Як здавати? Якесь посилання є? Я щось не доганяю…

    12. LeBron каже:
      04.12.2010 о 21:06

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

      Суть така, якщо пишеш матч краще, ніж повинен би, у відповідності до своїх рейтингових балів, то ці рейтингові бали ростуть (на скільки – залежить від частоти виступів, поточних рейтингових балів, стабільності виступів, різниці між очікуваним і показаним результатом), інакше – падають. Рейтингове місце в Алго-змаганнях на ТопКодері – це місце у відсортованому за рейтинговими балами списку кодерів, котрі брали участь хоча б в одному матчі за останні 6 місяців.

    13. LeBron каже:
      04.12.2010 о 21:12

      Ой) Не туди) Це відповідь на запитання про рейтинг Шефа) зараз копірну)

      З приводу домашнього завдання – нам такі задачі, щоб “не надто зазнавались”? ))

    14. Patlatus каже:
      04.12.2010 о 21:27

      Посилання на змагання знайшов. Але було б прикольніше, якби воно зразу десь тут висіло, разом з оголошенням… А то я десь півгодини то змагання шукав…

    15. Shef каже:
      06.12.2010 о 11:27

      Задача 1319 додана для того, щоб продемонструвати що бувають різні ігрові задачі і тривіальні у тому числі. Приклад хороший навіть не зважаючи на те, що цю задачу з натяжкою можна віднести до ігрових.

    Leave a Reply

    Клацніть, щоб скасувати відповідь.

    CAPTCHA Image CAPTCHA Audio
    Refresh Image
    Лекція Одинадцята (Сезон Другий)
    Новий Рік у Коледжі
     
    • Банери

    • Категорії

      • Змагання (2)
      • Лекції (149)
      • Некатегоризовано (12)
      • Розбір задач (13)
      • свято (4)
    • Архіви

      • Жовтень 2016 (1)
      • Квітень 2016 (3)
      • Березень 2016 (5)
      • Лютий 2016 (3)
      • Грудень 2015 (3)
      • Листопад 2015 (1)
      • Травень 2015 (1)
      • Квітень 2015 (4)
      • Березень 2015 (4)
      • Лютий 2015 (3)
      • Грудень 2014 (2)
      • Листопад 2014 (4)
      • Жовтень 2014 (5)
      • Вересень 2014 (1)
      • Травень 2014 (2)
      • Квітень 2014 (3)
      • Березень 2014 (3)
      • Лютий 2014 (1)
      • Грудень 2013 (3)
      • Листопад 2013 (4)
      • Жовтень 2013 (4)
      • Травень 2013 (2)
      • Квітень 2013 (4)
      • Березень 2013 (4)
      • Лютий 2013 (4)
      • Листопад 2012 (7)
      • Жовтень 2012 (2)
      • Травень 2012 (1)
      • Квітень 2012 (4)
      • Березень 2012 (5)
      • Лютий 2012 (4)
      • Грудень 2011 (3)
      • Листопад 2011 (4)
      • Жовтень 2011 (4)
      • Вересень 2011 (3)
      • Травень 2011 (2)
      • Квітень 2011 (5)
      • Березень 2011 (4)
      • Грудень 2010 (4)
      • Листопад 2010 (5)
      • Жовтень 2010 (4)
      • Вересень 2010 (3)
      • Травень 2010 (4)
      • Квітень 2010 (4)
      • Березень 2010 (6)
      • Лютий 2010 (3)
      • Січень 2010 (1)
      • Грудень 2009 (7)
      • Листопад 2009 (2)
      • Жовтень 2009 (2)
    • ACM-Контестер

      • ACM-Contester Архів задач із автоматичною системою тестування “ACM Contester”.
    • Мета

      • Зареєструватись
      • Вхід
      • RSS публікацій
      • RSS коментарів
    

    © 2019 Коледж алгоритмічного програмування is proudly powered by WordPress | Constructor Theme
    Entries (RSS) and Comments (RSS).
    Наші проекти: Контестер, _Колледж.