Вопросы по курсу.
На момент переезда был открыт вопрос – делать ли третье задание (множество на основе БСП). Так вот, не знаю, что такое «БСП», но задание реализовать нужно, тем более, что оно не сложное.
Перезагрузить сервер с мудлом за 20 минут до дедлайна - какой цинизм. 
Сервер с мудлом не перезагружался.
Ну не знаю. Вчера в 23:40 кинулся заливать работу, но moodle и форум лежали - поднялись примерно 00:10
Проблемы были у сети университета, она была недоступна.
у меня такая же ситуация вчера была: не мог задание загрузить
Лежала вся сеть ЮФУ. Мне кажется, это хороший урок о том, что задания не нужно делать в последний момент. Такова жизнь.
Ну, на почту задания получил, сгодится. Но замечание о том, что не стоит до последних минут затягивать, мне кажется весьма разумным.
Вопрос. Задание сдал в классе, черновик залил, а отправить забыл… Теперь задание “висит” как не сданное. Что с ним делать?
Да ничего не делать, раз сдали. На практике просто указать на это преподавателю, и всё.
А если так регулярно делать: в процессе работы заливать и обновлять версии черновика, а если что-то в жизни случится, замотаться в других делах и не успеть нажать кнопку “Отправить задание”, то будет ли это критично? Т.е. так делать нежелательно, но баллы будут за это ставится или не будут, или всё равно - нажато ли там чего, лишь бы залито???
Не важно, черновик это, или представлено к оценке – главное, чтобы была возможность выставить оценку.
Если $m_h$ — минимальное число вершин в AVL-дереве высоты $h$. Как показать, что $m_{h+2} = m_{h+1} + m_h + 1$?
Это $h(L) + h® + 1$?
Ну да, это практически очевидно, Вы всё правильно поняли.
Если AVL-дерево имеет высоту $h+2$, то, согласно определению, одно из поддеревьев корня имеет высоту $h+1$, а второе – $h+1$ или $h$. Для того, чтобы исходное дерево имело минимальное число вершин, левое и правое поддеревья корня должны иметь минимальное число вершин, тогда получаем: $$m_{h+2}=1 + m_{h+1} + min{m_{h+1},m_h}$$Осталось только показать, что $m_{h+1} > m_h$, что можно принять как очевидное, а можно и более строго попробовать доказать вспомогательное утверждение, что из AVL-дерева всегда можно удалить лист, и полученное дерево также будет AVL-деревом. Ну, остальное просто, хотя для полноты надо еще проверить верность утверждения для базиса – деревьев высотой 0 и 1, к примеру.
А как тут формулы-то по-человечески вставлять?
1 лайк
Выполнить задание «Частотный словарь» с использованием реализованных выше структур данных и сбалансированных деревьев. В качестве основы для структуры данных «Множество» использовать тот вариант сбалансированного дерева поиска, который был реализован в предыдущем задании.
Что это за задание, и зачем реализовывать множество на основе предыдущего задания (сбалансированные деревья)?
Эта задача обсуждалась на лекции, и представляет собой простейший словарь, где ключ - слово, а значение по ключу - кол-во вхождений слова в текст. Другими словами, нода представляется в виде пары ключ-значение, т.е. D[слово] равно какому-то целочисленному значению - кол-ву вхождений слова в текст.
Надеюсь, словарь не надо делать на основе кучи?
Зря надеетесь. Если эта надежда связана с предположением о том, что преподаватель опять заставляет использовать неэффективные алгоритмы, могу предложить такой вариант: если Вы реализуете это задание по-своему, и докажете эффективность реализации, то получите x2 баллов. Не сможете доказать эффективность или «изобретете велосипед» – x0, причём выбор структуры для реализации ассоциативного массива оптимизацией не является.
Кстати, пояснение по заданию в Moodle обновлено.
Институт математики, механики и компьютерных наук ЮФУ, 2005–2021