(2 курс ФИИТ) Алгоритмы и структуры данных

Вопросы по курсу.

На момент переезда был открыт вопрос – делать ли третье задание (множество на основе БСП). Так вот, не знаю, что такое «БСП», но задание реализовать нужно, тем более, что оно не сложное.

Перезагрузить сервер с мудлом за 20 минут до дедлайна - какой цинизм. :grimacing:

Сервер с мудлом не перезагружался.

Ну не знаю. Вчера в 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 симпатия

5 сообщений перенесены в новую тему: Пишем формулы и учим Маркдаун

Выполнить задание «Частотный словарь» с использованием реализованных выше структур данных и сбалансированных деревьев. В качестве основы для структуры данных «Множество» использовать тот вариант сбалансированного дерева поиска, который был реализован в предыдущем задании.

Что это за задание, и зачем реализовывать множество на основе предыдущего задания (сбалансированные деревья)?

Эта задача обсуждалась на лекции, и представляет собой простейший словарь, где ключ - слово, а значение по ключу - кол-во вхождений слова в текст. Другими словами, нода представляется в виде пары ключ-значение, т.е. D[слово] равно какому-то целочисленному значению - кол-ву вхождений слова в текст.

Надеюсь, словарь не надо делать на основе кучи?

Зря надеетесь. Если эта надежда связана с предположением о том, что преподаватель опять заставляет использовать неэффективные алгоритмы, могу предложить такой вариант: если Вы реализуете это задание по-своему, и докажете эффективность реализации, то получите x2 баллов. Не сможете доказать эффективность или «изобретете велосипед» – x0, причём выбор структуры для реализации ассоциативного массива оптимизацией не является.

Кстати, пояснение по заданию в Moodle обновлено.

 Институт математики, механики и компьютерных наук ЮФУ, 2005–2021
Администрация форума: В.Н. Брагилевский, С.С. Михалкович, А.М. Пеленицын
Yandex.Metrica