0:00
[ЗАСТАВКА] [ЗАСТАВКА] Добрый день!
Сегодня мы поговорим про вычислительные аспекты в информатике и,
в частности, про алгоритмы.
Алгоритм — это процедура пошаговая вычисления результата некоторой задачи.
Компьютеры работают, используя алгоритмы.
С помощью алгоритмов программисты и информатики описывают
решение каких-то задач.
Когда у вас даны некоторые данные, и вам нужно, например, собрать геном,
то вам нужно применить алгоритмы сборки генома, чтобы получить собранный геном.
Давайте рассмотрим сложность алгоритмов и какие алгоритмы бывают, что такое
линейные алгоритмы, квадратичные алгоритмы и какие алгоритмы лучше, какие хуже.
Например, давайте рассмотрим задачу вычисления длины максимального контига,
самого длинного контига.
У вас есть набор чисел на входе вашей программы, это длины контигов,
например, 1 еще 1, 2, 3, 7, 5 или 6.
Как среди этих чисел найти максимум?
Сколько нужно сравнений сделать?
Допустим, у вас N таких чисел, и N может быть очень большое,
если у вас сотни тысяч контигов, то N может быть сотни тысяч.
Тут видно, что максимум — это число 7.
Но компьютеру нужно как-то это найти и как-то описать этот
алгоритм пошагово для компьютера.
Как это можно сделать?
Например, берем первое число — единицу — и сравниваем ее со всеми остальными.
С единицей, с двойкой, с тройкой, с семеркой, с пятеркой и с шестеркой.
Если это число окажется самым большим, то это максимум.
Если оно не самое большое,
то есть оно меньше какого-то из сравниваемых чисел, то идем дальше.
Берем следующее число — единицу, сравниваем ее также с единицей, двойкой,
тройкой, семеркой, пятеркой, шестеркой, и оно тоже не является самым большим числом.
И так далее.
Сколько нужно операций, чтобы вычислить максимум?
Для первой единицы — мы ее сравнили с N минус 1 числом.
То есть N минус 1 сравнение мы сделали, вернее, их сделал компьютер.
Дальше следующее число мы сравнили также со всеми оставшимися элементами,
это снова N минус 1.
И так далее.
И мы итого взяли N чисел,
каждое сравнили с каждым и получили N умножить на N минус 1,
что примерно равно N квадрат.
Компьютер умеет делать операции достаточно быстро.
За 1 секунду 1-гигагерцовый процессор умеет делать миллиард операций,
то есть 10 в девятой.
Но допустим, если вам нужно найти среди миллиарда чисел максимальное.
Вам для данного алгоритма нужно сделать N в квадрате сравнений,
то есть 10 в 18 степени операций сравнения.
И это займет время, сопоставимое с временем жизни вселенной.
И такой алгоритм очень неэффективный, вряд ли вы захотите использовать его и
находить максимум с помощью такого алгоритма.
Как можно найти максимум более эффективно?
Например, если у вас даны те же числа,
вы можете присвоить максимум
первому числу, то есть вы берете и говорите, что максимум равен единице.
Это, конечно, неправда.
Но на данный момент времени в данном шаге вычисления максимум равен единице.
Дальше вы смотрите на следующее число.
Если его значение больше, чем наш сохраненный максимум, то вы его изменяете.
Но оно не больше.
Идем дальше, смотрим на двойку.
Двойка явно больше единицы, мы говорим: все, максимум уже не единица, а двойка.
Идем дальше, видим 3.
3 больше, чем 2, максимум равен 3 на данном этапе алгоритма.
Дальше видим 7, 7 больше 3, максимум равен 7.
Идем дальше, смотрим 5, 5 не больше 7, поэтому максимум остается равен 7.
Смотрим на 6, и максимум также остается прежним.
Итого в конце мы получаем ответ 7.
Сколько операций сравнения чисел мы сделали в таком алгоритме?
Мы сравнили максимум с каждым из N чисел,
кроме первого, потому что первое число мы взяли за исходный максимум.
Итого мы сделали N минус 1 операцию сравнения,
что сильно меньше предыдущих N умножить на N минус 1,
то есть это в N раз быстрее наш алгоритм отработал.
В частности, если у нас миллиард чисел,
то такой алгоритм будет работать около 1 секунды на современном компьютере,
на любом ноутбуке, в частности, с которого вы смотрите эту лекцию.
А прошлый алгоритм не завершил бы свое время ну,
свою работу за приемлемое время, больше, чем время жизни вселенной.
Соответственно, выбор эффективных алгоритмов очень важен для решения задач,
и особенно он важен для информатики, где входные данные очень большие.
Когда у вас миллионы или сотни миллионов ридов, то квадратичные алгоритмы
уже работают очень плохо, и нужно применять линейные алгоритмы.
Какие-либо алгоритмы, которые неэффективно обрабатывают данные,
просто не могут быть применимы в этой области.
Из-за этого в информатике все время придумывают более эффективные методы
анализа данных и более эффективные алгоритмы,
для того чтобы их применять к получаемым в эксперименте биологическим данным,
в частности, в геномных экспериментах, о чем мы и
поговорим дальше.
Alla L LapidusProfessor, Department of Cytology and Histology
Николай Вяххи
Павел ДобрынинМладший научный сотрудник
Михаил РайкоПостдок
Екатерина ЧерняеваПостдок
