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

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

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

Name (required)

Mail (will not be published) (required)

Website

CAPTCHA Code