Информатика на Python, лекция 4, ФБВТ МФТИ (2023)
Вставка
- Опубліковано 31 тра 2024
- Курс информатики для 1-го курса ФБВТ МФТИ (2023).
Лекция 4, алгоритмы с использованием запоминания в список
Таймкоды:
00:00 Вступление
01:29 2 задачи (перестановка чисел)
10:45 Решето Эратосфена
42:58 Шифрование данных
01:04:21 Сортировка подсчетом
Плейлист с лекциями 1-го курса ФБВТ МФТИ (2023): • 2023 ФБВТ Информатика ...
Снял и смонтировал видео: youtube.com/@antonoreshkin?si...
Спасибо Вам огромное, что выкладываете лекции для общего доступа. Смотрю с огромным удовольствием!
К сожалению, в программу на доске закралась ошибка. Вычеркивать числа в дипазоне после корень(n) надо все-таки с шагом x, а не все подряд: for i in range(x * x, n + 1, x), иначе при любом n программа будет находить только два простых числа - 2 и 3
@@mika34444 У Вас в голове какая-то каша из убогих преподов и убогих студентов, один Вы весь в белом.
"Заячьи уши торчат нашего образования:" - Вашего - это какого? Американского? Я вот ясно вижу уши западопоклонничества и либеральной пропаганды... или это не уши вовсе, но не суть. То, что он несёт не по теме - ну, все мы не без недостатков.
Но Тимофей, по факту - один из лучший преподавателей, что я видел, так что Ваши претензии совершенно непонятны. Вы видели лучше? Приведите пример, чтобы и мы могли ознакомиться. Человек кучу времени потратил на студентов, да ещё и на публикацию замечательных лекций в общем доступе.
Да, конкретно в этом курсе информатики всё как-то печально, но ранние лекции по питону - шикарны, и это заметно по количеству просмотров.
Так что комментарий выше - это, как Вы правильно выразились, "полный трэш". О чём, зачем? Нет ответов. Похоже, просто кто-то, сидя в отхожем месте, понажимал в экран смартфона, оставляя свой цифровой пахнущий след в интернете.
Спасибо! Конечно, вы правы. К сожалению, пропустил в коде на доске. Но содержательное объяснение верное, так что будем считать это опечаткой.
@@tkhirianov вне всякого сомнения конечно же опечатка, большое спасибо за то, что ваши лекции есть в свободном доступе!
Ну как же это может быть опечаткой, если никто не печатал? Это описка!
Спасибо, что вы это написали, потому что я уже думал может я чего то недопонимаю😅😅, но всё таки это опечатка
Посмотрев все предыдущие в этом плейлисте, начиная с этого видео наступил момент, когда сложно оторваться
Спасибо Вам!!! Все ваши лекции это просто кладезь,
очень надеюсь что вы продолжите выкладывать материал, ибо я уж думал что вы решили попрощаться с каналом. ( почти год видео не было )
Спасибо студенту, который взялся записывать, обрабатывать и выкладывать.
А то у меня совсем рук не хватает.
@@tkhirianovспасибо тебе, безызвестный герой
Здраствуйте. Очень жду Вашу пятую лекцию.
Спасибо, Вам большое за такой материал.
Спасибо большое!
Спасибо за видео!
Спасибо!
таймкоды: алгоритм сдвига на один влево, вправо, Решето Эратосфена, тест простоты, логические выражения, шифрование, RSA, сортировка подсчётом, частотный анализ
0:00 вступление. Алгоритмы с запоминанием в Список
На прошлой лекции, в потоковых алгоритмах, в которых была последовательность и мы делали некоторую стат. выжимку или наоборот генерировали последовательность, мы не концентрировались на Запоминании и оно там было лишним. Если возможно обслужить поток и посчитать эту выжимку, не запоминая всю эту последовательность - это хорошо (Сопрограммы)
1:02 В этой лекции: задачи, в которых запоминание данных является необходимостью
1:30 дана последовательность чисел (X1 X2 X3....Xn-1 Xn). I) Вывести первое число последним (X2 X3....Xn-1 Xn X1). II) Вывести последнее число первым (Xn X1 X2 X3....Xn-1). Скорость решения одинаковая. O(N). Есть существенное отличие по памяти
4:57 код I
4:58 сколько памяти: 2 ячейки: первая хранить и вторая - пробрасывать поэлементно
5:12 задача II . Если это не файл, который уже хранит на диске список, и до последнего можно отмотать. Это, например, данные термометра, которые поступают нон стоп и вам нужно последнее число этого дня записать первым. Значит: надо его дождаться. а все элементы - хранить. Выход: создавать структуру данных, массив, список, в который будем аппендить (добавлять в конец) поэлементно. Возникают варианты: 1) если мы заранее знаем его длинну, то сразу можем его заготовить list(range(N-1)), 2) создать пустой и заполнять при помощи метода аппенд (append())
6:40 списки list изменяемой длины в Питоне, они динамические массивы ссылок. Ссылок, потому что тип у каждого элемента может быть разный, потому что элемент - суть, ссылка на объект. Они не хранятся в самом списке. 3) через генератор
8:38 два цикла вместо одного не меняет принципиально асимптотику по скорости, это меняет асимптотику по памяти. Ёмкостная сложность O(N)
9:19 код II
10:24 Решето Эратосфена: есть таблица всех натуральных чисел, кроме единицы, начиная с двойки. Остаются только простые числа, составные вытрясаются, не_делится_ни_на_одно_число меньшее его
12:28 простым называется число, у которого нет нетривиальных делителей. Тривиальные делители: единица и само число
18:37 подсчитать количество делителей аналогично тесту простоты
20:25 мы должны действовать Последовательно
22:47 шифрования RSA
23:36 объяснение решения. нужно помнить (хранить) статус зачёркнутости числа (факт зачёркнуто\незачёркнуто - логическое, булевское значение), сами числа хранить не надо
26:26 в проверке if sieve[x] == True: В алгебре логики есть атомарные высказывания (которые могут быть истинными и могут быть ложными), например, (("Петька - дурак")=правда)=точняк.... Если мы высказывание пишем, то оно Логическое само по себе, оно уже либо правда либо ложь. Поэтому пишем просто сразу if sieve[x]: оттуда просто достанется булевское значение. То, что число простое гарантируется последовательностью действий, что иксы проходятся снизу вверх, от младших к старшим
29:32 на доске ОШИБКА! for x in range(x*x, n+1, x) С шагом x. если число простое - бежим дальше, начиная с икс квадрата
30:26 в алгоритме число, которое имеет смысл - это индекс доступа списка
32:27 множества set
35:00 генератор множества, set comprehension списковое включение, только для множества, в фигурных скобках {}
36:12 код решето Эратосфена (поиска простых чисел)
40:02 тест простоты для одного числа
40:57 для скорости проверки вероятностный тест простоты - тест простоты ФермА Для любого n>1 выбираем a>1, вычисляем an−1(modn), если результат не 1, то n составное, если 1, то n - слабовозможно простое. Числа Кармайкла
42:41 приватный ключ, публичного ключа, шифрование симметричное
45:16 шифр Атбаш, очень древний а < --> я, б ю
46:44 перебор всех возможных ключей
47:27 шифр Цезаря плох тем, что ключей мало (в англ алфавите 26, в русском 33)
48:35 взлом сбоку, защищённое соединение
50:30 ключ публичный +ключ приватный. Шифрование сообщений (encoded message, шифротекст) RSA
57:38 разложение на множители является криптоустойчивым
58:29 наука, которая занимается построением шифрования наз криптография (скрытопись, тайнопись). Математическая область - криптоаналитика, криптоанализ
1:00:08 моноалфавитная замена
1:03:39 как осуществить частотный анализ
1:04:24 сортировка подсчётом
1:04:57 сайт code.org в разделе час кода - про взлом шифрования, там частоты отбражаются и можно порасшифровывать текст
1:06:37 N цифр десятичной системы счисления ( от 0 до 9 = 10 разных)
1:08:17 быстрые сортировки добиваются O(Nlog2N)
1:09:12 существует алгоритм который отсортирует за - O(N) за - 1 проход:
1:09:35 нужно создать массив частот
1:11:54 что такое отсортированный массив. Мы храним в массиве не сами числа
1:13:35 код частотного анализа
1:14:21 код сортировки подсчётом по возрастанию
1:14:43 асимптотика O(N+M) если M много меньше N, то можно ею и пренебречь
1:17:20 сортировку подсчётом не применяют, потому что она не универсальная
Разъяснение тем лекции (читать, скачать бесплатно в формате docx) в группе ВК "Основы Программирования (кодинг) на Python" (osnovyprogrammirovania)
Спасибо.
Тимофей, спасибо вам, дорогой наш просветитель.
👍👍👍
сопрограммы? интересно
👏👍
Тимофей, классический вопрос 2023: заменят ли нейросети программистов? 🙃
Подскажите пож-а , на какой уровень подготовки предназначены данные лекции?
10 класс, в современных реалиях "технологический профиль". Рекомендую учебник К.Ю. Полякова.
1:03:29 Мария Стюарт
Эту девушку звали.. Альберт Эйнштейн
Я первый ура!
Здравствуйте . Вопрос Тимофею Фёдоровичу : На сайте Микрософт ясно написано что услуги и продажи продуктов компании на территории РФ прекращены . А интернет магазины как например Валдберис продают ОС с ключами активации . Почему ???
Не знаю. Но я советую вообще не устанавливать продукты Майкрософт. Если только есть такая возможность, лучше пользоваться свободным ПО, т.е. со свободными лицензиями и открытым исходным кодом.
@@tkhirianov astra linux подойдет?
Устаёте ли вы уже от преподавания ?Выглядите устало немного
уфф как чел долго обьяснял что массив с булевыми значениями оставляет на месте себя булевое значение, и при записи If massive[x], massive оставит вместо себя значение икса(индекса) который вы введете, и получится if true:(выполнится) или if false: (то есть не выполнится)
суть в том что нужно изначально обьяснять что If берет 1 булевое значение а не вычисляет что истинно а что ложно, этим занимаются операторы сравнения, if ничего не сравнивает.
короче чел заведомо ложную инфу вкидывает по программированию на основах чтобы потом в частных случаях выглядеть как высококлассный учитель.
типа само название if это скорее подьебка от разрабов языка, на деле это вопрос "Сделать?" и вы вписываете "да" или "нет".
1 == 1 (да) , 1==2 (нет)
а в целом так
"Сделать? (1
амос там пророк
Реально много воды. Как это относится к программированию на Питоне, не пойму? Это должно читаться на лекциях по математике....
Курс называется "Информатика", а "на Python" в названии видео фигурирует лишь для понимания того, синтаксис какого языка будет использоваться. Потому что всё равно каким-то языком пользоваться придётся. Точно так же там могло быть указано "На русском языке".
По алгоритмам, структурам данных и практическим работам есть отдельные ролики на канале.
В - Внимательность.
Ну наконец-то!)
Два года, и я буду у вас учиться !!
Спасибо!