• ,

Дополнительные материалы к лекциям CS50: Week 0 (лекции 1 и 2)

Кто еще не смотрел Гарвардский лекции по основам программирования заходите сюда: javarush.ru/cs50.html =)

Введение. Структура курса CS50


Дополнительные материалы к лекциям CS50
Друзья! Во введении мы напомним (или расскажем, кому как) о структуре CS50. Курс длится 12 недель. Каждую неделю проходит две лекции, а также всякие семинарские занятия и пояснения. Такие вот статьи, как эта, мы будем выпускать по мере готовности лекций. В ней будет краткое описание лекций, конспект «шортов» и дополнительной информации, а также перевод заданий практических заданий.

Лекции нулевой недели осветили следующие вопросы:

  • Двоичная система счисления.
  • ASCII
  • Алгоритмы и алгоритмичность мышления
  • Компиляторы
  • Язык Scratch
  • Булевы выражения
  • Условия
  • Циклы
  • Переменные
  • Функции
  • Массивы
  • Потоки
  • События

Цели нулевой недели:

  • Понять, каким образом информация может быть представлена в цифровом виде.
  • Изучить основные программные конструкции и понятия.
  • Создать собственную анимацию, игру или интерактивное действие на Scratch.
  • Произвести впечатление на друзей =).

CS50 Week 0 (Лекция 1-2): конспект

Алгоритмы

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

А еще, следующий шаг зависит от предыдущего.

Подробнее об алгоритмах можно почитать, например, здесь: ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC#.D0.9C.D0.B0.D1.88.D0.B8.D0.BD.D0.B0_.D0.A2.D1.8C.D1.8E.D1.80.D0.B8.D0.BD.D0.B3.D0.B0

Если знаете английский, вот прекрасная анимация на TED авторства Дэвида Малана:
www.youtube.com/watch?v=6hfOvs8pY1k

Хотя в целом информация в ролике повторяет таковую в лекции=).

Двоичная система счисления

Двоичная система счисления
У нас 10 пальцев, и система — десятичная. То есть, любое, сколь угодно большое число мы можем представить с помощью цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. В зависимости от того, где в числе стоит цифра, она может означать разное: если эта цифра последняя, то она расположена в разряде единиц, предпоследняя — разряд десятков, еще левее — разряд сотен и так далее. По сути, любое число можно расписать в виде суммы цифр, каждая из которых умножена на десять в определенной степени. В случае единиц — нулевой. Например, 1573 = 3*100 + 7*101+5*102+1*103. Число, на степень которого умножаются цифры называется базой системы счисления. Для десятичной системы базой, логично, является десятка.

У компьютера пальцев нет, но есть два состояния: условно «ток идет» и «ток не идет», нулик и единичка. Соответственно все числа (да и вообще информация) в памяти компьютера состоят только из двух цифр — 0 и 1. Их расположение, как и в случае десятичной системы счисления, указывает на разряд. Только теперь число можно разложить на сумму цифр, помноженных не на степени десятки, а степени двойки.

0 в двоичной системе = 0
1 в двоичной системе = 1
2 в двоичной системе = 10
710=1112

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

Пример:

Давайте найдем десятичный аналог двоичного числа 1011012
Самая правая единичка = 1*20
Следующий нулик = 0*21
Третья справа единичка = 1*22
Четвертая = 1*23
… и так далее

1011012 = 1*20 + 0*21 + 1*22 + 1*23 + 0*24 + 1*25 = 1 + 0 + 4 + 8 + 0 + 32 = 4510

Представьте восемь лампочек, выставленных в ряд. У каждой из них — свой собственный выключатель.

Каждая из лампочек — это разряд. Да что представлять, вспомните самую первую лекцию (там есть такой агрегат) или вот вам виджет: cdn.cs50.net/2016/x/psets/0/pset0/bulbs.html

Поиграйтесь с ним, потренируйтесь «прочувствовать» двоичную систему.
Перевод из десятичной системы в двоичную.

Тут тоже всё очень просто, если понимать суть. вот есть у нас число 5710. Чтобы перевести его в двоичную систему, нужно определить, какая максимальная степень двойки не превосходит это число. 26 = 64. Это явно многовато. А вот 25 = 32. Вот мы определили старший разряд. 3210 = 1000002. Теперь ищем следующий разряд. 57-32 = 25. Теперь для 25 ищем степень двойки, которая не превосходит 25. 24 = 16. Значит, следующий разряд у нас тоже равен 1. 32+16 = 4810 = 1100002. 57 – 48 = 9. 23 = 8, это больше, чем 9. Значит следующий разряд тоже будет единичкой.

32 + 16 + 8 = 5610 = 1110002.
57-56 = 1, то есть осталась только одна степень 20.

Таким образом 5710 = 1110012.

Если вдруг что осталось непонятым, можно подробнее почитать в викиучебнике, а если сильны в английском — вот маленькое дополнение к лекции.

ASCII

ASCII
Компьютер понимает только нулики и единички, а его память можно представить в виде ооочень длинной строки из лампочек с выключателями, как вы видели выше. Как представить цифры в компьютере мы уже поняли. А что с остальной информацией? Буквами, картинками? Скажем, в английском алфавите 26 букв. То есть теоретически мы можем представить буквы цифрами от 0 до 25, только в двоичной системе. Возникает следующий вопрос: а как понять, перед нами строчная буква или прописная? А знаки препинания? Знаки-«невидимки» вроде пробела? Словом, нужна система кодирования, Кэп! В 1960 годах существовало множество разных схем, кодирующих символы. Отсутствие единообразия оказалось проблемой, и в 1963 году Американский институт стандартизации ANSI разработал и ввел в обиход схему кодировки ASCII (American Standard Code for Information Interchange).

Каждый символ ASCII состоит из семи разрядов или семи бит, каждый из которых может принимать значение 0 или 1. В 7 бит можно поместить числа от 0 до 127 в двоичной системе, то есть у нас есть 128 чисел для кодирования символов. Казалось бы, достаточно для кодировки письменной английской речи?

Давайте посчитаем:

a-z — 26 вариантов
A-Z — еще 26
0-9 — 10
,;:~& и прочие знаки пунктуации — 32
И еще один пробел.
Итого — 95 символов.

Оставшиеся 33 вакантных варианта используют для так называемых управляющих символов, вроде перевода строки или возврата каретки.
ru.wikipedia.org/wiki/ASCII#/media/File:ASCII_Code_Chart.svg

Важно различать символы 0-9 и числовые значения 0-9. Символы 0-9 представлены значениями ASCII 48-57. Интересно отметить, что крайние правые четыре бита этих значений ASCII представляют собой двоичные представления числовых значений 0-9. Это несколько упрощает способ преобразования между значениями ASCII и их фактическими числовыми значениями.
Начинаем программировать?

Scratch

Scratch
Итак, Scratch. Об этом визуальном языке программирования и его основных командах вам рассказали в лекции.

Чтобы опробовать Scratch самостоятельно, переходим по ссылке scratch.mit.edu/ и нажимаем «Присоединиться». После регистрации вы можете начинать программировать онлайн. Да, кстати, на сегодняшний день Scratch отчасти русифицирован. Справка, правда, пока на английском.
При желании можно поиграть, а также посмотреть код студенческих проектов, которые демонстрировались в лекции. Вот Pikachu Pastry Catch: scratch.mit.edu/projects/26329354/

Или проект с сортировкой мусора по разным емкостям: scratch.mit.edu/projects/71161586/

Дэвид и компания просят вас не волноваться, если вам кажется, что вы не можете сделать столь сложные проекты: такой уровень уже требует определенной сноровки.

Задание

1. Чтобы лучше понять процессы, происходящие в Scratch, можно загрузить исходный код нескольких проектов отсюда: scratch.mit.edu/explore/projects/all/. Поиграйтесь, посмотрите. Изучать чужой код — это очень полезно. Это один из лучших способов узнать, что внутри у тех программ, до которых вы сами ещё не доросли. Когда вы начнете понимать, как работают эти приложения, можно смело идти дальше.

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

Требования к проекту:

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

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

Если что-то не получается, возможно, следует изменить подход к решению задачи. Главное, без страха — в путь!

Предлагаем вам задавать вопросы, а также делиться своими проектами в комментариях.

Scratch: краткое руководство к действию
Спрайт — центральный объект проекта. Любой персонаж — кот, самолет, мячик — является спрайтом. Если вы добавили двух разных котов — это два разных спрайта.

Scratch CS50
У каждого спрайта есть скрипты, которые описывают его поведение. Это блоки действий.
Костюмы — это то, как выглядят объекты. Сами спрайты, по сути — это просто рисунки. Каждый спрайт может иметь несколько костюмов.

Чтобы создать спрайт, нужно либо выбрать его изначальный костюм из библиотеки Scratch, нарисовать свой собственный во встроенном редакторе, загрузить любое изображение или даже сделать фотку с помощью веб-камеры и загрузить её.

Все спрайты помещаются на так называемую сцену (stage). Сцена — по сути, наш холст, место действия программы.

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

scratch green flag
И присоединить к нему, как к детали конструктора, какие-то блоки. Например:

Scratch блоки
В таком случае при нажатии на флажок, спрайт, к которому привязаны действия, делает 50 шагов и мяукает.
Блоков у нас очень много. Они разделены на три вкладки: скрипты, костюмы и звуки. Давайте сделаем простенькую программу с условием. Если оно выполнится, кот мяукнет, не выполнится — останется молчаливым. Операторы обозначены зеленым цветом. Те из них, которые проверяют на истинность или ложность условия, отличаются острыми углами по бокам. Структуры проверки условий и циклы обозначены оранжевым. В них есть специальные отверстия, куда можно помещать другие блоки.

Циклы:

Повторить бесконечное количество раз
Scratch: повторить бесконечное количество раз
Повторить что-то определенное количество раз.
repeat
Повторить действие, если условие выполняется.
Scratch repeat until
Создавать переменные можно в блоке Data. Ниже в примере мы создали переменную x, и сразу появились действия, которые можно с ней проделать. Вы можете задать область видимости переменных: для всех спрайтов или для одного.

Scratch блок Data
Зеленый флажок — не единственное действие. Также в разделе Events вы можете обнаружить еще ряд управляющих условий. Например, вы можете выбрать, что делать по нажатию на кнопку или на сам спрайт мышкой.

Если понадобится дополнительная информация, можно её найти, например, здесь: younglinux.info/scratch/introduction

Что еще

Если ваш доступ к интернету оставляет желать лучшего, рекомендуем загрузить офлайновый редактор Scratch по адресу scratch.mit.edu/scratch2download/. Потом не забудьте переслать ваш проект в scratch.mit.edu/ с помощью меню Файл > Загрузить с компьютера.

7 комментариев

luch
Отредактируйте статью.
EvIv
Бендер в личке мне ответил, что отредактирует. Ждём =)
ONYX
не понятна эта запись 1011012 = 1*20 + 0*21 + 1*22 + 1*23 + 0*24 + 1*25 = 1 + 0 + 4 + 8 + 0 + 32 = 4510
а именно откуда взялись эти числа 1 + 0 + 4 + 8 + 0 + 32???
EvIv
Именно поэтому и ждем, когда статью отредактируют.
В оригинале там последние «2» и «10» в этих числах — нижние индексы, как в химических формулах. Здесь они означают систему счисления, в которой представлено число. В других случаях это верхние индексы — показатели степени, в которую нужно возвести основание системы счисления.
То есть конкретно здесь следует читать 101101(маленькая 2) = 1*2^0 + 0*2^1 + 1*2^2 + 1*2^3 + 0*2^4 + 1*2^5 = 1 + 0 + 4 + 8 + 0 + 32 = 45(маленькая 10)
EvIv
  • EvIv
  • 0
  • Комментарий отредактирован 2016-07-04 17:07:21 пользователем EvIv
1011012 = 1*20 + 0*21 + 1*22 + 1*23 + 0*24 + 1*25 = 1 + 0 + 4 + 8 + 0 + 32 = 4510
Bender
Спасибо за внимательность! Вроде все поправили.
nolich
"= 8, это больше, чем 9"
Поправьте, пожалуйста.
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.