АиСД S01E01. Алгоритмы. Оценка времени. Сортировка слиянием.

Алгоритмы и структуры данных. Семестр 1. Лекция 1.
На первой лекции мы обсудили, что такое алгоритм и как измерять его эффективность, а так же рассмотрели алгоритм сортировки слиянием и оценили время его работы.
Университет ИТМО, 2020 г.

[@42jU29Mp]

6:51 время работы 8:57 модель вычислений 14:12 T(n) для \sum a_i 16:22 O(n) 19:21 T(n) = O(n) 23:23 T(n) = Ω(n) 26:51 for ы 31:18 рекурсивные функции 38:54 сортировка вставками 46:38 сортировка слиянием 1:06:29 T(n)

[@konstantinta2803]

Вижу новую лекцию - ставлю лайк

[@helloworld9018]

Спасибо за лекции!

[@vladimireliseev7602]

Благодарю за лекцию!

[@andreyshudrik1140]

Спасибо, очень понятно и доступно! Приятно слушать !

[@sergeyefimov1692]

Лучшая превьюшка!!!!!!!!

[@dmitrypetrov8491]

Спасибо за лекцию! Новая превьюшка очень понравилась! Мастер теорема как-то совсем косячно написана: О-большое забыто в 1-й и 3-й строчках. Из того, что написано на доске следует, что из верхней оценки на функцию f(n) мы получаем точную оценку на время работы алгоритма T(n)

[@pavelmavrin]

Ну торопился уже под конец, но понятно же, что там тоже асимптотические оценки

[@user-bo7lm3bw9p]

Только начал смотреть, нравится что объяснения не завязаны на синтаксе одного языка.

[@cplusplus4milfs]

Спустя год уже точно можно сказать что оценили достаточно точно

[@user-sz6kn1ib1s]

качество по сравнению с прошлогодней лекцией - топ

[@pavelmavrin]

Ну хуже было сложно сделать) Но еще далеко до идеала, буду улучшать свет и камеру

[@usercommon1]

крутяк

[@jokerguy7054]

when will you start uploading English lectures? Eagerly waiting for these

[@pavelmavrin]

codeforces.com/blog/entry/82336

[@maxploter2272]

В книге "The Algorithm Design Manual" - Steven S. Skiena RAM расшифровывается как random access machine Любопытно почему в лекции random access memory

[@asaki1k]

1:10:45 Можно ещё доказать так, раскрывая формулу T(n) = 2T(n/2) + n = 4T(n/4) + 2n = 8T(n/8) + 3n = ... , можно заметить, что T(n) = 2^i * T(n / 2^i) + in, докажем это: База i = 1 - это исходная формула, Предположим, что для i = k это верно: T(n) = 2^k * T(n / 2^k) + kn = (*) Докажем, что для i = k + 1 это тоже верно: T(n) = 2^(k + 1) * T(n/2^(k + 1)) + (k + 1)n = 2^(k + 1) * T(n/2^(k + 1)) + n + kn = 2^k * (2T(n/2^(k+1)) + n/2^k) + kn = 2^k * T(n / 2^k) + kn = (*), значит, формула верна Возьмём i = log_2(n), тогда T(n) = n * T(1) + log_2(n) * n = n(log_2(n) + T(1)) = O(n * log(n)), т.к. T(1) - константа

[@pavelmavrin]

тоже вариант да

[@user-lk2qh2cb7x]

Ну штош начнем

[@alexxsu]

Отличные лекции, спасибо! В примере со сложностью рекурсии с n/2 (32:30) условие выхода n = 0 никогда не сработает... Мелочь, но цепляет

[@pavelmavrin]

Сработает. Деление нацело же

[@alexxsu]

@@pavelmavrin Да, действительно. Устно это проговаривается, пропустил:) А вот из синтаксиса неочевидно. Спасибо

[@su5k]

а будут ли домашки по этому курсу?

[@ize4wer]

Давно задаюсь этим вопросом, но автор дает лишь лекционную нагрузку. Единственное, удалось найти на github задачи бывших студентов ИТМО, но там нужна система судейства для проверки %) по итогу практика из CLRS, steven halim competitive programming и leetcode.

[@maksimpinchuk7062]

Это курс кт, за домашками обращаться в пииемную комиссию ИТМО факулттет Фитип направление ПМИ

[@webdev56]

Здравствуйте, Павел! Здесь нет ошибки? : " if j=m || (i < n && a[i] < b[j])". Если j=m - true, то в a[i] < b[j] произойдет ошибка - выход за границу b, т.к. последний b[m-1]. kzbin.info/www/bejne/bnPRmqqalqaIg8U

[@pavelmavrin]

Ну я считаю что выражение считается слева направо, как в большинстве языков, поэтому если j=m, то сработает левая часть || и правая считаться не будет

[@arthell]

Это первая лекция по программированию для первокурсников? Надеюсь там подготовленная аудитория)

[@tagaiismailov4235]

Подготовленная. Они там что-то по матаналитически говорили.

[@denisbel9740]

А что на практике разбирается? А есть где посмотреть? 😂

[@user-ns4if6ct1k]

В ИТМО уже начался кружок по олимпиадному программированию?

[@pavelmavrin]

школьный? сейчас вступительная идет

[@user-ns4if6ct1k]

@@pavelmavrin а откуда тогда запись лекций? подумал сначала, что со школьного кружка.

[@pavelmavrin]

нет, это вузовский курс

[@42jU29Mp]

35:00 почему будет 2n?

[@pavelmavrin]

Где? Не вижу

[@42jU29Mp]

@@pavelmavrin Вы проговорили вслух. Действительно, высота полного двоичного дерева будет h = logn + 1, тогда 2^h = 2n. В данном случае это не важно, просто я для себя давно хотел понять

[@42jU29Mp]

upd: Все же нет. h = ⌊log(n)⌋ = ⌈log(n+1)⌉, тогда 2^h

[@annicioua]

PS почему-то лекторы часто не задумываются, что делая корректировки прямо в написанном (стирая, например, что-то равное единице в частном случае - как было в конце лекции) они делают медвежью услугу студентам: студент должен сначала написать старый вариант (где с не равно 1-це), потом новый (где с = 1), а лектор уже "убежал за лес и гору" в материале, ведь лектор просто СТЕР ненужное ему. НЕ НАДО ТАК.

[@pavelmavrin]

Ну сорян. Но тут же видео, можно промотать назад.

[@annicioua]

​@@pavelmavrin у ребят из аудитории на выходе с пары должен остаться читаемый материал, ведь стройный рассказ - это хорошо, но представьте себе, если они не смогут на ютубе отмотать вашу лекцию (что-то случилось с аудиодорожкой, к примеру), а в тетрадке абракадабра.. Минус одна лекция. :((( PS это всё моё личное мнение, вы спокойно можете забить на него болт, но доля рац. зерна в нем существенная, isn't it? PSS прощу прощ. за другой коммент. Я была очень неосторожна в словах. Буду исправляться

[@andreywhiteid]

У вас есть высшее образование? Если нет открою секрет, ТАК ВЕЗДЕ. И ничего, красные дипломы как-то умудряются получать, система образования не развалилась из-за этого

[@tagaiismailov4235]

Купите хорошую стиралку лектору.

[@user-lk2qh2cb7x]

сдохнуть можно я на лекии по матеше был или алгоритмам блять