Форум Всеукраїнської інтернет-олімпіади NetOI

>>> Доречі люди які їздили на IOI говорили, що й там є задачі на геометрію. --- Еее, ти не про себе? Чи ти Симоненко третій? ( http://www.uoi.kiev.ua/Default.aspx?pag … ;year=2007 - Руслан Симоненко http://www.uoi.kiev.ua/Default.aspx?pag … ;year=2006 -    
Владислав Симоненко)

Не спорю, в математиці є й цікаві задачки. Пам'ятаю, перед вступом в ліцей були там всякі теореми Діріхле й всяке таке. Ехх, хороші були часи Але через повсякденний отстой, якому вчать в школі тепер мене нудить від самого слова математика
В любому випадку такі задачки треба давати на олімпіадах з математики, а не програмування.

Звичайно згоден з тим, що деяка геометрія (вектори) не найрідше зустрічається на інших контестах. Хоча теж доволі рідко...

>>> навіть сортування і те має математичне доведення

Ти про доведення через епселон-дельта? І шо з того? Не завжди N log N сортуватиме найшвидше. + швидкість може залежити від того ЩО потрібно посортувати. Тут треба дивитись на специфіку (ось тут і починається програмування!). Припустимо, якщо тобі треба посортувати 1000000 цілих чисел до 100000 (по модулю) за сек. - ти можеш посортувати й за O(N). Подумай, як Ми маємо РЕАЛЬНІ (+/- (більш-менш)) числа. Нам не однаково, чи звертатись до 10, чи 10^10000, як в математиці. Тому тут мат-доведення малувато шо значить...

>>> Отсюда вытекает, что и TopCoder, и ACM, и IOI, и NetOI - это 90% чистой математики, и лишь 10% остальных проблем.
Фанаааарь. На ТС тааак багато математики!.. А на АСМ скільки!.. Йооой...

>>> Во-вторых, алгоритмистика как научная отрасль - это математический раздел.
Ну й шо з того, шо якийсь лапух її туди приписав, коли ше взагалі не було компів? Взали просто, шо перші програмісти (алгоритмісти) були математиками й того приписали туди ж.

>>> Или вы считаете, что до 40-х годов ХХ века в науке не существовало понятия "алгоритм"?
Euclid not dead! Знаю, і шо?

>>> Про АСМ я вообще молчу - там бывает и математика, и физика. Да еще в таких объемах, что мало не покажется.
Ти про шо? Де ти там їх стільки побачив?.. Там таких одна на тисячу буває. А з фізики - взагалі мовчу - покищо жодної такої не бачив.

>>> Вот и всё, что действительно является информатикой - практика реальной жизни.

http://en.wikipedia.org/wiki/Computer_science
...
Computer science is considered by some to have a much closer relationship with mathematics than many scientific disciplines. Early computer science was strongly influenced by the work of mathematicians such as Kurt Gödel and Alan Turing, and there continues to be a useful interchange of ideas between the two fields in areas such as mathematical logic, category theory, domain theory, and algebra.
...


http://en.wikipedia.org/wiki/Graph_theory
...
In mathematics and computer science, graph theory is the study of graphs; mathematical structures used to model pairwise relations between objects from a certain collection
...
То шо деякі речі можуть відноситись і до програмування і до (напевне - швидше формально) математики, не означає, шо це - територія математики.

Відредаговано ibm (2007-12-25 18:18:58)

Навіщо тобі саме матиматичне доведення? Хіба не мало логічного? Навіщо доводити задачку, яку і так швидко зрозуміти?

З тим, шо інформатика - ">>> по специфике работы ПК, разработка ПО и т.д.... <<<" згоден. Але програмування - ні.

>>> Почти все задачи, которые были изначально рассчитаны на то что их решат не сразу и над которыми требуется подумать, причем довольно серьезно в информатике являются чистейшей математикой.

А шо нарахунок задачок на NP, динаміку? То - теж математика, правда? По-твому задача на максимальний потік - теж математика, чи вона не з тих, над якими "над которыми требуется подумать".

>>> Да реально тяжелых задач чисто на кодинг пересчитать на пальцах можно...
Якшо "задачі на кодінг" - не математичні задачі на програмування - глянь сюди http://acm.lviv.ua/fusion/viewpage.php?page_id=8 (не дивись на останні звідти) пальців не вистарчить...

>>>По-твому задача на максимальний потік - теж математика, чи вона не з тих, над якими "над которыми требуется подумать".

Ну насправді максимальний потік - одна з тих тем, в яких видно, що вклали в рішення математики, а що - інформатики...
Математики
1). Придумали алгоритм Форда-Фалкерсона. Сказали - пхайте той потік поки лізе, а далі подивимось...
Інформатики
2).Придумали на його основі інші більш швидкі алгоритми...Вони показали, не що ця заача вирішується ТАК, а що так вона вирішується ШВИДКО...ЗА ПРАКТИНИХ ОБМЕЖЕНЬ
Математики
3).Знову ж таки довели, що у інформатиків вище усе КЛЬОВО...

І мені здається що щось подібне відбувалось у інших галузях алгоритмів

Тому ви, здається, не зрозуміли одне одного...Самі алгоритми, якими ми користуємось - це інформатика, проте це лише вершина айсберга..ВСЕ інше - математика

>>>Ну а умные методы поиска максимального потока без хотя бы минимального доказательства понять окажется проблематичным - их время работы доказывается чисто математически.

Отут не згоден..часто, використовуючи "розумні" методи знаходження макспотока, або коли ти їх будеш використовувати в прикладних задачах, ти будеш подумки казати доведення складності, вірності чи ще чогось у даному алгоритмі?

>>>Навіщо тобі саме математичне доведення? Хіба не мало логічного? Навіщо доводити задачку, яку і так швидко зрозуміти?

Коли ми вирішуємо задачі - ми навряд чи будемо вигадувати щось фундаментальне, новий алгоритм, проте те, чим ми будемо користуватись - це якісь ЗОВНІ очевидні факти, про які ми можемо не згадувати, що це математика, але не можемо забувати!

Відредаговано MAXXX (2007-12-25 20:49:04)

necro
Про то, что здесь сложно писать, мы явно расходимся во мнениях.
Мое ИМХО (не как жюри, а как олимпиадчика с 5 летним стажем): тут есть только одна задача, про которую можно сказать то, что ты говоришь про все.

MAXXX
Я говорил не про метод Форда-Фалкерсона, а про более продвинутые алгоритмы, которые к нему никакого отношения не имеют.

Что же до того, что в решении задач не нужно знать доказательств оценок и алгоритмов - это так. Но только пока используется оригинальный алгоритм. А когда же необходимо его модифицировать для поиска чего-то похожего, но иного, или когда нужно построить иной алгоритм, но на той же идее, то уже придется понимать, как работает оригинальный и откуда берется его время работы.
>Коли ми вирішуємо задачі - ми навряд чи будемо вигадувати щось фундаментальне, новий алгоритм, проте те, чим ми будемо користуватись - це якісь ЗОВНІ очевидні факти, про які ми можемо не згадувати, що це математика, але не можемо забувати!
Браво. Красивая фраза.
Но иногда решение может базироваться и на неочевидных фактах. Тогда про это уже придется вспомнить.

ibm написав:

Просто я хотів, щоб тут були алгоритмічні задачки. В тому числі й на графи, бо ІМХО, графів на Вінниці нема й давненько не було... А от довгої арифметики (яку б, якби хтось її використовував в житті - вписали в СТЛ), р-нь типу y=kx+b --- дофігіще...

Це, шановний, мяко кажучи,  не відповідає істині. Проаналізуйте задачі NetOI за всі роки (вони є на сайті, видані книгою), і знадете вельми значну кількість "алгоритмічних" задач, в т.ч. і на графи.

А тепер по суті дискусії. Вона створена частиною "крутих олімпбійців", які засвоївши півтора десятка базових алгоритмів навчилися більшість пропонованих їм на олімпіадах задач зводити до цих алгоритмів і "гарантовано" мати 80% результату, а поталанить - і всі 100. Звичайно, знання цих речей є НЕОБХІДНИМ і корисним, але, як на мене, НЕДОСТАТНІМ для підготовки програміста високого рівня. А спроби "гнати" на математику і відділити її від теорії алгоритмів... просто  смішні.

MAXXX

>Іноді на олімпіадах треба застосовувати алгоритм Евкліда...Ти часто перед тим як його застосувати, доводив, що він видасть в кінці кінців правильну відповідь?smile  >Але ж ти був впевнений що так воно і є?smile
Могу тебя обрадовать. Выведение алгоритма Эвклида - тоже вещь полезная и пользоваться им мне доводилось. Потому что на нем базируется расширенный алгоритм Эвклида.

>Інший приклад - кількість виборок С(n,m)=n!/(m!*(n-m)!)...теж мабуть користувався, але не доводив..
Опять же. Комбинаторное доказательство этого равенства очевидно.

>Методы, связанные с проталкиванием предпотока тоже не на пустом месте родились...Если ты говоришь про что-то еще более продвинутое - ну сорри, я тебя неверно понял...

Я как про реализации этого метода, так и про пару иных интересных идей, связанных с потоками.

ibm
Как тебе удается сказать столько противоречащих истине тезисов в одном посте?

>По-друге, програмування - це не мови, а алгоритми, й якщо якийсь математик зробив алгоритм - це не означає, що алгоритми відносяться до математики, як і >математика не відноситься до фізики, хоч фізики й зробили значний вклад в неї.
Ты явно путаешь олимпиадное программирование с программированием вообще. Реальное программирование - далеко не одни алгоритмы. Тут и языки, и прикладные библиотеки, и протоколы, и еще много всего к алгоритмам отношения не имеющего. Ведь алгоритм - это лишь ответ на вопрос "что делать?". На вопрос "как делать?" искать ответ часто приходится в других областях.

Ну а про определение математики уже все сказал Юрий Яковлевич.
Разве что добавлю, что та же теория множеств и теория чисел на самом деле выглядывает из практически всех разделов математики. Просто в школе на этом внимание не акцентируют.

Ту же теорию графов тоже трудно назвать новой - основы ее заложены еще Эйлером.

---
Я из всей этой дискуссии вынес только один тезис - ты категорически против обычной школьной математики . Выводы отсюда очевидны.

MAXXX
Обшибка вышла

Мне этот разговор начал напоминать открытие всеукра этого года, где раз пять было сказано "Що таке інформатика?"

reiten написав:

Вообще, интересно слышать от "серого" (на ТС),у котогого контестов в алгоритме вообще нету (специально посмотрел статистику на сайте) про то, какие задачи на ТС есть, а какие - нет.

Вже не сірий То просто Різдво було й вони не перевірили на правильність тести останнього марафону. А так - я змагався в контестах на алгоритми. Правда тільки в 2-му дивізіоні.... Просто довелось створювати нового юзера, бо на минулому я заглючив з реєстрацією на High School... Тому не міг змагатися в хайскул. Ну то - нічого... Сьогодні в 6-тій вечора матч --- може писатиму...

pro написав:

Еще до того как начались все эти рассусоливания на левую тему было сказано, что начало отрезка не закрашивается, но в примере к условию ясно видно, что начала закращиваються. Так ли это?

Где это такое писалось?
Начало и конец закрашиваются. Это очевидно и на форуме об этом ничего не говорилось.

askold написав:

ДУЖЕ цікаве обговорення ЗАДАЧІ LOGO... таке інформативне))))...... Може варто відділити тему?
Андрій: а яке там питання в умові задачі про драконів?

Кто выиграет при правильной игре, а также все варианты первого хода, если выигрывает первый.

З наступаючим!
http://ace.delos.com/usacotext2?a=xlTz0 … mp;S=probs