#5 CS50 на русском 2016 — Структуры данных и сжатие информации

Приветствую Вас, дорогие друзья!
Неделя 5 курса Гарвардского университета по основам программирования CS50 2016 года на русском языке. На пятой Неделе мы изучим структуры данных, что позволит использовать память компьютера эффективнее. В начале Недели 5 вы увидите краткий обзор предыдущей Недели 4, в которой мы рассматривали память компьютера.

00:00:00 — Обзор Недели 4
00:07:22 — Ограничения в массивах
00:10:45 — Списки
00:13:11 — Узлы
00:15:10 — Связанные списки
00:20:39 — Список людей
00:26:52 — Список операций
00:28:14 — Реализация поиска
00:40:11 — Компромиссы в вязанных списках
00:41:26 — Стеки
00:43:57 — Реализация стека
00:47:30 — Очереди
00:49:43 — Реализация очереди
00:54:40 — Типы абстрактных данных
00:56:06 — Мультфильм о стеке и очереди
00:57:53 — Деревья
01:00:59 — Двоичное поисковое дерево
01:07:56 — Реализация дерева
01:14:26 — Код Хаффмана
01:28:42 — Хэш таблицы
01:30:37 — Ящики
01:33:31 — Линейное пробирование
01:36:21 — Отдельные цепочки
01:39:05 — Префиксное дерево

Словарь терминов и структуры данных

Во-первых, я хочу искренне поздравить Вас, дорогие друзья  с тем, что Вы изучили 50% курса Гарвардского университета CS50 на русском 2016. Неделя 5 это середина курса и является последней Неделей, в которой рассматриваются основы того, что происходит в памяти компьютера, ведь во второй половине курса CS50 2016 мы сосредоточимся на таких темах, как протокол передачи данных HTTP, язык Python, SQL, Javascript и т.д.

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

  1. Список — list
  2. Узел — node
  3. Указатель — pointer
  4. Очередь — queue
  5. Дерево — tree
  6. Префиксные деревья — tries

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

Динамическое выделение памяти

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

Для этих целей в программировании существуют связанные списки, которые позволяют динамически получать или отдавать место в памяти компьютера, но, к сожалению, возникает еще одна проблема. Какая именно? Смотрите видео Недели 5 курса Гарвардского университета по основам программирования.

Как реализован стек или очередь queue?

На Неделе 5 курса CS50 на русском рассматривается интересный пример размещения информации в стек. Представьте стопку разносов в столовой или кафе. Идея заключается в том, что когда Вы кладёте разнос на стопку, а потом снова хотите взять разнос, Вы, как правило, берете верхний разнос, а все остальные разносы лежат, как и прежде. Это если бы Вы пришли купить новый iPhone  в магазин Apple в первый же день начала продаж, простояли бы в очереди в ожидании открытия магазина и начала продаж, однако, получили бы свой новый iPhone не в порядке очереди, а после тех, кто пришел в магазин последним. С точки зрения логики, если Вы дадите товар сначала людям, которые ближе к выходу, эти люди выйдут из магазина первыми, в результате чего магазин будет постепенно опустошаться. Но вряд ли Вам понравится такой алгоритм продажи новых iPhone.

Такая же ситуация складывается и в стек, но для того, чтобы справедливость восторжествовала и первый элемент в очереди был использован в первую очередь существует такое понятие, как очередь queue.

Разницу между stack и queue можно легко понять, посмотрев короткометражный мультик на 56-й минуте Недели 5.

Код Хаффмана или азбука Морзе?

Скорее всего нет человека, который бы не знал что такое азбука Морзе. На Неделе 5 курса CS50 на русском 2016 проводится аналогия между азбукой Морзе и кодом Хаффмана. Так вот, интересным моментом азбуки Морзе является использование длинных или коротких сигналов для обозначения той или иной буквы. Основным является то, что самый короткий сигнал используется для буквы E. Все дело в том, что при создании своей азбуки, господин Морзе увидел, что некоторые буквы фигурируют в словах чаще других. Поэтому для того, чтобы сделать передачу информации максимально быстрой, было решено передавать самыми короткими сигналами те символы, которые используются чаще всего, а более длинными сигналами — буквы, которые реже всего используются.

Такой же принцип использует код Хаффмана, который служит для сжатия файлов. Принцип сжатия, например, файла Microsoft Word заключается в том, что для хранения в памяти букв, которые чаще всего используются, используется более короткий набор нулей и единиц. Более того, зная принцип работы кода Хаффмана, Вы можете закодировать информацию, а затем с легкостью расшифровать. Если Вы хотите узнать в каком случае сжатый файл может стать большего размера, нежели первоначальный — смотрите перевод на русский язык Недели 5 курса CS50 Гарвардского университета.

В заключении стоит отметить, что практически весь код программ на Неделе 5 сопровождается использованием рекурсии. Рекурсия является очень эффективным инструментом в плане скорости выполнения в случае, когда Вы выбрасываете половину проблемы прочь, как на Неделе 0 при поиске Майка Смитта.

На следующей Неделе мы рассмотрим протокол передачи данных HTTP.

Приятного просмотра, дорогие друзья!

Поделиться:

Оцените запись:
Notice: Undefined variable: thumbnail in /home/level80/level-80.com/www/wp-content/plugins/wp-postratings/wp-postratings.php on line 1176
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (3 оценок, среднее: 5,00 из 5)
Загрузка...

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*Комментарий - обязательное поле для ввода
* Имя - обязательное поле для ввода
* Email - обязательное поле для ввода