Блог пользователя PapkovNikita

Автор PapkovNikita, 12 лет назад, По-русски

Привет всем. Хотел попросить у вас совета, как развиваться, что читать, какие учебные дисциплины вам помогли?
UPD №3:
Добавлю всё что нашел для обучения:
1) http://e-maxx.ru/ — Отличный сайт с описанием алгоритмов и книгами на эту тему.
2) http://codeforces.com/blog/entry/224 — список книг рекомендуемых для прочтения.
3) http://codeforces.com/blog/entry/1594 — тоже хороший пост, а точней кросспост на тему: Теоретический минимум для программиста.
4) Лекции по ДП:
4.1) http://g6prog.narod.ru/din_kotov.rar
4.2) http://ejudge.btty.su/bmstu/2007-2008/docs/dp1.pdf
4.3) http://ejudge.btty.su/bmstu/2007-2008/docs/dp2.pdf
4.4) http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg
5) Онлайн курсы
5.1) http://informatics.mccme.ru/moodle/course/view.php?id=9 — курс по ДП
5.2) http://ips.ifmo.ru/courses/course1/index.html — Введение в алгоритмику.
6) Видео-курсы:
6.1) http://www.intuit.ru/video/tree/catalog/algorithms/ — огромное количество курсов по алгоритмам
6.1.1) http://www.intuit.ru/department/algorithms/basicalgos/1 — отдельно порекомендовал dalex
6.2) http://www.lektorium.tv/course/?id=22823 — Совместный проект Школы анализа данных Яндекса, CS клуба, Академии современного программирования и ФМЛ №239. Занятия начались осенью 2011.
6) Задачники для новичков:
7.1) http://acmp.ru/ — много простых задач, для которых указана и тематика, и уровень сложности; на них можно отрабатывать технику.
7.2) http://dl.gsu.by/ — каждую неделю проходят (раньше так точно проходили, сейчас не уверен) по воскресеньям олимпиады для начинающих и не очень.

  • Проголосовать: нравится
  • +20
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Такие вопросы уже были, поищи на этом сайте через гугл.

»
12 лет назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится
while (getCurrentSkills() <= getDesiredSkills())
{
    OnlineJudge &judge = getPreferredOnlineJudge();
    Problem &problem = judge.getRandomProblem(getCurrentSkills(), OnlineJudge::NOT_SOLVED);
    Solve(problem);
}
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    :))) Если я сейчас начну решать все подряд, то это почти всегда будет тупой перебор в этом и проблема. Хочу граммотней решать.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +110 Проголосовать: не нравится

      Если у тебя получается Accepted перебором по любой задаче, то либо ты специально отбираешь задачи на перебор, либо ты Burunduk1.

      Кстати, это английская ветка.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    It is very stupid and slow algorithm.

    1. It is better to solve no only problems of your level, but so still problems with little higher difficulty that your level, and easier then problems of your level.

    2. When you cant to solve a problem in a fixed time, you must to read an analysis and a solution, and then you must to write and accept it. If you have accepted current problem, all the same, you must to read the analysis and solution.

    3. It is better to have a teacher, who will get you problems needed for you.

    (sorry for broken English)

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
      1. Not only problems with little higher difficulty. I think that getRandomProblem() should be implemented with normal distribution on problem level.
      2. Individually. Of course, if you got AC, you must read an analysis and solution. But when you can not solve a problem, sometimes you need not to read an analysis. I've used some ideas like this: 2a) In the last 2 or 3 contests I got all my AC before 3/4 of competition time. I need to read an analysis, but not need to write program after that. 2b) In the last 2 or 3 contests at the end I have some ideas how to got AC on problems that I have not solved. I need to solve in a short time some easier problems in order to increase my coding skills. 2c) Neither 2a, nor 2b. I will read the analisys if and only if I am sure that it contains an idea that I've never seen. Otherwise, I will try to solve this problem without analisys.
      3. Of course, if you have a teacher, he can help you with your weak sides.
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -23 Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Немного не по теме: уже несколько часов пытаюсь найти, как рассчитать за сколько задача «решается». Везде пишут, что-то вроде: «Задача решается за O(n*log(n))» или «Задача решается за n*sqrt(n)». А что это означает? И как определить за сколько задача решается?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится

    Читать Кормена.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    На e-maxx.ru в разделе "литература" есть книга Кормена. Там это написано. Вкратце — обычно под в СП имеется ввиду, что в худшем случае программа сделает не более, чем операций для некоторого C.

»
12 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Да, чуть не забыл. tsya.ru

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Ребята, а что про эти видео-курсы скажите ? http://www.intuit.ru/video/tree/catalog/algorithms/

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Могу сказать, что смотреть лучше только те, что "для школьников".

»
12 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Обновил пост, может кому-то понадобится.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

На гомельском сайте dl.gsu.by каждую неделю проходят (раньше так точно проходили, сейчас не уверен) по воскресеньям олимпиады для начинающих и не очень. Также есть курсы для прорешивания задач ежедневно. Курс "программирование начинающие" содержит детские задачки, курс "методы алгоритмизации" — серьезнее.

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

как говорил один мой учитель: "Чтобы научиться решать, надо решать".

начни с простеньких задач, постепенно. не сразу Москва строилась. на хорошую подготовку уходят годы тренировок

»
12 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Из пока неупомянутого есть еще "Интернет-школа информатики и программирования" ИТМО, в частности, курс "Введение в алгоритмику", хотя он, пожалуй, уже для не совсем начинающих и не претендует на полноту.
Поскольку текущий уровень подготовки автором не заявлен, то (предполагаю по фразе о том, что любая задача сводится к перебору), вероятно, не помешают книги, в которых излагается построение алгоритмов, притом с самых простых (иначе вряд ли удастся понять, как до такого додуматься).
Из книг именно для начинающих, но "с продолжением", вероятно, заслуживают внимания "Программирование: типовые задачи, алгоритмы, методы" Д.М. Златопольского и "Основы программирования" С.М. Окулова.
Из online-"задачников" еще добавлю "Школу программиста" — много простых задач, для которых указана и тематика, и уровень сложности; на них можно отрабатывать технику. Конечно, если эти задачи не вызывают проблем и пишутся со скоростью от 10 шт/час, тогда можно почитать, например, "Алгоритмы и программы: решение олимпиадных задач" И.Н. Порублева и А.Б. Ставровского и что-то еще более серьезное из уже перечислявшегося: разные лекции, книга Кормена, статьи с e-maxx.ru... И постоянно решать — соревнований и архивов существует достаточно много.
(На всякий случай: принцип выбора источников не "где больше", а где "методическое изложение")

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Конечно, если эти задачи не вызывают проблем и пишутся со скоростью от 10 шт/час

    Тогда попробуйте сдать все 600)

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

Чтобы чего-то достичь, надо иметь математический склад ума, уметь придумывать всякие неочевидные вещи, не лениться и решать больше задач. Школьные/университетские дисциплины почти всегда далеки от олимпиад, так что трудно сказать, чтобы они сильно помогали — для олимпиад нужна специальная подготовка.

Лично я с зеленого уровня до фиолетово-оранжевого прокачался, решив на тимусе пару сотен задач, попутно выучив несколько приемов и алгоритов.

И вот классный видеокурс (расчитан на синих, может зеленых): http://www.intuit.ru/department/algorithms/basicalgos/1

Автору: вышеприведенный видеокурс не совсем для начинающих: что-то надо все-таки уметь для его восприятия. Начинающие — это серые. И да, этот курс есть по ссылке 6.1

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

    Спасибо, исправил. Да, есть, но там их очень много и не хотелось бы тратить время выбирая где лучше, а где хуже. Лучше сразу воспользоваться чужим опытом и не терять время.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Тренировки, это, бесспорно, очень хорошо, но что же это такое? PS за видеокурс спасибо.

»
12 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

Да, почему-то еще никто ничего не написал по этому поводу. Нужно обязательно научиться программировать. Причем учиться программировать только на олимпиадных задачах — плохо. Нужно писать достаточно большие программы. Когда вы напишете что-нибудь работающее тысяч на десять строк кода, скорее всего, вы начнете понимать, где нужно писать функцию, где можно написать длиннее, но точно не ошибиться, и так далее.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    Не могу не поддержать. Написание больших программ — довольно эффективный способ приучиться продумывать "архитектуру", "внутренние связи" и т.п. В общем, никакого вреда, кроме пользы. КМК, для начала могут быть небезынтересны проекты из книг М.В. Мозгового (есть по Delphi ("Занимательное программирование"), по C++; книжка про компиляторы тоже хороша, хоть и может показаться не совсем по теме).

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я, наверное, начал наиболее правильно структурировать программу только после того, как полгода насмотрелся чужого C++ кода на работе. :)

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      По привычке пытался взламывать? :)

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        Скорее, как обычно, пытался разобраться. :):)

»
12 лет назад, # |
Rev. 4   Проголосовать: нравится +46 Проголосовать: не нравится

6.2) http://www.lektorium.tv/course/?id=22823 Картинка с главной страницы:

1+2+..+N=O(N). ? ?Нет,я не буду это смотреть..Читайте книги!

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

    Возможно, он рассуждает, почему так делать нельзя? :) Например, можно еще порассуждать так:

    Пусть T(n) = O(n), тогда:

    Хотя правильно

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +47 Проголосовать: не нравится

      Я нисколько не сомневаюсь,что он знает, как правильно, и приводит это как пример ошибки.

      Но для меня это равносильно тому,что там бы были уроки по арифметике и было бы на главной странице написано 2+2=5,или уроки по русскому языку с грамматической ошибкой на доске. Меня это просто очень повеселило:)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится

    Оказывается, qsort в худшем случае работает за O(n)