Седмичен изглед

  • Главна

    Сгъване на всички Разгъване на всички

  • 22 февруари - 28 февруари

    Конспект по ДАА-практикум (за всички групи):

    1. Запознаване с online judge системи и състезателното програмиране

    2. Сортиране О(n^2) - bubble sort, selection sort, insertion sort.

    Сортиране count sort

    3. Сортиране О(nlgn) - quick sort, heap sort, merge sort

    4. Binary search

    5. Обхождане на непретеглени графи: DFS, BFS, топологично сортиране

    6. Обхождане на претеглени графи: Dijkstra, Floyd, Ford-Bellman

    7. Минимално покриващо дърво: Prim, Kruskal

    8. Динамично програмиране


    Упражнение 1:

    Запознахме се с judge системата на http://judge.openfmi.net:9280/ (ако някой все още няма регистрация, ще е хубаво да си направи) и решавахме глупави задачки от там, за да свикнем с нея. Там ще бъдат публикувани всички домашни и контролни, които ще правим през семестъра,

    Няколко важни неща:

    1. В условието на всяка задача ще е описан строго форматът, в който се въвеждат входните данни и се извеждат изходните. Не слагайте подсещащи или уточняващи съобщения. Решенията се проверяват от компютър.
    2. Изхода трябва да завършва с нов ред, за да бъде обработен правилно от проверяващата програма.
    3. Оценяването на всяко решение става, чрез няколко (обикновено) 10 предварително зададени теста. Ако всички те минат успешно системата ще върне резултат от вида ok ok ok ok ok ... Ако на някой тест програмата ви даде грешен отговор системата ще върне wa (wrong answer).
    4. При оценяването освен верността на изхода в тестовите случаи се проверява и:
      • времето за изпълнение - ако е превишено системата ще върне tl (time limit)
      • използвана памет - ако е превишена системата ще върне ml (memory limit)
    5. Ако има грешка по време на изпълнението системата ще върне re (runtime error) - напр. ако барате извън масив или делите на нула. 
    6. Ако има грешка по време на компилацията - ce (compilation error)


    Друго
    На когото му се решават задачки:

    Тези правят периодично онлайн състезания (освен това ако имате добри резултати можете да сложите връзка към профила в CV-то си; дори е възможно досадните ейчш ари да ви налазят докато си решавате там)

    За тренировка можете да ползвате:

    • http://acm.timus.ru/ (тук има доста задачи, разделени по категории)
    • https://arena.maycamp.com/ (задачки от български ученически състезания; Обърнете внимание, че това е арена, различна от нашата, на която ще правим контролни и домашни!)
    • http://bgcoder.com/ 
    • http://www.spoj.com/
    • http://judge.openfmi.net:9080/spoj0/ (задачи от български студентски състезания по програмиране)
    • https://projecteuler.net/ (по-математически ориентирани задачи)
    • и още много други, за които не се сещам сега

    Малко повече за състезателното програмиране: https://en.wikipedia.org/wiki/Competitive_programming

    Материали за подготовка:

    Algorithms & Data Structures:
    TopCoder algorithm tutorials
    Introduction to Algorithms (Third Edition) - Cormen, Leiserson, Rivest
    Програмиране =++Алгоритми - Преслав Наков, Панайот Добриков
    Algorithms, 4th edition - Robert Sedgewick, Kevin Wayne
    The Algorithm Design Manual, 2nd edition - Steven Skiena
    The Art of Computer Programming - Donald Knuth

    C:
    C reference guide
    The C book
    C file handling commands
    C and C++ tutorial 

    C++:
    C++ online reference
    C++ FAQ lite
    Thinking in C++ (Second Edition) - Bruce Eckel
    The C++ Programming Language (Third Edition) - Bjarne Stroustrup

    STL:
    Standard Template Library Programmers Guide
    STL online reference
    C++ STL tutorial

    Изключително полезен сайт: http://informatika.bg/. В раздела "Лекции" има голяма част от материала, който ще бъде преподаден по ДАА-практикум. Авторът се е стремил да изгражда интуиция у четящия, в резултат на което са се получили доста сполучливи лекции, по които можете да се подготвяте.


  • 29 февруари - 6 март

    КН 1-2 група

    Нямахме, защото беше 3ти март.



  • 7 март - 13 март

    КН 1-2 група

    Решавахме следните задачи от http://judge.openfmi.net:9280/ (ако някой все още няма регистрация ще е хубаво да си направи).


    КН, групи 5 и 6 - Сложности на алгоритми, бавни сортировки 

    Визуализации на сортиранията - цък.

    За всяка от следващите задачи Ви препоръчвам да си напишете на ръка бавните сортировки, а не да ползвате std::sort(...) (поне за сега). Целта е да се упражните да ги напишете поне веднъж. 

    2013 Упражнение 2 - Лесни Сортировки:

    Шоколади - сложете си всичко в една структура и си дефинирайте operator< на база полетата в нея – day, month, year, index; оттам нататък задачата става тривиална;

    CERN - лесно се сравняват числата лексикографски, ако ги прочетем (и разглеждаме) като стрингове; да се ползва InsertionSort; ако работим с обекти от класа string, да се ползва swap(...) варианта при InsertionSort (оптимизирали са го и върви много добре)

    2011 ДАА - Контролно 3:

    Medians – ползва се Insertion Sort

    ДрДруги:

    http://informatika.bg/problems/DAA.2011.Trosver/Trosver.pdf, online judge: http://acm.timus.ru/problem.aspx?space=1&num=1290 – задачата има очевидно решение; по-сложното е да се обоснове защо точно това решение е правилно;


  • 14 март - 20 март

    КН 1-2 група

    Мен ме няма днес. Ще сте с Влади Владимиров в 309 или 122. Планът е да пишете бързи сортировки и да упражните с подходящи задачи ~Марин 

    КН, групи 5 и 6 - Бързи сортирания

    На практикума тази седмица разгледахме следните бързи сортирания - QuickSort, MergeSort, HeapSort.

    Решавахме следните задачи:

    2013 Упражнение 3 - Бързи Сортировки:

    Бързо сортиране - задачата се решава с използването на някой от бързите алгоритми. Моят съвет е да пробвате да я решите и с бавните алгоритми за сортиране, за да видите колко по-бавно се държат те с толкова голям вход.

    PermSwap - намиране броя на инверсиите в масив – приложение на MergeSort.

    Drinking game - приложение на HeapSort. Можете да решите задачата за 100 точки и с използването на priority_queue.

    Задачи за упражнение вкъщи:

    2015 Домашно 1 Бързи сортирания:

    Събития - задача, подобна на Шоколади от предния път. Разликата е, че тук трябва да използвате някое от бързите сортирания.

    2015 Домашно 2:

    График - това е малко по-трикова задача, чието решение на пръв поглед не изглежда особено интуитивно. Решава се като първо всяко събитие се сортира в нарастващ ред по край (забележете – „край‘) и, ако 2 събития имат еднакъв край, се сортират по начало. След това започваме от първото събитие - вземаме го и гледаме следващото, ако то не се засича с предното, вземаме и него, ако се засича, не го вземаме и продължаваме напред по същия начин.

  • 21 март - 26 март

    КН, групи 5 и 6 - Counting Sort, Двоично търсене, Троично търсене

    Задачи, които решихме:

    1) 2013 Контролно 1 - Coaching Sort - задачата се решава с директна имплементация на Counting Sort

    2) 2015 ДАА Тренировка 1 -  Sysadmin - задачата се решава с Binary Search по отговора. В какви граници може да бъде нашият отговор? Т.е. какви са минималните и максималните възможни дължини за тези поне K парчета кабел с еднаква дължина? Минималната възможна дължина за всяко от тези парчета е 1 (=left), а максималната е 100,000,000 (=right) (може вместо 1*10^8, да ползвате дължината на най-дългото парче кабел от входа, но така ще направите линейно повече операции). Имайки този range от възможни отговори, правим Binary search в него. На всяка стъпка хващаме mid = (left+right)/2, като след това, линейно по входните парчета кабел, проверяваме колко парчета кабел с дължина mid можем да изрежем от тях. Ако се получава < K, трябва да намалим дължината (за да се увеличи бройката) и съответно right = mid-1. Ако се получава >= K, запомняме текущия отговор (mid) и пробваме с по-голяма дължина, т.е. left = mid+1. Update-ваме mid, т.е. mid = (left+right) / 2, и повтаряме същите стъпки докато left <= right. Накрая печатаме отговора.

    3) 2013 Упражнение 4 - Разделяй и владей:

    Сума - В тази задача е важно да забележим малкия брой суми, за които трябва да проверяваме, а именно <= 10. За всяка една сума (sum[i]), проверяваме, във вече сортирания масив от N елемента, дали може да се получи като сбор на 2 елемента от него по следния начин: вземаме първия елемент (a[0]), намираме разликата между сумата и текущия елемент - diff = sum[i] - a[0], и търсим diff с двоично търсене в масива с N елемента, като внимаваме да не счетем, че сме намерили diff, а реално да сме намерили a[0]. T.e. ако sum[i] = 2, а a[0] = 1 и трябва да търсим diff = sum - a[0] = 2 - 1 = 1, трябва да изключим от търсенето a[0].

    Задачи за упражнение:

    1) 2013 Упражнение 4 - Разделяй и владей:

    Алкохолици

    Намери числата

    Тръби

    2) 2015 Домашно 2 Двоично търсене:

    Elliot


  • 28 март - 3 април

    КН, групи 5 и 6 - BFS, DFS

    Задачи, които решихме:

    1) 2013 Упражнение 5 - Графи:

    Ябълки - Задачата се решава с BFS в мрежа, като този път входните данни са малко по-особени. Координатите на първата ябълка ги четете стандартно, а за координатите на втората, можете да ползвате следния начин:

    if( scanf("%d %d", &x, &y) == 2 )

            apples.push_back(make_pair(x-1, y-1));, 

    където apples е от тип vector < pair<int, int> > apples; и служи да си запишем в него координатите на ябълките. Кодът на тази задача ще бъде качен в муудъл. Обърнете внимание на начина, по който достъпваме съседните клетки на текущата клетка с използването на масива delta[][].

    Школа - Задачата се решава с DFS, като целта е да преброим свързаните компоненти в неориентиран граф. Пускаме DFS от всеки необходен връх, обхождаме графа, като маркираме всеки връх през който минем. Ако след обхождането, все още има необходени върхове, пускаме DFS от някой от тях. Колкото пъти пуснем DFS, това ни е отговорът на задачата.

    Задачи за упражнение:

    1) 2013 Упражнение 5 - Графи:

    Лабиринт 

    2) 2012 - Извънредно контролно:

    Рицари

    3) 2015 (летен) Контролно 2:

    Още една редица

    • Файл icon
      Apples Файл
    • Файл icon
      BFS Файл
    • Файл icon
      DFS Файл

    • КН 1-2

      Взехме двоично търсене.

      Видяхме, че за да търсим, не необходимо да разполагаме с всички стойности от колекцията, в която търсим. Конкретно правихме задачата, в която е дадена монотонно растяща функция, чийсто стойности са от - безк до +безк, и се търси коренай. Това разбира се стана с двоично търсене по аргумента. 

      Гледахме и задачата:

      Elliot 

      Напомням, че задачата Sysadmin от тук , която разглеждахме преди време, също се решава с двоично търсене. Като там търсим двоично отговора. 

    • Файл icon
      Eliot 1 Файл

      Решение, в което представяме масива суми като растяща редица (както обсъдихме на упражнението ако някой елемент е по-малък от предишния, то винаги ще избираме поне предишния).

    • Файл icon
      Eliot 2 Файл

      Второто решение, за което говорихме. Сортираме заявките и след това обхождаме линейно (въднъж) масива със суми.

  • 4 април - 10 април

    КН, групи 5 и 6 - Продължение  на BFS, Минимални пътища в графи - алгоритъм на Dijkstra

    Задачи, които решихме:

    1) 2015 (летен) Контролно 2:

    Още една редица - Задачата се решава с BFS (макар и малко странно да изглежда отначало). Първоначално слагаме в опашката само числото А. След това на всеки ход вземаме един елемент от опашката, прилагаме върху него двете операции, описани в условието, и новополучените два елемента ги слагаме в опашката, ако още не са били слагани в нея. В момента, в който от опашката извадим число равно на B, отговорът на задачата е броят нива + 1, които сме обходили с BFS-то.

    2) 2015 Домашно 5:

    Пешо - Задачата се решава с директно прилагане на Dijkstra. Пускаме Dijkstra от всяка болница и гледаме всеки път каква е сумата от всички dist[i], за които i не е болница. От всички суми, минималната е нашият отговор.

    Задачи за упражнение:

    1) 2015 Домашно 5:

    Cheating

    2) 2015 (летен) Контролно 2: 

    Пътища

    3) Домашно Дейкстра:

    Екскурзия

    4) 2014 Домашно Dijkstra:

    Превъртял

    • Файл icon
      Dijkstra Файл
    • КН 1-2 група

      Разгредаме начините за представяне на граф в паметта:

      • матрица на съседство
      • списък на съседите
      • списък на ребрата

      За всяко от тях видяхме каква е сложността за проверка дали има ребро между два върха и обхождане на всички съседи между на връх:

      _

      		има ли ребро (u,v) обхождане на съседите на връх u памет
      матрица на съседствоO(1) O(N) N*N
      списък на съседите O(logD) O(D) N*D
      списък на ребрата
      		 O(logE) O(max(logE, D)) E

      където N е броят на върховете, D е най-голямата степен на ребро и E и броят на ребрата.

      Разгледахме алгоритмите BFS, DFS и Dijsktra и решихме няколко задачи от http://judge.openfmi.net:9280/practice/open_contest?contest_id=39

      • Школа
      • Диаметър

       

  • 11 април - 17 април

    КН, групи 5 и 6:  (Floyd-Warshall, Ford-Bellman)

    Тази седмица взехме алгоритъма на Floyd-Warshall за намиране на най-кратките пътища между всеки два върха в граф за O(N^3), където N е броят на върховете в графа. Алгоритъмът е коректен дори когато в графа има ребра с отрицателна дължина, за разлика от Dijkstra, където алгоритъмът не изкарва верни резултати и е неприложим.
    Също така, разгледахме и алгоритъма на Ford-Bellman за намиране на краткия път между един конкретен връх и всички останали за O(N*M), където N е броят на върховете в графа, а M е броят ребра. Този алгоритъм е приложим също, когато искаме да проверим дали в графа има отрицателен цикъл (такъв със сума на ребрата си по-малка от 0). Ако има такъв, който е достижим от началния връх, тогава не можем да говорим за минимален път в графа. Защо? Защото можем да се въртим до безкрай в отрицателния цикъл и така минималният ни път да става все по-малък.
    И двата алгоритъма могат да се прилагат върху ориентирани и неориентирани графи.

    Задача, която решихме: Имайки матрица на съседство на граф, да се направи съответната и матрица на достижимост (на позиция (i, j) стои 1, ако от връх i можем да достигнем връх j, или 0 в противен случай).

  • 18 април - 24 април

  • 25 април - 1 май

    КН, Групи 5 и 6: Покриващи дървета, Минимални покриващи дървета, Алгоритъм на Крускал

    Задача, която решихме:
    2015 Домашно 6 - И пак пътища :)

    Задачи за упражнение:
    Контролно 3 2016 - Хипертелепорт
    Домашно 2015/2016 - Поддръжка

  • 2 май - 8 май

  • 9 май - 15 май

  • 16 май - 22 май

  • 23 май - 29 май

  • 30 май - 5 юни

    КН, Групи 1 и 2:  Динамично програмиране

    Задачи, които решихме:

    2-те примерни задачи от лекцията по Динамично програмиране.

    2014 Домашно Динамично: Первази

    Задачи за упражнение:

    ДАА - контролно 2 (есен 2012): Паркетиране

    2012 Упражнение - Динамични: Всички 8 на брой задачи

  • 6 юни - 12 юни

    КН, Групи 1 и 2: Динамично програмиране (продължение)

    Задачи, които решихме:

    ДАА - контролно 2 (есен 2012) - Паркетиране

    Турнир за купата на Декана 2009 - B.Fuel

    2011 ДАА - Контролно 2 - Разправия (Известна още като "Братска подялба")

    Задача за раницата (Knapsack problem)

    Задачи за упражнение:

    2015 ДАА Тренировка 2 - D.Fuel (Разликите с тази от spoj0 са, че ограниченията за входните данни са по-големи, а ограничението по време - по-малко. Тук ще трябва да напишете итеративно решение, за да имате на всички тестове "ok").