Практика языка C (МФТИ, 2023-2024). Семинар 2.1. Простые числа.
Рет қаралды 7,960
Күн бұрынПрактические занятия по языку C на первом курсе МФТИ. Кафедра информатики.
На этом семинаре мы разберёмся с двумя крайне важными концепциями -- со структурами в языке и с асимптотикой алгоритмов. Для иллюстрации и того и другого я выбрал простые числа.
Семинарист: Константин Владимиров.
Дата: 22 сентября 2023 года.
Съёмка: Марк Гончаров.
Звук: Юлий Тарасов.
Предыдущий семинар: • Практика языка C (МФТИ...
Следующий семинар: • Практика языка C (МФТИ...
Слайды к занятиям: cs.mipt.ru/wp/?page_id=7775
Примеры кода: github.com/tilir/c-graduate
Задачник: olymp1.vdi.mipt.ru/
Timeline
00:00 Простые числа
06:25 Решето Эратосфена
15:02 Структуры в C
20:55 Площадь треугольника
27:03 Структуры для решета
32:15 Время решать задачи
35:40 O-нотация
51:43 Улучшаем алгоритм P
01:00:05 Упражнения с асимптотикой
01:08:00 Ревью кода и завершение
Errata:
* пока нет
@Tiolych 8 ай бұрын
Желаю вам крепкого здоровья !
@rg99999 4 ай бұрын
На 1:12:45 скорее всего имеется в виду "спекулятвино увеличить" надо перед циклом for,а не внутри, как может показаться, "в надежде, что не нарвемся на if", а если все-такие нарвались, то откатить Count на один. Спасибо за видосы)
@artorios5192 8 ай бұрын
Только зашёл)
@dsorvq Ай бұрын
Асимптотика на 1:07:20 скорее всего несколько выше, чем O(n), нам ведь еще нужно на каждой итерации считать что-то вроде lcm(i, result). O(n * log(lcm(2,...,n))) точно подойдет, но наверное, можно уже
@tilir Ай бұрын
Если числа M-битные, это добавляет множитель O(logM). Но для 32-битных чисел это константа, поэтому O(N) -- мы зависим только от общего количества чисел и съедаем их по одному.
@artorios5192 8 ай бұрын
От разрядности чисел?)
@dolmat3434 8 ай бұрын
Константин, а где теоретическая часть курса? Лекции будут залиты на ютуб ?
@tilir 8 ай бұрын
Насколько я понимаю нет. Лекции читаю не я и их никуда не выкладывают. Поэтому я стараюсь записать все семинары максимально самодостаточными. Если вам не хватает теории, читайте K&R.
@bv9876 7 ай бұрын
Спасибо, что выкладываете такой полезный материал! (жаль только ссылка на слайды ко 2-му семинару нерабочая почему-то).
@tilir 7 ай бұрын
Пофиксил проверьте
@bv9876 7 ай бұрын
@@tilirСпасибо, работает )
@lisenkoevg 7 ай бұрын
На 30:55 формула написана математическим языком, соответственно правильно будет использовать для натурального логарифма символы "ln", а не "log".
@tilir 7 ай бұрын
G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers, 4th Ed., Oxford 1975, footnote to paragraph 1.7: "log x is, of course, the 'Naperian' logarithm of x, to base e. 'Common' logarithms have no mathematical interest".
@lisenkoevg 7 ай бұрын
@@tilirДа, так. Но если заглянуть в русские школьные учебники по алгебре, то там "ln". Например, если загуглить (коммент с ссылкой наверно ютьюб не пропустит) "натуральный логарифм мфти", то одним из первых попадается учебник "Лекции по математическому анализу" Г.Е. Иванова. ("Содержание материала соответствует программе кафедры высшей математики МФТИ." Я в свое время учился по подобному учебнику, поэтому такая ваша запись меня немного запутала )
@tilir 7 ай бұрын
Не надо путать матан и теорию чисел. Разные традиции обозначений.
@lisenkoevg 7 ай бұрын
@@tilir Понятно.
@iamdozerq 2 ай бұрын
По поводу синтаксиса -> - на ютубе есть паренек, новосибирский, но вещает только на английском - он взял какой то очень простой компилятор сей и добавил точке право делать тоже самое что делает ->, и попробовал покомпилить библиотеки заменив эту стрелку точкой - ничего не сломалось. Технически от стрелки можно избавиться в пользу точки, зачем она нужна не понятно.
@tilir 2 ай бұрын
В языке C она нужна только потому, что это хорошая дизамбигуация для читающего код. Но кроме того это интересный случай гениального технического видения наперёд. В C++ это раскрылось: точка осталась обозначать id-expression, а стрелка стала перегружаемой и приобрела drill-down поведение и разница стала существенной.
@user-gl1bg3ef5m 8 ай бұрын
1:00:50: Я был бы чуть более аккуратным в вопросах O нотаций для комплексных функций. Для модуля, конечно, всё работает также, но вот с самими функциями...
@tilir 8 ай бұрын
Я не ввожу этих понятий для комплексных функций. Время и память это действительные числа. Вообще интересная идея -- найти комплекснозначный ресурс....
@user-gl1bg3ef5m 8 ай бұрын
@@tilir (из Википедии): "Ресу́рс (от фр. ressource) - источник покрытия нужд, потребностей." Я думаю, квантовые состояния системы (волновые функции) подошли бы под это описания
@voffkavoffkaa3539 8 ай бұрын
Доброго дня будите ли дублировать канал на рутубе или в ВК ?
@tilir 8 ай бұрын
На рутубе давно есть: rutube.ru/channel/10218561
@napalm20005 5 ай бұрын
Ближайшим циркулярным к 200 будет 199
@nullptr_or_null8301 8 ай бұрын
Смотрел до 4-ой минуты, и сразу на вопрос как определить простое число, в двоичной системе счисления, ответ достаточно просто, если последний разряд (младший) оканчивается на 0, то число не простое, если на 1 то число простое, если же в десятичной то да, там уже сложнее.
@tilir 8 ай бұрын
Вы неправы. В двоичной системе число 9 имеет вид 1001. Оно тем не менее составное.
@nullptr_or_null8301 8 ай бұрын
@@tilir Спасибо за поправку,согласен не прав.
@unclemax1 8 ай бұрын
Ты, видимо, хотел сказать о четном и нечетном числе)
@nullptr_or_null8301 8 ай бұрын
@@unclemax1 Да, именно так
Konstantin Vladimirov
Рет қаралды 6 М.
Konstantin Vladimirov
Рет қаралды 8 М.
Konstantin Vladimirov
Рет қаралды 4,3 М.
Konstantin Vladimirov
Рет қаралды 4,6 М.