Десята лекція другого сезону відбудеться 2 грудня о 17 годині у конференц-залі на третьому поверсі.
Лекцію веде: Shef.
Тема: Теорія ігор.
На порядку денному:
- Загальні підходи до розв’язання ігрових задач.
- Ігри на графах.
- Числа Шпрага-Гранді.
Десята лекція другого сезону відбудеться 2 грудня о 17 годині у конференц-залі на третьому поверсі.
Лекцію веде: Shef.
Тема: Теорія ігор.
На порядку денному:
© 2024 Коледж алгоритмічного програмування is proudly powered by WordPress | Constructor Theme
Entries (RSS) and Comments (RSS).
Наші проекти: Контестер, _Колледж.
Домашнє завдання:
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.
Тренувальне змагання
Algorithmic Programming College Season Two Practice Contest 10
Сервер – ACM Контестер.
Початок – субота, 4 грудня 2010 року о 18:00.
Тривалість – 4 години.
Задачі – Shefs Contest 6.
А…. А чого так рано? Лекція ж тільки завтра…
Хоча, дуже хороша ідея – дати домашнє наперед, шоб люди знали на шо їм очікувати, плюс підготувати питання по задачках.
Ем. А мене цікавить… Задачки на контесті будуть НОВІ, чи з бази?
CUPIDON: читай другий пост:
Задачі – Shefs Contest 6.
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…
До речі, про гру Банаха-Мазура.
Коли двом математикам Банаху і Мазуру стало нудно, вони стали грати в таку гру. Вони визначили для себе деяку множину A на відрізку [0, 1]. Після цього Банах узяв якийсь відрізок, Мазур всередині цього відрізка ще відрізок, потім Банах взяв ще відрізок і т. д. При цьому вони відразу домовилися, що довжина відрізків буде прямувати до нуля і тому в перетині буде виходити точка. Так от, якщо ця точка міститься в A, то виграв перший гравець, а якщо не міститься, то виграв другий (можете на дозвіллі пограти. Тільки грати потрібно з шаховими годинниками і ходи робити швидко).
Легко зрозуміти, що якщо A зліченна, то у другого є виграшна стратегія. Він може за перший свій хід позбутися від першої точки, взявши відрізок, що не містить її, за другий хід – від другого, і т. д. Якщо A ніде не щільна, то другий може виграти взагалі за один хід. Першим же ходом потрібно просто взяти відрізок, що не перетинається з A (таких існує величезна кількість, просто за означенням). Якщо A – зліченне об’єднання ніде не щільних множин (такі множини Бер називав множинами першої категорії), то другий також може виграти: на першому кроці він позбавляється від першої ніде не щільної множини, на другому – від другої, і т. д.
Банах із Мазуром задумалися, чи для будь-якого A в одного з гравців є виграшна стратегія. Це цілком природне твердження: або для будь-якого ходу першого є такий хід другого, що для будь-якого ходу першого є такий хід другого, що … і т. д., або існує хід першого, такий що для будь-якого ходу другого існує хід першого, такий що для будь-якого ходу друге існує хід першого … і т. д.
Множина A називається детермінованою, якщо для неї в одного з гравців є виграшна стратегія. Твердження про те, що всі А з [0, 1] детерміновані, називається аксіомою детермінованості.
З нею проблема навіть не в тому, що її не вміють доводити. На відміну від аксіоми вибору ще навіть невідомо, чи дійсно вона несуперечлива з аксіоматикою Цермело-Френкеля. Зате відомо, що з аксіоми вибору миттєво випливає заперечення аксіоми детермінованості, але з аксіоми детермінованості випливає аксіома вибору для зліченного числа множин (завдяки чому у нас зберігається весь математичний аналіз).
Якщо прийняти аксіому детермінованості, можна отримати багато цікавих і дивовижних фактів:
1) всі множини з [0, 1] вимірні за Лебегом;
2) будь-яка обмежена функція інтегровна за Лебегом;
3) немає вільних максимальних ідеалів;
4) базис є тільки в скінченновимірних лінійних просторах.
Загальна ідея аксіоми детермінованості в тому, що об’єкт існує, тільки якщо його можна побудувати «руками», взяти і пояснити, як його будувати. А якщо не виходить пояснити, то об’єкт не існує зовсім.
Детальніше про аксіому вибору і аксіому детермінованості див. книгу
В. Г. Кановей. Аксиома выбора и аксиома детерминированности. — М.: Физматгиз, 1984.
Мене дуже цікавить хто скільки задач з домашнього завдання зможе зробити.
Ем… Шеф? А до чого в д/з 1319 задачка?!)
http://acm.tju.edu.cn/toj/showp3300.html – Ось задачка на Ейлерову функцію. Я її успішно здав) Використав розклад на множники і решето Ератосфена. Але після того випадково в асі розмові з одним хлопаком з Росії згадав про ту задачу, і він сказав, що у них на районній (по району міста) олімпіаді школярів на днях була така ж сама, тільки дається кількість тестів (до 100), і знайти не від а до б, а від 1 до а суму. Але обмеження – 50 мільйонів!
Час 2 секунди.
Можна дізнатись, чи таке реально зробити, чи той хлопець щось напутав або вирішив з мене пожартувати?.. І взагалі, який найшвидший метод пошуку “суми функцій Ейлера” в таких випадках? Там є якась формуляка, чи нема?
Певно, це логічніше до теорії чисел писати, але нема бажання старі теми рухати.
“Тренувальне змагання
Algorithmic Programming College Season Two Practice Contest 10
Сервер – ACM Контестер.
Початок – субота, 4 грудня 2010 року о 18:00.
Тривалість – 4 години.
Задачі – Shefs Contest 6.”
Де це змагання?
Як здавати? Якесь посилання є? Я щось не доганяю…
Можна глянути на сайті їхньому, там є пачка формул, але вони досить нудні для “сторонньої людини”, і, допустим, я ними користуюсь лише деколи щоб оцінити, на скільки приблизно було б краще для мене, якби така-то задача не впала або таку-то задачу я здав трохи швидше)
Суть така, якщо пишеш матч краще, ніж повинен би, у відповідності до своїх рейтингових балів, то ці рейтингові бали ростуть (на скільки – залежить від частоти виступів, поточних рейтингових балів, стабільності виступів, різниці між очікуваним і показаним результатом), інакше – падають. Рейтингове місце в Алго-змаганнях на ТопКодері – це місце у відсортованому за рейтинговими балами списку кодерів, котрі брали участь хоча б в одному матчі за останні 6 місяців.
Ой) Не туди) Це відповідь на запитання про рейтинг Шефа) зараз копірну)
З приводу домашнього завдання – нам такі задачі, щоб “не надто зазнавались”? ))
Посилання на змагання знайшов. Але було б прикольніше, якби воно зразу десь тут висіло, разом з оголошенням… А то я десь півгодини то змагання шукав…
Задача 1319 додана для того, щоб продемонструвати що бувають різні ігрові задачі і тривіальні у тому числі. Приклад хороший навіть не зважаючи на те, що цю задачу з натяжкою можна віднести до ігрових.