Лекція 3. Про алгоритми та їхню складність
HTML-код
- Опубликовано: 29 сен 2024
- Якщо бажаєте підтримати (to donate) донатами наш лекторій, щоб було більше заходів та відеоматеріалів:
/ scientificmeetings
Наш спікер: Кирило Сніжко, PhD, інженер-дослідник в CEA Grenoble (Франція). Сфера наукових інтересів: теоретична фізика в галузях конденсованих середовищ та квантових обчислень.
Анотація циклу:
Ви хочете знати, що таке квантові комп’ютери? Чому навколо них стільки галасу? Чого справді можна від них очікувати і коли? У цьому циклі лекцій ми пригадаємо шкільну фізику та шкільну геометрію, познайомимося з теорією алгоритмів, і вийдемо на рівень, коли зможемо зрозуміти, як працюють квантові комп’ютери. Тоді ми поговоримо про їхні останні досягнення: що вони можуть, які є проблеми, куди рухається галузь і як швидко.
Очікуваний вік слухачів: від учнів 5-го класу до допитливих людей 256 років.
Анотація лекції 3. Про алгоритми та їхню складність:
Цього разу ми знову забудемо про квантовий світ та поринемо у світ класичних комп’ютерів. Що таке алгоритм? Наскільки складно вишикувати клас за зростом? Що спільного між словником та списком контактів у вашому телефоні? І чому у власній кімнаті варто прибирати?
#Квантові_обчислення #алгоритм #Кирило_Сніжко #scientific_meetings #наукові_зустрічі
Якщо бажаєте підтримати (to donate) донатами наш лекторій, щоб було більше заходів та відеоматеріалів:
www.patreon.com/scientificmeetings
Чудова лекція
Дякую!
Дякую за перегляд!
Дякую. Одразу скажу, що я не програміст. Але як для звичайної людини підхід видається дивним. По перше складність сортування 5 та 10 чисел ( у 4,5 рази складніше або у 2 рази). Якщо 10 чисел були б десятковими дробами з трьома або чотирма знаками після коми, то сортування десяти чисел зайняло б не 27 секунд. Далі, нівелювання коефіцієнту 1/2. Це ціла половина, це дуже багато. Ви відчули б різницю, якщо Вам запропонували працювати 4 години замість 8 за ту саму зарплатню?
Дякую за запитання. Ви підняли справді цікаву тему. Оцінка складності алгоритмів базується на певних припущеннях і переслідує певні цілі.
Наприклад, ми припускаємо, що обробка кожного числа бере однакову кількість часу. Маєте рацію: людині простіше порівняти 85 та 38, аніж 2,5385 та 2,5358. У комп'ютера це бере однаковий час. Крім того, людина має властивість втомлюватися - коли чисел стане 100, ця втома дасться взнаки дуже швидко. Тому ми робимо певні припущення, які більш-менш відповідають платформі, що виконуватиме алгоритм. І тоді ми можемо отримати певну оцінку складності алгоритму. Цю оцінку потім можна покращити, використовуючи кращі припущення - якщо захочеться.
І ця оцінка переслідує певні цілі. У даному разі нам важливо зрозуміти, як складність зростає із розміром задачі. Порівняємо ми n1^2 із n2^2 чи 0,5*n1^2 із 0,5*n2^2, складність зростає в (n1/n2)^2 разів. Для цієї цілі коефіцієнт 1/2 виявляється неважливим. Хоча, якщо нам оцінка складності потрібна, щоб дізнатися конкретний час роботи, то ця 1/2 нам буде потрібна.
Користуючись вашою аналогією із зарплатнею, поставте себе на місце не працівника, а підприємця. Він хоче створити компанію та має оцінити потрібні кошти. У нього є 10 тисяч євро, а оцінка каже, що потрібно мільйон. Очевидно, що цю компанію за свої гроші він не запустить - і навіть якщо оцінка неточна: потрібно пів мільйона чи два мільйони, це не міняє ситуацію принципово. Йому треба шукати інвестиції на масштабі мільйонів. Якщо в нього є такі джерела інвестицій, то один мільйон потрібен чи два, це питання уточненої оцінки. Спочатку треба зрозуміти масштаб.
Так що, чим можна нехтувати, а чим не варто, - це визначається цілями.
гарна лекція. Нарешті стало зрозуміло з алгоритмами що до чого))