Основы программирования: Гарвардский курс CS50

платформа образовательных курсов

 

Признанный одним из лучших в мире, CS50 — курс, разработанный преподавателями Гарвардского университета. Он посвящён основам программирования и основам информационных технологий. CS50 рассчитан на абсолютных новичков или тех, кто имеет начальные знания по программированию. Однако даже опытный «айтишник» может найти в «Гарвард CS50 основы программирования» много интересного. Курс подойдёт и заинтересованным школьникам лет 12-14, и студентам (даже «не-технарям»), и «перебежчикам» из других профессий, которое хотят изучать основы программирования с нуля.

Кому подойдет курс

Начинающим

Чему вы обучаетесь на курсе

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

Концепции алгоритмов, алгоритмичность мышления.  

Концепции абстракции, структуры данных, инкапсуляции, управления памятью. Основы компьютерной безопасности. Процесс разработки ПО и веб-разработка.

Основы программирования для начинающих на языке Cи и визуальном языке Scratch. Большинство примеров и заданий студенты создают на языке Cи.

Основы баз данных и SQL.

Веб-разработка: основы CSS, HTML, JavaScript и PHP.

Основы подготовки презентации проектов по программированию.

Программа курса

Модуль 1: Системы счисления. Алгоритмы. Визуальный язык Scratch и программы на нём.
Урок 1: Вступительная

 

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

 

00:00 Вступление. Это CS50. Что будем изучать на этой неделе.


06:45 Бинарная система счисления. Как она связана с десятичной, почему именно она применяется в компьютерах и причём здесь транзисторы.


16:25 Алгоритмы.

  • Что такое алгоритм?
  • Как быстро найти человека в телефонном справочнике?
  • Эффективность алгоритмов.
  • Псевдокод.

29:53 Как построено обучение на CS50.

Модуль 2: Основные команды Linux. Язык Си, его синтаксис. Первая программа

В наших широтах мы такого не встречали, а в США, похоже, распространён игрушечный кассовый аппарат, изображенный на фото выше. Цилиндры предназначены для хранения монет разного диаметра (и номиналов). Выдает их пружинный механизм, а сам агрегат можно закрепить на поясе ребёнка-кассира. 

Однако что будет, если кто-то рассчитается с кассиром крупной купюрой? Представьте, сколько мороки будет с тем, чтобы посчитать монетки на сдачу. Для минимизации количества выдаваемых монет можно использовать так называемые «жадные» алгоритмы. Они, согласно определению Национального Института Стандартов и Технологии (NIST) всегда находят оптимальное решение на каждом шаге решения задачи, допуская, что конечное решение (полученное из совокупности таких шагов) также будет оптимальным. 

Что это значит? Представим, что кассир должен покупателю сдачу в 41 цент, а у него на поясе есть цилиндры с монетками для сдачи номиналом в 25, 10, 5 и 1 цент. Руководствующийся «жадным» алгоритмом кассир сразу же захочет выдать максимум, на первом же шаге. На этом шаге оптимальным или наилучшим решением будет выдать 25 пенсов. 41-25 = 16. Осталось выдать 16 пенсов. Очевидно, 25 пенсов слишком много, значит, остается 10. 16-10 = 6. Теперь выдаем по тому же принципу 5 пенсов, и затем — 1. Таким образом, покупатель получит всего четыре монеты номиналом 25, 10, 5 и 1 пенс. 

Оказывается, «жадная» пошаговая инструкция выдачи денег оптимальна не только для этого случая, но также для номиналов валюты США (и Евросоюза тоже). То есть, если у кассира достаточно монет любого номинала, алгоритм будет работать лучшим образом, то есть, выдаст минимальное количество монет из всех возможных случаев. 

Итак, какое минимальное количество монеток нам нужно, чтобы дать сдачу? Это и есть наша третья задачка.

Создайте файл greedy.c в своей директории ~/workspace/pset1

Дано: монетки номиналом 25, 10, 5, 1 цент 

Программа должна:

  1. Спросить пользователя, сколько сдачи нужно выдать.
  2. Посчитать минимальное количество монет, с помощью которых можно это сделать

Примечание: для ввода будем пользоваться функцией GetFloat из библиотеки CS50 и printf из стандартной библиотеки ввода/вывода для вывода. Кроме того, программа должна проверять корректность ввода. 

Мы попросили вас использовать GetFloat, чтобы пользователь мог вводить значение в долларах и центах через точку. Например, если мы должны $9.75, пользователь должен ввести 9.75, но не $9.75 или 975. 

Вы должны проследить, чтобы пользователь ввел число, которое имеет смысл. Скажем, неотрицательное, в этом функция GetFloat сама по себе не поможет. Если пользователь сделал неправильный ввод, нужно просить его повторить его, и выполнять программу только с корректными данными. 

Внимание! Остерегайтесь неточностей, свойственных числам с плавающей точкой. Например, 0.01 не может быть представлено непосредственно как float. Попробуйте использовать форматированный вывод, например, с 50 знаками после запятой, используя указанный ниже код: 

float f = 0.01;
printf("%.50f\n", f);

Кстати, перед тем, как что-либо считать, будет логично перевести всю сумму в центы, (и заодно преобразовать её из float в int), что поможет избежать массы ошибок и сложностей. 

Чтобы наш автоматический анализатор кода мог правильно проверить вашу задачу, убедитесь, что последняя строка вывода вашей программы не содержит никакой другой информации, кроме минимального количества монеток: целое число с символом \n после него (те, кто учится на JavaRush, прекрасно знают, о чём мы здесь говорим =)). Ниже — пример, как должен выглядеть результат работы вашей программы. 

username:~/workspace/pset1 $ ./greedy
O hai! How much change is owed?
0.41
4

Учитывая особенность чисел с плавающей точкой, можно игнорировать нуль и вводить такое число в форме .41.

Конечно, пользователи, которые захотят проверить программу на возможность ввода некорректных данных по полной, должны увидеть что-то вроде:

username:~/workspace/pset1 $ ./greedy
O hai! How much change is owed?
-0.41
How much change is owed?
-0.41
How much change is owed?
foo
Retry: 0.41
4

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

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

Как компилировать и выполнять программу вы уже знаете. 

Если вы хотите проверить правильность работы вашей программы, с помощью утилиты check50, в терминале введите следующую строку:

check50 2015.fall.pset1.greedy greedy.c

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

~cs50/pset1/greedy
Модуль 3: Что такое криптография? Простые криптографические шифры. Баги. Си: строки и массивы.

Организатор курса

Куратор отвечает за 5 минут
Обучаясь по бесплатным курсам престижных университетов, таких как Гарвардский университет, студенты увеличивают свои шансы на получение стипендий в США, Великобритании или Австралии, а также на успешное трудоустройство после окончания вуза. Гарвардские бесплатные курсы предлагаются в формате онлайн и называются Harvard Online Learning.


0
Продолжить бесплатно