Коды из лекций 13, 14 и 15

Добрый день, коллеги!
Стали доступными коды из трех последних лекций. Я не конвертировал их в презентации, а сохранил исходный формат C#. Их можно скачать по следующим ссылкам:
- красно-черное дерево (узел, дерево);
- хэш-таблица;
- алгоритмы сортировки.
С уважением, Михаил Баранов.

Уважаемые коллеги!
Мы закончили учебную часть нашего курса! Надеемся, что курс оказался полезным и Вы приобрели новые знания. Спасибо всем!
Пожалуйста, приходите 3 июня на завершающую часть, где будут вручены сертификаты об окончании курса. Ждем Вас!
С уважением, Михаил Баранов.

Расписание

Уважаемые коллеги!
Напоминаем Вам, что ближайшая лекция состоится 24 мая.
С уважением, Михаил Баранов.

Коды из лекций 12

Уважаемые коллеги!
Представляем Вам очередную, двенадцатую, порцию кодов из лекций. Найти можно здесь.
С уважением, Михаил Баранов.

Задание

Уважаемые коллеги!
Представляем Вам очередное задание для самостоятельной работы по курсу "Алгоритмы и структуры данных".

Напишите на естественном языке или псевдокоде алгоритм, определяющий, какой треугольник можно построить из трех длин сторон: равносторонний, равнобедренный, разносторонний или из данных длин сторон невозможно построить треугольник.

Ввод: длины сторон a, b, c.

Вывод: тип треугольника, который можно построить из сторон a, b, c (равносторонний, равнобедренный, разносторонний, никакой).

С уважением, Михаил Баранов.

Коды из лекций 11

Добрый день, коллеги!
Представляем 11 порцию кодов из лекций. Найти можно по этой ссылке.
С уважением, Михаил Баранов.

Задание

Добрый день, коллеги!
Для всех, кто не смог придти на лекцию 29 апреля и еще не присылал решение, остается в силе предыдущее задание. Пожалуйста, присылайте Ваши решения.
С уважением, Михаил Баранов.

Коды из лекций 10

Добрый день, коллеги!
Представляем очередную порцию слайдов с кодами из лекций. Располагаются по этой ссылке.
С уважением, Михаил Баранов.

Задание

Добрый день, коллеги!
Представляем Вам очередное задание для самостоятельной работы по курсу "Алгоритмы и структуры данных".

Напишите на естественном языке или на псевдокоде алгоритм поиска самого длинного пути в бинарном дереве поиска от корня к листовому узлу (или, что то же, алгоритм нахождения максимальной глубины в бинарном дереве поиска).

Ввод: ссылка на бинарное дерево поиска tree.

Вывод: число d, обозначающее максимальную глубину дерева tree.

С уважением, Михаил Баранов.

Коды из лекций 9

Добрый день, коллеги!
На очереди девятая порция кодов из лекций. Найти можно по ссылке.
С уважением, Михаил Баранов.

Задание+

Добрый день, коллеги!
Представляем Вам небольшое дополнительное задание для самостоятельной работы. За него можно будет получить дополнительный балл.

Напишите на естественном языке или на псевдокоде алгоритм поиска узла в бинарном дереве поиска, содержащего минимальное значение и алгоритм поиска узла, содержащего максимальное значение.

Ввод: ссылка на бинарное дерево поиска tree.

Вывод: узел, содержащий минимальное/максимальное значение в дереве tree.

С уважением, Михаил Баранов.

Коды из лекций 8

Добрый день, коллеги!
Представляем Вам восьмую порцию кодов из лекций. Найти можно здесь.
С уважением, Михаил Баранов.

Задание

Добрый день, коллеги!
Представляем Вам очередное задание для самостоятельной работы по курсу "Алгоритмы и структуры данных".

Напишите на естественном языке или на псевдокоде алгоритм обохода дерева SiblingTree по уровням, т.е. сначала посещается корень, затем все дочерние узлы (имеющие уровень 1), затем дочерние узлы дочерних узлов (имеющие уровень 2) и т.д., так что последовательно посещаются все узлы на одном уровне. Дерево SiblingTree состоит из узлов, каждый из которых имеет следующую структуру:

- значение, хранимое в данном узле;

- ссылка на узел, являющийся самым левым ребенком данного узла;

- ссылка на родительский узел для данного узла;

- ссылка на следующего (при отображении слева направо и корне вверху) брата/сестру.

Ввод: ссылка tree на дерево типа SiblingTree, ссылка на метод Visit(node), который выполняет некоторую работу при посещении узла node дерева.

Вывод: выполнение метода Visit(node) для каждого узла дерева tree по уровням, от меньшего уровня к большему.

С уважением, Михаил Баранов.

Лекция от 19 апреля

Добрый день, коллеги!
В лекции от 19 апреля мы лишь начали написание бинарного дерева поиска и дерева SiblingTree. Код будет опубликован после того, как мы закончим создание этих типов. Если Вам нужен текущий код для анализа, пожалуйста, присылайте соответствующий запрос мне на почту misha_bar@mail.ru.
С уважением, Михаил Баранов.

Курс в целом и успеваемость

Добрый день, коллеги!
На данном этапе очень бы хотелось оценить ход курса "Алгоритмы и структуры данных" как со стороны материала, способов его изложения, так и со стороны успеваемости всех слушателей курса. Пожалуйста, пишите в комментариях к данному сообщению или мне на почту misha_bar@mail.ru Ваши впечатления, замечания, пожелания по поводу курса, просто общие слова. Возможно, Вы бы хотели обсудить какую-то определенную тему, скажем, на последнем, дополнительном занятии, или встретиться и подвести итоги по пройденному материалу.
В свою очередь, здесь, в этом сообщении, будет публиковаться некоторый рейтинг успеваемости слушателей, которые хотя бы раз присылали свои решения к заданиям.
На текущий момент таблица успеваемости выглядит следующим образом (последнее обновление 31 мая; красный цвет означает, что по итогам выполнения домашних заданий, курс усвоен менее, чем на 50%, оранжевый - от 50% до 80%, зеленый - усвоено более 80%):
 Андрей Кашин (97%)
 Виталий Зубков (76%)
 Алексей Хоченков (74%)
 Дмитрий Вакин (72.5%)
 Александр Масалин (69%)
 Наталья Станкова (61%)
 Александр Рыбаков (58%)
 Илья Левцов (50%)
 Анна Смородина (40%)
 Александр Николаев (37%)

Ждем Ваши комментарии и письма!
С уважением, Михаил Баранов.

Задание

Добрый день, коллеги!

Представляем Вам очередное задание для самостоятельной работы по курсу "Алгоритмы и структуры данных".

Разработайте тип данных, представляющий список управления доступом (Access Control List, ACL). Под разработкой понимается описание типа данных на естественном языке: поддерживаемые операции, внутренние структуры данных, обоснование выбора этих структур. 

В простом варианте, ACL должен представлять собой тип данных, содержащий список пользователей, которым разрешен доступ к какому-то ресурсу. 

В более сложном (и необязательном) варианте, ACL должен различать виды доступа: создание (create), чтение (read), запись (update), удаление (delete), полный доступ (full trust).

Использование данного типа может быть следующим. Логические объекты в системе (например, файлы или документы) содержат указатель на экземпляр списка управления доступом. Данный экземпляр содержит список пользователей, имеющих разрешение на получение доступа к этому логическому объекту (к файлу или документу). Клиент может проверить, разрешен ли доступ или разрешен ли конкретный вид доступа какому-то пользователю.

С уважением, Михаил Баранов.

Коды из лекций 7

Добрый день, коллеги!
Представляем Вам седьмую порцию кодов из лекций. Как и всегда, найти их можно по ссылке.
С уважением, Михаил Баранов.

Задание

Добрый день, коллеги!
Представляем Вам очередное задание для самостоятельной работы по курсу "Алгоритмы и структуры данных".

Напишите на естественном языке или псевдокоде алгоритм проверки правильности простановки скобок в выражении, используя стек.

Ввод: строковое выражение, содержащее, возможно, кроме прочих символов, скобки различного вида, а именно: (),{},[],<>

Вывод: истина, если все скобки правильно открыты/закрыты, ложь – в противном случае.

Например, на входе может быть строка "class Vector<T> { public Vector() {} }". Здесь все скобки открыты и закрыты верно. А, например, строка "[3+(5*6)/2" имеет незакрытую скобку.

С уважением, Михаил Баранов.

Коды из лекций 6

Добрый день, коллеги!
Представляем Вам шестую порцию кодов из лекций. Найти их можно по этой ссылке.
С уважением, Михаил Баранов.

Задание

Добрый день, коллеги!

Представляем Вам очередное задание для самостоятельной работы по курсу "Алгоритмы и структуры данных".

Напишите план, которым Вы будете руководствоваться при создании типа данных Сетка со следующими совйствами:

1. Сетка (grid) представляет прямоугольник, состоящий из ячеек, в которых хранятся некоторые данные.

2. Ширина и высота сетки задаются при ее создании.

3. Сетка должна позволять работать со всеми ячейками.

Какие внутренние структуры Вы выберете для создания такой сетки? Какие основные операции реализуете?

С уважением, Михаил Баранов.

Коды из лекций 5

Добрый день, коллеги!
Представляем Вам очередную, пятую, порцию кодов из лекций. Они доступны по этой ссылке.
С уважением, Михаил Баранов.

Коды из лекций 4

Добрый день, коллеги!
Представляем очередную порцию слайдов с кодом из лекций. Найти можно здесь.
С уважением, Михаил Баранов.

Задание

Добрый день, коллеги!
Представляем Вашему вниманию очередное задание для самостоятельной работы по курсу "Алгоритмы и структуры данных".

Напишите на естественном языке или псевдокоде алгоритм решения судоку для заданной текущей конфигурации.

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

Вывод: полностью заполненный массив a, удовлетворяющий правилам игры судоку, и представляющий правильное решение, конечную конфигурацию.

Правила игры судоку Вы можете найти здесь.

Как обычно, присылайте Ваши ответы на почтовый ящик misha_bar@mail.ru.

С уважением, Михаил Баранов.

Коды из лекций 3

Добрый день, коллеги!
Публикуем очередную порцию слайдов с кодом из лекций. Их можно найти здесь.
С уважением, Михаил Баранов.

Задание

Добрый день, коллеги!
Представляем Вам очередное задание для самостоятельной работы по курсу "Алгоритмы и структуры данных".
Имеется реализация алгоритма вычисления квадратного корня с использованием итерационной формулы Герона на С#.
Ввод: вещественное число x; вещественное число Epsilon, задающее точность вычислений.
Вывод: квадратный корень из x с точностью Epsilon.
double SquareRoot(double x, double Epsilon)

{

  // squareRoot(n+1) = (x / squareRoot(n) + squareRoot(n)) / 2.0

  double squareRoot = 1.0;

  double currentGuess = ((x / squareRoot) + squareRoot) / 2.0;

  while (Math.Abs(squareRoot - currentGuess) > Epsilon)

  {

    squareRoot = currentGuess;

    currentGuess = ((x / squareRoot) + squareRoot) / 2.0;

  }

  return squareRoot;

}

Необходимо определить инвариант цикла, используемого в алгоритме. Пожалуйста, присылайте Ваши рассуждения, которыми Вы руководствовались, при определении инварианта.

С уважением, Михаил Баранов.

Слайды с кодом

Добрый день, коллеги!
Представляем Вам очередную порцию слайдов с исходным кодом, который мы пишем на лекциях. Найти их можно здесь. Также обещанная ссылка на лекции В.В. Борисенко.
С уважением, Михаил Баранов.

Коды из лекций

Добрый день, коллеги!
Рад сообщить, что теперь слайды с кодом из лекций можно будет найти на нашем сайте. Первая порция находится здесь.
С уважением, Михаил Баранов.

Задание

Добрый день, коллеги!
Представляем Вам задание для самостоятельной работы по курсу "Алгоритмы и структуры данных".

Напишите на естественном языке или на псевдокоде алгоритм возведения вещественного числа в целую степень. Оцените эффективность этого алгоритма в нотации большого О. Постарайтесь написать наиболее эффективный алгоритм.

Ввод: вещественное число a; целое число x.

Вывод: число a в степени x.

Пожалуйста, присылайте Ваши ответы на мой почтовый ящик misha_bar@mail.ru.

С уважением, Михаил Баранов.

Формат общения

Добрый день, коллеги!
В очередной раз хотелось бы сделать несколько объявлений по поводу формата общения по курсу "Алгоритмы и структуры данных".
1. Пожалуйста, пишите мне на электронный почтовый ящик misha_bar@mail.ru, если Вы бы хотели получить исходные коды, которые мы пишем в курсе (но рекомендуется все записывать в ходе лекций. см. п. 2), а также с высказыванием пожеланий и замечаний относительно курса. Только таким ПРЯМЫМ взаимодействием мы сможем продвигаться в сторону решения задач, поставленных перед курсом.
2. На мой взгляд, наиболее эффективно материал усваивается и понимается, когда слушатели сами записывают всю ключевую информацию. Пожалуйста, записывайте код и важные определения в ходе лекций! Это многократно повысит понимание материала, позволит запомнить.
С уважением, Михаил Баранов.

Возобновление работы факультатива

Коллеги, не пора ли нам возобновить работу факультатива? На повестке дня курс лекции "Алгоритмы и структуры данных". Есть живые?