Вопрос 11: Расстояние Левенштейна — это количественная мера различия между двумя
строками. Например, расстояние Левенштейна между словами "Левенштейн" и
"Эйзенштейн" равно трём. В статье о расстоянии Левенштейна и его
применениях приводится другой пример, в котором сравниваются более
длинные "слова". Напишите все буквы, входящие в эти "слова".
Ответ: T, C, G, A.
Зачёт: Т, Ц, Г, А; те же буквы в любом порядке; тимин, цитозин, гуанин, аденин.
Расстояние Левенштейна — это минимальное количество операций вставки
одного символа, удаления одного символа и замены одного символа на
другой, необходимых для превращения одного слова в другое. Это понятие
нашло применение в генетике при сравнении ДНК.
Источник(и):
1. http://ru.wikipedia.org/wiki/Расстояние_Левенштейна
2. http://planetcalc.com/1721/
3. https://web.stanford.edu/class/cs124/lec/med.pdf
Авторы: Михаил Перлин, Юрий Выменец