Схема на раздела

◄1 май - 7 май
►15 май - 21 май
  • Разделяй и владей
    • Въведение
      • Идея - за да решим задача с размер N, я разделяме на няколко по-малки независими. Например на 2 задачи с размер N/2. После има стъпка на обединяване отговорите на подзадачите.
      • Приложения
        • най-лесно се вижда за паралелни задачи. Разделяме задача на няколко подзадачи и всяка от поздачаите може да се изполнява независимо на отделна машина (или процесор).
        • ако подзадачите са една и съща задача, може да се пресметнат само веднъж. например бързо повдигане на степен.
        • получаване на нов по-добър алгоритъм.
    • Класически задачи разделяй и владей
      • Сортиране чрез сливане - ние избирам как да разделим
      • Quick sort - случайно се избира как да се раздели
      • Намиране на K-ти по големина елемент
        • подобно на quick sort.
        • избор на разделящ елемент - разделяне на 5торки и избор на техните медиани и т.н. до получаване на един елемент.
    • Задача за намиране на най-близки точки
      • Дадени са N точки в равнината. Търсят се двете точки, най-близо една до друга
      • Равнината се разделя на две части от права.
      • Решават се две двойно по-малки задачи.
      • Провера дали най-малкото разстояние не е между точки от подзадачите
        • Тривиална проверка на всяка точка от едната подзадача със всяка точка от другата подзадача води до подобрение с константа (N^2).
        • Проверките могат да се ограничат до точки различаващи се по едната координата с по-малко от най-добрия отговор на подзадачите. При подходяща имплементация може да се направи O(N*log^2(N))
    • Задача за бързо умножение на числа
      • Числата се разделят на части.
      • Всяка от частите си я представяме като цифра и умножаваме като две "двуцифрени" числа. Умножението на цифрите са подзадачите. Може да се направи с 3 подзадачи с размер N/2, ако по-дългото число за умножение е било с дължина N.
◄1 май - 7 май
►15 май - 21 май