Вот подумал интересную вещь. Как эволюционировали олимпиады по информатике, и куда они движуться дальше?
Помню в 90-е... Не было ни STL, ни 256 метров памяти...
Проскакивали задачи на олимпиадах, вроде "отсортировать по возрастанию N<=100 чисел).
Огромным счастьем досовского Borland C++ 3.11 было то, что в нем можно было объявить массив больше чем 64 килобайт и о чем только мечталось в Borland Pascal 7.0 (там для массива в 200 килобайт нужно было выделять 4 массива по 50 кб в динамической памяти :) )
Из алгоритмов, к примеру, нахождение простых чисел от 1 до N вполне получалось за N*sqrt(N) , так как решето Эратосфена NlogNlogN не могло себя проявить в полной мере (так как размеры массивов были не велики) (и оно зараза только жрало лишнюю память :)
Теоретический минимум был на порядок уже чем сегодня.
Сегодня "среднедипломированный" школьник уже пишет деревья интервалов, сумматоры, , более продвинутые школьники уже используют декартовые деревья.
А раньше такое далеко не все топ-студенты умели... Индустрия движется вперед огромными темпами.
В связи с этим возник интересный вопрос. Кто бы что спрогнозировал на 10(20)(50) лет в олимпиадах по информатике (школьных и студенческих).
Какие алгоритмические задачи (которые не распространены сейчас) будут на олимпиадах будущего?
Какие будут ограничения на размеры входных данных (например для задачи о кратчайшем пути в ориентированном неразреженом графе)?
В каком году в задаче про построение выпуклой оболочки, количество точек будет равно 10^9 ? :)
Какие алгоритмы(или оптимизационные трюки) вымрут через Х лет на олимпиадах?
Какие вещи в 2020 году будут писать девятикласники на летней компьютерной школе?
Появятся ли на привычных нам олимпиадах программирование устройств?
Ну вобщем, прогнозы в студию!
→ Обратите внимание
До соревнования
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 05.11.2024 22:33:28 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
Думаю, что появятся задачи, в которых асимптотически лучшее решение с огромной константой будет ощутимо лучше решения с меньшей константой, но большей асимптотиков.
Просто N надо подобрать такое, что O(N) вкладывается в 0.5 секунд.
Тогда NlogN вкладывается всего лишь в 0.5logN секунд.
===А вообще сейчас олимпиады идут по принципу "кто быстрее набирает код", как мне кажется.
Хм, я думал, что это мое субъективное мнение. Но вижу, не одному мне такое мерешится...
А что на счет вычислений на видео карте?
CUDA жжет синим пламенем и вообще управление таким количеством процессоров как единым организмом не особо тривиальная задача.
Интересно, а вымрет ли программирование как олимпиадное направление в скором будущем? Или, может быть, потеряет свою полезность для ежедневной жизни, отсутствие которой и так критикуют уже в наше время (алгоритмы ненужные, код олимпиадный непрактичный и т.д.)
В наше время мало кто, допустим, метает копье в повседневной жизни, потому что это ему нужно по работе или чтоб добыть пищу:) А в спорте - как раз:)
Подобная история сейчас в комп. печати - мол, раньше работа машинистки была нужной, а сейчас есть ридеры различные, быстро развивается голосовой набор, скоро будет "чисто спорт".
Может, через какое-то время и олимпиады по программированию будут "только не нужным в жизни спортивным увлечением", чтоб мозг потренировать? Представляю картину - во всем мире универсальный язык программирования, при открытии любого алгоритма или любой оптимизации существующего алгоритма быстренько пишется функа для соответствующей реализации, и выкладывается в "всемирную библиотеку кода", откуда пользователи тянут функу, даже не подозревая, как она работает...
И олимпиадным будут заниматься только те, кто как раз "ищет оптимизации и новые алгоритмы", или же хочет показать, что он "знает как оно работает".
Я уже молчу о привычном для фантастики "придумали искусственный интелект, который теперь всех нагибает и сам разрабатывает оптимизации себя самого, имитируя деятельность человека":)
=====
Если же серьезней... Уровень быстро растет. Мне вот рассказывают, какой диковинкой пару лет назад был FFT. Или как призеры финала мира прямо во время финала придумали Форда-Фалкерстона - при том что они толком и не слышали о таком понятии, как поток в графе, и тем более об соответствующих алгоритмах.
всякие qsort, да и весь STL тому пример.
Сколько процентов использующих STL знают как организован map?
А сколько его напишут сами? :)
Вон раньше сколько народу на асемблере кодили?
Помню в 90-х даже конкурсы были насамую короткую по кол-ву байт програму (скомпиленую). И алгоритмами тогда не так баловались.
Раз уж речь зашла о футуризме и искусственном интеллекте, я всем очень рекомендую послушать вот это - по ссылке есть, как видите, ещё и рецензия, и авторский видеоряд к первым десяти трекам.
На старте стоит 100 игрушечных роботов.
Пофиг запрограммируешь ты быстрее всех, или лучше всех. Показателем победы будет приход робота на финиш в лабиринте.
Можешь за 10 минут написать тупую программу, и твой робот будет блуждать до конца контеста.
А можешь потратить 100 минут, а робот за оставшиеся 20 справиться с задачей :)
А по отношению к другим роботам :)
Эдакая модель общества :)
Там, правда, правила известны примерно за год и можно готовиться. Но и задания на порядок сложнее, чем "пройти лабиринт".
Нашли вот такое шуточное развитие событий:
Решили, что если докажут равенство P=NP и сделают еще пару клевых открытий, то можно будет делать так:
Один участник пишет специальный анализатор(допустим он делает это 4 часа)
Остальные 2 участника формализуют задачи под какую-то конкретную задачу, которую решает анализатор.
Остается час, что бы вбить формальные решения в процедуру и отправить это все джуджу :)
На срок больший 10 лет полагаю загадывать не имеет смысла. Для роста производительности наверняка можно в грубой форме воспользоваться законом Мура - удвоение числа объектов в задачах будет происходить каждые 1-2 года. Однако на длинных периодах 20-50 лет вероятно могут быть революционные изменения в науках и технологиях которые качественно повлияют на учебные и спортивные процессы.
Многие авторы фантастических книг обещали в будущем массовое использование видеотелефонов. Зато мало у кого в книгах встречаются мобильники. Вышло всё наоборот - видеосвязь востребована мало даже при её доступности, зато мобильность крайне актуальна.
1) В однопоточном режиме современные процессоры "быстреют" за счёт векторных команд (типа SSE) и улучшением суперскалярного декодера. На олимпиадах выставляются настройки компиляторов, которые запрещают использование всяких подобных фишек (запретить суперскалярность особо нельзя, но реально рассчитывать на неё тоже невозможно).
2) Основное направление развития - в сторону большего количества ядер. Пока олимпиадные задачи не подразумевают параллельных вычислений, использовать это не представляется возможным.
Закон Мура можно более общо рассматривать - например в приложении к самим задачам а не к технике, на которой они выполняются... Т.е. общее предположение что объёмы обрабатываемых данных растут экспоненциально со временем... Или я не прав?