ДС17о01-введение (1238897)

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

Текст из файла

Carnegie MellonВведениеАлгоритмыи алгоритмические языкиgoo.gl/c8pyqxЛекция1,05 сентября,2017Лектор:ДмитрийСеверов,кафедраинформатики608КПМdseverov@mail.mipt.ruhttp://cs.mipt.ru/wp/?page_id=607712Алгоритмыиструктурыданных(1/2)¢¢ЧастьI Теоретическиеосновыинформатики§ Формализацияпонятияалгоритм§ МашинаТьюринга§ Алгорифмы МарковаЧастьII Структурыданных§ ОдиалектахСи§ Составныетипыданных§ Абстрактныетипыданных3Алгоритмыиструктурыданных(2/2)¢¢ЧастьIII Основытеорииалгоритмов§ Анализэффективностиалгоритмов§ РекурсияЧастьIV Основные(базовые)алгоритмы§ Задачисортировки§ Задачипоиска§ Поискнаграфах4Предусловие– умения…алгоритмическимыслитьМожнопроверитьспомощьюhttp://lightbot.comформальноизлагатьрешениезадачиМожнопроверитьспомощьюhttps://drakon-editor.com5Извикипедии (1/2)¢Программи́рование§ процесссозданиякомпьютерныхпрограмм¢Компью́тернаяпрогра́мма1.

комбинациякомпьютерныхинструкцийиданных,позволяющаяаппаратномуобеспечениювычислительнойсистемывыполнятьвычисленияилифункцииуправления(стандартISO/IEC/IEEE24765:2010)[1];2. синтаксическаяединица,котораясоответствуетправиламопределённогоязыкапрограммирования,состоящаяизопределенийиоператоровилиинструкций,необходимыхдляопределённойфункции,задачиилирешенияпроблемы(стандартISO/IEC2382-1:1993)[2].6Извикипедии (2/2)¢Програ́мма (отгреч.προ —пред,греч.γράμμα —запись)термин,впереводеозначающий«предписание»,тоестьпредварительноеописаниепредстоящихсобытийилидействий.Данноепонятиенепосредственносвязаноспонятиемалгоритм.…¢Алгори́тмнаборинструкций,описывающихпорядокдействийисполнителядлядостижениянекоторогорезультата.<…>Независимыеинструкциимогутвыполнятьсявпроизвольномпорядке,параллельно,еслиэтопозволяютиспользуемыеисполнители¢Инструќ цияилиопера́тор(англ.

statement)наименьшаяавтономнаячастьязыкапрограммирования;командаилинаборкоманд.Программаобычнопредставляетсобойпоследовательностьинструкций.7ПонятияпрограммированияПрограммаопределённый наборпредписанийпрограммистДанныенеопределённый наборинформацииПрограммаПроцессожидаемый набор событийДанныеПрограммируемаясистема(исполнитель)ПроцессРесурсыВремя работы¢§§Ресурсы¢¢ПрограммистаСистемыЭнергияПространство8ИзопределенийГОСТ33707 (1/3)¢Программа§ Данные,предназначенныедляуправленияконкретнымикомпонентамисистемыобработкиинформациивцеляхреализацииопределенногоалгоритма.¢Языкпрограммирования§ Искусственныйязыкдляизложениятекстовпрограмм9ИзопределенийГОСТ33707 (2/3)¢Алгоритм§ 2015:Конечноеупорядоченноемножествоточноопределенныхправилдлярешенияконкретнойзадачи§ 1984:Конечныйнаборпредписаний,определяющийрешениезадачипосредствомконечногоколичестваопераций¢Алгоритмическийязык§ Искусственныйязык,предназначенныйдлявыраженияалгоритмов10ИзопределенийГОСТ33707 (3/3)¢Языкспецификаций§ Языкприкладногохарактера,который,1.2.3.4.5.частоявляясьориентированнымнакомпьютерысинтезоместественногоязыкаиискусственногоязыка,используютсядлявыражениятребованийксистемеиликомпоненте,дляописанияихконструкции,аиногдаипротоколовпроверки,дляпроектирования,исследованияидокументированияуказанныххарактеристик.11[Около]компьютерныеявления¢¢¢Модель– упрощённоепредставлениезаконовповедениячастейиотношенийсистемыЯзыкмодели- знаковаяподсистемафиксации,переработкиипередачиинформацииМашина– модельныйисполнитель,которомунаправленыпредписаниянаязыкемоделиРынки¢ Потребители¢ Задачи¢Алгоритмы¢ Программы¢ Система/Аппаратура¢ Цифровыесхемы¢ Аналоговыесхемы¢Физическиеявленияв[не]линейныхструктурах¢12Некоторые[около]компьютерныеязыки¢Задачи¢Языкиспецификаций¢Языкипроектирования¢Алгоритмы¢Алгоритмическиеязыки¢Программы¢Языкипрограммирования¢Архитектура«системы»¢Языкиобращенийк«системе»¢Архитектурааппаратуры¢Языкикомандаппаратуры¢Блокиархитектуры¢Языкимикрокоманд¢Цифровыесхемы¢Языкицифровыхсхем¢Аналоговыесхемы¢Языкианалоговыхсхем¢Языкифизическихмоделей¢Физическиеявленияв[не]линейныхструктурах13АлгоритминтуитивноПоискНОД(a,b),гдеa,b >0,a<b§ Перебор:1– подходит,2- ?,3- ,…а-?§ АлгоритмЭвклида1.

Разделитьпервоенавтороеиполучитьостаток2. Еслиостатокравеннулю,товторое–результат3. Иначе:заменитьпервоенавторое,второе– наостатокиперейтикшагу114СвойстваалгоритмаДискретность данныхидействийнаднимиПонятность: доступностьиоднозначностьправилКонечность: решение задачи законечноечислошаговОпределённость: воспроизводимость результатаМассовость:применимостькразличнымданным15Алгоритмформально:отступлениекфункцииИсходныеданныеРезультаты16Алгоритмформально:отступлениекмножествам(1/2)1.

Элементмножестваа2. МножествоА3. Элементпринадлежитмножеству аÎ А4. НепринадлежитаÏА5. А={a,b,c}6. Æ7. Подмножество AÌBÛ " aÎ A:aÎ B8. A=B Û AÌ Bи BÌ A17Алгоритмформально:отступлениекмножествам(1/2)9. ОбъединениеАÈВ10.ПересечениеAÇB={aÎA:aÎB}11.РазностьA\ B={aÎA:aÏB}12.Декартово(прямое)произведение Aх BА={0,1},B={a,b,c}, AxB={0a,0b,0c,1a,1b,1c}A1 xA2 xA3 x…xAnA0=Æ,A1=A,A2=A x A,An =AxAxAx…xAn18Алгоритмформально:функцияформально¢МножествоFестьфункцияизмножестваАвB тогдаитолькотогда, когдаверноследующее.1.

FÍ AxB,2. если…1. aÎA,2. b,cÎB3. abÎF,4. acÎF,… тоb=c.10,1515,256,914,2119Алгоритмформально:итог§A={a1,a2,…,ap} - алфавит§A* = A0 È A1 È A2 È …È An –множествовсехслов,состоящихнеболеечемизn символов.§F:A*® A*20АланТьюрингЭмиль ПостНорбертВинерАлонзоЧёрчАндрейМарков21ПрограммаРеализацияалгоритманаязыкепрограммирования,определяющем…§ Действия: операциииоператоры§ Данные: типыиэкземпляры§ Организация: конструкции сложных данныхидействий§ Окружение: взаимодействие со средой22Масштабысобытийвашейпрограммы¢ВашисполнительЯдропроцессораПамятьУBBУBBУBBУBBКрупнее:§ Средаразработк觧§§СоединительРедактированиеТрансляцияСвязывание…§ СредаисполненияЗагрузка§Выделениересурсов§Нормированиеработыиреагированиеназапросы§Освобождениересурсов§…Мельче– зарамкамисеместра§¢Вашпроцесс§§¢ВыполнениеоперацийИзменениесостоянияДругиепроцессы23СозданиепрограммыРедактирование⇓ ТекстпрограммыТрансляция⇓ ОбъектныйкодКомпоновка⇓ ЗагрузочныйкодЗагрузка⇓ ИсполняемыйкодВыполнение, отладка⇓ Результат24СозданиепрограммывместеРедактирование⇓ Текстпрограммы⇐ ВашиизменениявручнуюТрансляция⇓ Объектныйкод⇐ БиблиотечныйисходныйтекстКомпоновка⇓ Загрузочныйкод⇐ БиблиотечныймашинныйкодЗагрузка⇓ Исполняемыйкод⇐ РешениясредыисполненияВыполнение, отладка⇓ Результат⇐ Внешниеданные,коды,события25СозданиепрограммывокруженииРедактированиеG Предписанияредактору⇓ Текстпрограммы⇐ ВашиизменениявручнуюТрансляцияE Предписаниятрансляции⇓ Объектныйкод⇐ БиблиотечныйисходныйтекстКомпоновкаE Предписаниякомпоновки⇓ Загрузочныйкод⇐ БиблиотечныймашинныйкодЗагрузкаE Предписаниязагрузки⇓ Исполняемыйкод⇐ РешениясредыисполненияВыполнение, отладка E Предписанияисполнения⇓ Результат⇐ Внешниеданные,коды,события26Carnegie Mellon(Само)обман¢Чтоесть(само)обман?§§§§§¢Братьчужойкод:копируя,перенабирая,подглядывая,принимаяфайлыПересказывать:устноеописаниекодаоднимчеловекомдругомуНатаскивание:помощьдругувпострочномнаписаниизаданийПоискрешениявсетиКопированиекодапредыдущихкусовиэкзаменовЧтоНЕесть(само)обман?§ Объяснятькакиспользоватьинструментыилисистемы§ Помогатьдругимввопросахконструкцииверхнегоуровня27.

Характеристики

Тип файла PDF

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

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

Список файлов лекций