таймкоды: сортировки, множество перестановок, алгоритм проверки упорядоченности, отношение порядка, fool sort, bubble sort, choice sort, insert sort 0:00 вступление 2:54 код фильтрация (сортировка, как в жизни) 3:32 в программировании сортировка - это упорядочивание 3:45 первым делом вопрос: Что упорядочивать. Должна быть структура данных, которая подразумевает наличие порядка. Например, список. Упорядочение по возрастанию, неубыванию, не строгому возрастанию, что равенства допускает 5:08 когда мы подаём в параметр функции массив (A), она его отсортировывает и возвращает отсортированный массив (A') - это новый массив или старый изменяется. Есть два варианта сортировок: 1) inplace мы должны обладать ссылкой на этот массив, передать по адресу ( по ссылке) и должно происходить действие ровно над этим самым объектом. 2) not inplace - старый массив остаётся в исходном состоянии, а сортировка выдаёт новый массив, новый объект с новым идентификатором. Если есть альтернативное имя подаваемого в функцию массива, то объект сам либо изменится либо нет 6:25 стандартная сортировка A.sort() меняет сам массив, inplace 6:38 B = sorted(A) - не сортирует массив А, создаёт новый B отсортированных значений. Т.е. sorted(A) ничего не делает с А, не меняет его. И получаемое значение нужно сохранить в другом массиве 7:00 сортировка подразумевает не заполнение новыми значениями, а некоторую перестановку старых 8:00 множество перестановок, теория групп 9:36 есть некоторые допустимые перестановки и возникает вопрос: какие состояния достижимы, какие нет 10:12 допустим все элементы разные, есть N шт. элементов, тогда существует перестановок N! факториал 13:08 генерация всевозможных перестановок в Питоне модуль itertools permutations 13:49 тождественная перестановка 15:33 алгоритм проверки упорядоченности быстрее поиска перестановки 17:26 поиск имеет комбинаторную структуру, мощность - N! Чтобы добраться до ответа, количество операций N! 18:04 оценка скорости алгоритма производится по наихудшему случаю 19:37 реализация поиск будет не систематический через permutations, а функция shuffle (случайный поиск) в библиотеке random 20:16 сортировка обезьяны bogosort неэффективный алгоритм 23:21 что нельзя отсортировать: 1) Объект неизменяемый кортеж tuple 2) структуры данных, в которых нет порядка двоичные деревья поиска, хэш таблицы, множества set 3) несравнимые типы 27:00 важно понимать какому множеству принадлежат элементы 27:20 мы должны понимать применимость. Списки могут содержать разные типы 28:05 4) оператор сравнения (==, > , b, b > c, то a > c (транзитивность по неравенству) и если a == b, b == c, то a==c (транзитивность по равенству) 31:46 пример не подходящего случая объектов А = ["камень", "ножницы", "бумага"]. Множества, где нет транзитивности: К > Н, Н > Б, Б > К => невозможно отсортировать принципиально, не важно каким алгоритмом сортировки 33:06 упорядочение подразумевает и ближний и дальний порядок 34:40 пример 2 сортировка неприменима 36:32 международный стандарт IEEE 754 - 2008 г. дробных чисел float, double. Вещественные числа тоже нельзя отсортировать 37:19 Универсальные Квадратичные Сортировки (3: bubble sort, choice sort, insert sort) 38:48 квадратичные сортировки: скорость сортировки O(N**2) 39:03 проверка факта отсортированности 39:10 fool sort сортировка дурака неквадратичная O(N**3). Локальный порядок означает глобальный (для чисел) 41:24 транзитивность (отношение порядка) работает для целых чисел, для множеств - нет, а для дробных не совсем 48:05 bubble sort сортировка методом пузырька 51:28 массив из одного элемента упорядочен всегда 51:31 сортировка пузырьком. На маленьких размерах является одной из самых оптимальных по количеству действий, она не требует рекурсии, вызова функций, стеков, она очень экономная 53:19 choice sort сортировка выбором. Неустойчивая сортировка 56:24 устойчивость - равные друг другу элементы не окажутся перепутанными относительно своего исходного порядка. Не всегда равенство с точки зрения упорядочения означает что элементы абсолютно одинаковы и неотличимы 57:24 пример устойчивости по ФИО и возрасту 58:24 insert sort сортировка вставкой ( еще существуют квадратичные сортировки: гномья gnome sort, шелла shell sort) 59:17 инвариантом называется некоторое условие, которое в цикле всегда остаётся истинным 59:37 те элементы, что слева - упорядочены 1:01:01 чтобы слева не выйти в ошибку. Устойчивая сортировка, требует довольно мало операций. Удобна, когда элементы поступают по одному 1:10:41 код проверка отсортированности is_ascending() по возрастанию 1:13:54 код test_asc() делает массивы и указывает их отсортированность или нет и test_sort 1:18:42 код fool_sort() bubble_sort() Разъяснение тем лекции (читать, скачать бесплатно в формате docx) в группе ВК "Основы Программирования (кодинг) на Python" (osnovyprogrammirovania)
Тимофей Хириянов, вам нет равных в качестве подачи информации за единицу времени. Благодарю! Было бы интересно послушать вас по поводу практики оптимизации кода, оценки затрат по памяти и т.п.
Давно закончил университет, в начале карьеры на каждом собеседовании спрашивали сортировки, и они очень хорошо запомнились. Но эта лекция просто отпад. Спасибо за отличное видео
Если вкратце - ошибки округления. Во всём программировании флоты - это, ПО ОПРЕДЕЛЕНИЮ, не абсолютно точное представление числа. Любое сравнение флотов - это вообще глобальная проблема. Нерешаемая. Там ВСЕГДА есть какая-то погрешность. Просто погуглите float equality на stackoverflow - и откроется бездна страданий. Как следствие, не зная конкретной области использования для функции (не зная, какие вообще там данные ожидаются, каковы возможные значения) - невозможно написать универсальную сортировку. Вернее, универсальную-то написать можно. Но она ГАРАНТИРОВАННО будет отказывать в определённых эдж-кейсах.
Преподаватель чудак на букву 'М', пионерская организация уничтожена уже больше 30 лет, но нет, нужно всё равно бросить свои испоражнения в неё. Но всё таки хочу сказать спасибо за урок.
Просмотрел многое из выложенного , и для меня лично это выглядит так : посмотрите как это здорово и интересно . Вопрос : а что с этим делать ? Ответ : а хрен его знает . Раз это блог МФТИ то как мне думается должно быть видео с написанием очень полезной программы для какого то конкретного предприятия ( как пример ) .
Фуххх ! Вас не закрыли как учёного который сотрудничает с иностранными агентами. Сейчас это в тренде. Тем более ваши ролики на ютуб, а он запрещён в РФ
Что делать во время бессонницы? Конечно же изучать языки программирования.
Отличный преподаватель с отличной подачей информации. Спасибо за лекцию!
таймкоды: сортировки, множество перестановок, алгоритм проверки упорядоченности, отношение порядка, fool sort, bubble sort, choice sort, insert sort
0:00 вступление
2:54 код фильтрация (сортировка, как в жизни)
3:32 в программировании сортировка - это упорядочивание
3:45 первым делом вопрос: Что упорядочивать. Должна быть структура данных, которая подразумевает наличие порядка. Например, список. Упорядочение по возрастанию, неубыванию, не строгому возрастанию, что равенства допускает
5:08 когда мы подаём в параметр функции массив (A), она его отсортировывает и возвращает отсортированный массив (A') - это новый массив или старый изменяется. Есть два варианта сортировок: 1) inplace мы должны обладать ссылкой на этот массив, передать по адресу ( по ссылке) и должно происходить действие ровно над этим самым объектом. 2) not inplace - старый массив остаётся в исходном состоянии, а сортировка выдаёт новый массив, новый объект с новым идентификатором. Если есть альтернативное имя подаваемого в функцию массива, то объект сам либо изменится либо нет
6:25 стандартная сортировка A.sort() меняет сам массив, inplace
6:38 B = sorted(A) - не сортирует массив А, создаёт новый B отсортированных значений. Т.е. sorted(A) ничего не делает с А, не меняет его. И получаемое значение нужно сохранить в другом массиве
7:00 сортировка подразумевает не заполнение новыми значениями, а некоторую перестановку старых
8:00 множество перестановок, теория групп
9:36 есть некоторые допустимые перестановки и возникает вопрос: какие состояния достижимы, какие нет
10:12 допустим все элементы разные, есть N шт. элементов, тогда существует перестановок N! факториал
13:08 генерация всевозможных перестановок в Питоне модуль itertools permutations
13:49 тождественная перестановка
15:33 алгоритм проверки упорядоченности быстрее поиска перестановки
17:26 поиск имеет комбинаторную структуру, мощность - N! Чтобы добраться до ответа, количество операций N!
18:04 оценка скорости алгоритма производится по наихудшему случаю
19:37 реализация поиск будет не систематический через permutations, а функция shuffle (случайный поиск) в библиотеке random
20:16 сортировка обезьяны bogosort неэффективный алгоритм
23:21 что нельзя отсортировать: 1) Объект неизменяемый кортеж tuple 2) структуры данных, в которых нет порядка двоичные деревья поиска, хэш таблицы, множества set 3) несравнимые типы
27:00 важно понимать какому множеству принадлежат элементы
27:20 мы должны понимать применимость. Списки могут содержать разные типы
28:05 4) оператор сравнения (==, > , b, b > c, то a > c (транзитивность по неравенству) и если a == b, b == c, то a==c (транзитивность по равенству)
31:46 пример не подходящего случая объектов А = ["камень", "ножницы", "бумага"]. Множества, где нет транзитивности: К > Н, Н > Б, Б > К => невозможно отсортировать принципиально, не важно каким алгоритмом сортировки
33:06 упорядочение подразумевает и ближний и дальний порядок
34:40 пример 2 сортировка неприменима
36:32 международный стандарт IEEE 754 - 2008 г. дробных чисел float, double. Вещественные числа тоже нельзя отсортировать
37:19 Универсальные Квадратичные Сортировки (3: bubble sort, choice sort, insert sort)
38:48 квадратичные сортировки: скорость сортировки O(N**2)
39:03 проверка факта отсортированности
39:10 fool sort сортировка дурака неквадратичная O(N**3). Локальный порядок означает глобальный (для чисел)
41:24 транзитивность (отношение порядка) работает для целых чисел, для множеств - нет, а для дробных не совсем
48:05 bubble sort сортировка методом пузырька
51:28 массив из одного элемента упорядочен всегда
51:31 сортировка пузырьком. На маленьких размерах является одной из самых оптимальных по количеству действий, она не требует рекурсии, вызова функций, стеков, она очень экономная
53:19 choice sort сортировка выбором. Неустойчивая сортировка
56:24 устойчивость - равные друг другу элементы не окажутся перепутанными относительно своего исходного порядка. Не всегда равенство с точки зрения упорядочения означает что элементы абсолютно одинаковы и неотличимы
57:24 пример устойчивости по ФИО и возрасту
58:24 insert sort сортировка вставкой ( еще существуют квадратичные сортировки: гномья gnome sort, шелла shell sort)
59:17 инвариантом называется некоторое условие, которое в цикле всегда остаётся истинным
59:37 те элементы, что слева - упорядочены
1:01:01 чтобы слева не выйти в ошибку. Устойчивая сортировка, требует довольно мало операций. Удобна, когда элементы поступают по одному
1:10:41 код проверка отсортированности is_ascending() по возрастанию
1:13:54 код test_asc() делает массивы и указывает их отсортированность или нет и test_sort
1:18:42 код fool_sort() bubble_sort()
Разъяснение тем лекции (читать, скачать бесплатно в формате docx) в группе ВК "Основы Программирования (кодинг) на Python" (osnovyprogrammirovania)
Тимофей Хириянов, вам нет равных в качестве подачи информации за единицу времени. Благодарю! Было бы интересно послушать вас по поводу практики оптимизации кода, оценки затрат по памяти и т.п.
я сейчас учу с# и эта лекция ну прям шикарно зашла. Маленький Ваня с детства впитывает таланты программирования 😀
Сначала лойс,потом просмотр! Спасибо,что делитесь своими знаниями!
Как всегда, прекрасная лекция. Спасибо большое
Давно закончил университет, в начале карьеры на каждом собеседовании спрашивали сортировки, и они очень хорошо запомнились. Но эта лекция просто отпад. Спасибо за отличное видео
Спасибо огромное.
Чтобы сделать задачи надо сделать задачи, не надейся на удачу разделяй на под задачи
чтобы сдееелать матреешку надо сдееелать матреешку :D
@@pe5ha но кто сконструирует последнюю матрешку?
👏👍
А что не так с сортировкой дробных чисел?
Если вкратце - ошибки округления.
Во всём программировании флоты - это, ПО ОПРЕДЕЛЕНИЮ, не абсолютно точное представление числа. Любое сравнение флотов - это вообще глобальная проблема. Нерешаемая. Там ВСЕГДА есть какая-то погрешность. Просто погуглите float equality на stackoverflow - и откроется бездна страданий.
Как следствие, не зная конкретной области использования для функции (не зная, какие вообще там данные ожидаются, каковы возможные значения) - невозможно написать универсальную сортировку. Вернее, универсальную-то написать можно. Но она ГАРАНТИРОВАННО будет отказывать в определённых эдж-кейсах.
Наличие в множестве дробных чисел с плавающей точкой состояния "Not a Number" ломает отношение порядка.
Преподаватель чудак на букву 'М', пионерская организация уничтожена уже больше 30 лет, но нет, нужно всё равно бросить свои испоражнения в неё. Но всё таки хочу сказать спасибо за урок.
Просмотрел многое из выложенного , и для меня лично это выглядит так : посмотрите как это здорово и интересно . Вопрос : а что с этим делать ? Ответ : а хрен его знает . Раз это блог МФТИ то как мне думается должно быть видео с написанием очень полезной программы для какого то конкретного предприятия ( как пример ) .
Фуххх ! Вас не закрыли как учёного который сотрудничает с иностранными агентами. Сейчас это в тренде. Тем более ваши ролики на ютуб, а он запрещён в РФ
ютуб запрещен? это что-то новенькое. Не выдумывайте.
Ахахахаха
@@ander1475 вообще то запрещён. запрещён и заблокирован разные слова если что
@@ander1475 АХАХАХАХА