Оберон-технология: особенности и перспективы |
Тематика обсуждения: Оберон-технология. Особенности, перспективы, практическое применение.
Всего в теме 6256 сообщений
Добавить свое сообщение
Отслеживать это обсуждение Обсуждение из раздела Школа ОБЕРОНА
№ 3266 17-03-2007 13:47 | |
Какое решение понятнее проще - судить сторонним наблюдателям.
На мой взгляд, решение на Хацкеле без поллитра не прочитать :-)
А теперь важные моменты.
Изюминка задачки в том, что пространство решений небольшое, и все их можно заранее просчитать и занести в таблицу, а при считывании входных данных из файла просто сразу выводить ответы. Иначе для больших входных наборов можно просто пролететь по времени.
И вот - внимание - мне очень-очень интересно, как из такой ситуации будут выкручиваться хацкелисты... Состояний нет, запомнить заранее ответы нельзя, разве что написать программу-генератор константной таблицы, которую потом засунуть в исходник? Или придется функциональщикам применять closures - без состояний никуда :-)
А ведь есть еще задачи на динамическое программирование. Они по структуре своей рекурсивны, вот бы где ФП развернуться, но увы - опять нужно запоминать промежуточные результаты в каких-либо переменных. Опять closures? :-)
№ 3265 17-03-2007 13:39 | |
№ 3264 17-03-2007 13:30 | |
Ответ на »сообщение 3258« (Geniepro)
___________________________
Ответ на »сообщение 3255« (Руслан Богатырев)
___________________________
Ну вот, я так и знал! :о))
Ну что ж, нужно привлекать добровольцев, или даже назначать их... :о)
Вот и решение на Компонентном Паскале подоспело :-)
Для ввода-вывода/создания экзешника использовал олимпиадную подсистему Info21olimp от Информатики-21.
MODULE OlimpBlood;
IMPORT In := Info21olimpIn, Out := Info21olimpOut, Strings;
CONST
aA = 0; aB = 1; aO = 2;
gA = 0; gAB = 1; gB = 2; gO = 3;
rP = 4; rM = 5;
TYPE
CorrelateMap = ARRAY 4, 4 OF SET;
VAR
directMap: CorrelateMap;
inverseMap: CorrelateMap;
strMap: ARRAY ORD()+1 OF ARRAY 128 OF CHAR;
PROCEDURE Alleles (group: INTEGER): SET;
BEGIN
CASE group OF gA: RETURN | gAB: RETURN
| gB: RETURN | gO: RETURN
END
END Alleles;
PROCEDURE GroupAbilities (alleles1, alleles2: SET): SET;
VAR g: INTEGER;
res: SET;
BEGIN
res := ;
FOR g := gA TO gO DO
CASE g OF
| gA: IF (aA IN alleles1 * alleles2) OR
(aA IN alleles1) & (aO IN alleles2) OR
(aO IN alleles1) & (aA IN alleles2) THEN
INCL(res, gA)
END
| gAB: IF (aA IN alleles1) & (aB IN alleles2) OR
(aB IN alleles1) & (aA IN alleles2) THEN
INCL(res, gAB)
END
| gB: IF (aB IN alleles1 * alleles2) OR
(aB IN alleles1) & (aO IN alleles2) OR
(aO IN alleles1) & (aB IN alleles2) THEN
INCL(res, gB)
END
| gO: IF (aO IN alleles1 * alleles2) THEN
INCL(res, gO)
END
END
END;
RETURN res
END GroupAbilities;
PROCEDURE InitDirectMap;
VAR g1, g2: INTEGER;
BEGIN
FOR g1 := gA TO gO DO
FOR g2 := gA TO gO DO
directMap[g1, g2] := GroupAbilities(Alleles(g1), Alleles(g2))
END
END
END InitDirectMap;
PROCEDURE InitInverseMap;
VAR g1, gx: INTEGER;
PROCEDURE FillCell;
VAR g2: INTEGER;
BEGIN
FOR g2 := gA TO gO DO
IF gx IN directMap[g1, g2] THEN
INCL(inverseMap[g1, gx], g2)
END
END
END FillCell;
BEGIN
FOR g1 := gA TO gO DO
FOR gx := gA TO gO DO
FillCell
END
END
END InitInverseMap;
PROCEDURE ResusAbilities (r1, r2: INTEGER): SET;
BEGIN
IF (r1 = rM) & (r2 = rM) THEN RETURN
ELSE RETURN
END
END ResusAbilities;
PROCEDURE ResusInverseAbilities (r1, rx: INTEGER): SET;
BEGIN
IF (rx = rP) & (r1 = rM) THEN RETURN
ELSE RETURN
END
END ResusInverseAbilities;
PROCEDURE SolveDirect (g1, r1, g2, r2: INTEGER): SET;
BEGIN
RETURN directMap[g1, g2] + ResusAbilities(r1, r2)
END SolveDirect;
PROCEDURE SolveInverse (g1, r1, gx, rx: INTEGER): SET;
BEGIN
RETURN inverseMap[g1, gx] + ResusInverseAbilities(r1, rx)
END SolveInverse;
PROCEDURE ExtractCase (IN s: ARRAY OF CHAR; OUT groups, resuses: ARRAY OF INTEGER);
VAR i, j: INTEGER;
PROCEDURE ReadElem;
BEGIN
CASE s[i] OF
| '?': groups[j] := -1
| 'A': IF s[i+1] = 'B' THEN groups[j] := gAB; INC(i, 2) ELSE groups[j] := gA; INC(i) END
| 'B': groups[j] := gB; INC(i)
| 'O': groups[j] := gO; INC(i)
END;
CASE s[i] OF
| '?': resuses[j] := -1
| '+': resuses[j] := rP
| '-': resuses[j] := rM
END;
INC(i); INC(j)
END ReadElem;
BEGIN
i := 0; j := 0;
WHILE s[i] = " " DO INC(i) END; ASSERT(s[i] # 0X, 20); ReadElem;
WHILE s[i] = " " DO INC(i) END; ASSERT(s[i] # 0X, 20); ReadElem;
WHILE s[i] = " " DO INC(i) END; ASSERT(s[i] # 0X, 20); ReadElem
END ExtractCase;
PROCEDURE BloodToStr (g, r: INTEGER; OUT str: ARRAY OF CHAR);
BEGIN
CASE g OF gA: str := "A" | gAB: str := "AB" | gB: str := "B" | gO: str := "O" END;
CASE r OF rP: str := str + "+" | rM: str := str + "-" END
END BloodToStr;
PROCEDURE AbilitiesToStrEnd (ab: SET; OUT str: ARRAY OF CHAR);
VAR i0, g, cnt: INTEGER;
s: ARRAY 4 OF CHAR;
BEGIN
i0 := LEN(str$);
cnt := 0;
FOR g := gA TO gO DO
IF g IN ab THEN
IF rP IN ab THEN INC(cnt); BloodToStr(g, rP, s); str := str + ", " + s END;
IF rM IN ab THEN INC(cnt); BloodToStr(g, rM, s); str := str + ", " + s END
END
END;
IF cnt = 0 THEN
str[i0] := 0X; str := str + "IMPOSSIBLE"
ELSIF cnt = 1 THEN
str[i0] := 0X; str := str + s
ELSE
str[i0] := ""
END
END AbilitiesToStrEnd;
PROCEDURE InitStrMap;
VAR a: INTEGER;
BEGIN
FOR a := 0 TO ORD() DO
AbilitiesToStrEnd(BITS(a), strMap[a])
END
END InitStrMap;
PROCEDURE SolveCase (IN istr: ARRAY OF CHAR; OUT ostr: ARRAY OF CHAR);
VAR groups: ARRAY 3 OF INTEGER;
resuses: ARRAY 3 OF INTEGER;
res: SET;
s: ARRAY 4 OF CHAR;
BEGIN
ExtractCase(istr, groups, resuses);
IF (groups[0] # -1) & (groups[1] # -1) THEN
res := SolveDirect(groups[0], resuses[0], groups[1], resuses[1]);
BloodToStr(groups[0], resuses[0], s);
ostr := s$;
BloodToStr(groups[1], resuses[1], s);
ostr := ostr + " " + s + " ";
AbilitiesToStrEnd(res, ostr)
ELSIF groups[0] # -1 THEN
res := SolveInverse(groups[0], resuses[0], groups[2], resuses[2]);
BloodToStr(groups[0], resuses[0], s);
ostr := s$ + " ";
AbilitiesToStrEnd(res, ostr);
BloodToStr(groups[2], resuses[2], s);
ostr := ostr + " " + s
ELSIF groups[1] # -1 THEN
res := SolveInverse(groups[1], resuses[1], groups[2], resuses[2]);
ostr := "";
AbilitiesToStrEnd(res, ostr);
BloodToStr(groups[1], resuses[1], s);
ostr := ostr + " " + s;
BloodToStr(groups[2], resuses[2], s);
ostr := ostr + " " + s
END
END SolveCase;
PROCEDURE Do;
VAR s, outs: ARRAY 256 OF CHAR;
line: INTEGER;
end: BOOLEAN;
PROCEDURE GetLine;
VAR i: INTEGER;
BEGIN
IF ~In.done THEN
end := TRUE
ELSE
INC(line);
i := 0; In.Char(s[0]);
WHILE In.done & (s[i] # 0DX) & (s[i] # "E") DO
INC(i); In.Char(s[i])
END;
IF s[i] = "E" THEN
end := TRUE
END;
s[i] := 0X; IF In.done THEN In.Char(s[i+1]) END
END
END GetLine;
BEGIN
end := FALSE; line := 0;
GetLine;
WHILE ~end DO
Strings.IntToString(line, outs);
outs := "Case " + outs + ":" + " ";
Out.String(outs);
SolveCase(s, outs);
Out.String(outs); Out.Ln;
GetLine
END
END Do;
PROCEDURE Main* ;
BEGIN
In.Open('blood.in'); Out.Open('blood.out'); Do
END Main;
PROCEDURE Test* ;
BEGIN
In.Open("blood.in"); Out.Open(""); Do
END Test;
BEGIN
InitDirectMap;
InitInverseMap;
InitStrMap
END OlimpBlood.
№ 3263 17-03-2007 13:30 | |
Ответ на »сообщение 3262« (Eugene)
___________________________
Значительная часть задач просто этого не требует - мне вот после окончания ВУЗа не то, что высшая математика ни разу не потребовалась, но и из алгоритмов сложнее QuickSort/двоичного поиска ничего не применял.
А Вы никогда не задавались вопросом, почему не применяли? Попробуйте...
Наукоемкость индустрии ПО в современном мире крайне низкая. Почему? Искусственно подогревается спрос на системы определенного класса, которые позволяют зарабатывать деньги в кратчайший срок и с минимумом мозговых затрат. В основном это информационные системы с примитивнейшими средствами анализа/синтеза. Наукоемкость сейчас требуется только в прорывных вещах, в заманчивых стартапах, на которых также варятся деньги. Она придет и корпоративный сектор (уже приходит), но только после периода начального окучивания, когда сформируется базис информационной инфраструктуры. А дальше -- надо же как-то бороться с конкурентами, а не просто соорганизовывать свою работу. А здесь без наукоемкости тяжеловато будет.
Корпоративный сектор -- основной поставщик финансовых потоков в индустрию ПО, давно смекнул, что тот же коробочный софт -- утопичный путь. Он работает только для массового рынка (а сейчас со скрипом). А на корпоративном нужен заказной и полузаказной софт, а также слой сервиса, который дает основу другим бизнес-моделям и защищает инвестиции от пиратства. Сейчас нередко программные системы отдают за так: стоит только информационное сопровождение. Это надежнее, если важна именно критическая информация, изменяемая во времени и требующая больших людских ресурсов на актуализацию. Пример для России -- справочно-правовые системы.
Далее инициируется потребность тех, кто может и готов платить (надо только их запугать/убедить). Так появился небезызвестный офшорный аутсорсинг, куда и стекаются сейчас основные финансы и где Индия впереди планеты всей. Ситуацию 6-летней давности по России можно понять, напр., по той статье, которую писал для "Открытых систем", собрав круглый стол руководителей лидеров экспортной заказной разработки ПО: http://www.osp.ru/os/2001/07-08/180316/ и http://www.osp.ru/os/2001/07-08/180332/
В России промышленное производство ПО концентрируются либо в компаниях-офшорниках, либо в "системных интеграторах", окучивающих местных крупных заказчиков. В остальном это кустарное производство (если классифицировать характер с точки зрения производства). В нем ценится: UI, информационный слой (БД), простейшая интеграция с учетом сетевой работы. Да и офшорники раньше большей частью "красили заборы" у западных гигантов, пока не заработали авторитет и их не стали допускать до нутра бизнес-процессов и критических вещей, подлежащих автоматизации. Но калибр отечественных компаний хилый: -- 500-1000 человек. Процесс их слияния слабенький. Это не позволяет браться за масштабные проекты (притом что команды по 20-30 человек на годы подвисают на обслуживании "постоянников"), а потому затрудняет темпы роста.
Что печально, именно такой крен в индустрии ПО содействует катастрофической ситуации с подготовкой кадров в высшей школе, о которой говорил Вирт в "Потерянной дороге" -- http://www.inr.ac.ru/~info21/texts/2002-06-Aarhus/ru.htm
Рынку нужны архитекторы или плиточники-облицовщики. Так-то.
№ 3262 17-03-2007 12:59 | |
Ответ на »сообщение 3240« (Руслан Богатырев)
___________________________
Доброго времени суток!
Небольшой offtopic
Тот же Митричев блестяще умеет справляться с решением алгоритмических задач. А в условиях жесткого прессинга по времени умеет это, пожалуй, лучше всех в мире. Что неоднократно уже доказывал. Это феномен, уникум, выросший на традициях советской математической школы. Вот, что надобно продвигать в народные массы, тем более для страны, которая хочет превратиться из экспортера полезных ископаемых в центр интеллектуального производства.
Рад за Петра. Но как представитель "народных масс" (рядовой программист) что-то
сомневаюсь в пользе продвижения традиций советской математической школы в эти самые массы.
Значительная часть задач просто этого не требует - мне вот после окончания ВУЗа
не то, что высшая математика ни разу не потребовалась, но и из алгоритмов сложнее
QuickSort/двоичного поиска ничего не применял.
Наши ведущие ИТ-СМИ пока поглощены другими важными событиями: Sony подключает владельцев PlayStation 3 к сети Folding@Home, Интернет-магнат попал за решетку...
И эта страна хочет превратиться в центр интеллектуального производства?
С уважением,
№ 3261 17-03-2007 12:57 | |
Насчет морального "устаревания Паскаля".
Вспоминаю переписку с одним из членов технического комитета ACM ICPC от нашей страны. Паскалиста по образованию. Когда речь зашла об аргументации, то я упоминал рейтинг TIOBE, единственный известный мне постоянно ведущийся рейтинг популярности языков, методика которого более-менее понятна и позволяет проверять результаты независимо. По популярности уже были дебаты в "Мыслях об Обероне". Но, думаю, для тех, кто следит за нынешним обсуждением, эта информация не будет излишней.
Просто регулярно можно слышать, что Паскали давно списали в утиль. А как эту чушь опровергнуть? Это один из объективных инструментов анализа, позволяющий ежемесячно отслеживать тенденции популярности.
Вот рейтинг TIOBE на март: http://www.tiobe.com/tiobe_index/index.htm
Из Паскалей в 20-ке лучших фигурирует Delphi. Он хоть и продолжает падать, но все еще на 12-м месте, не так уж сильно отставая от C#. Если интересуют функциональные языки, то их доля составляет по TIOBE 0.8% с годовым приростом 0.2. По остальным см. таблицу:
Category Mar 2007 Delta Mar 2006
Object-Oriented Languages 52.3% +0.9%
Procedural Languages 45.3% -1.8%
Logical Languages 1.7% +0.8%
Functional Languages 0.8% +0.2%
В сфере мониторинга 100 языков.
№ 3260 17-03-2007 12:17 | |
Ответ на »сообщение 3258« (Geniepro)
___________________________
Кстати, идеологи XP (экстремального программирования) как-раз рекомендуют схему "один компьютер на две головы". Утверждается, что при этом гораздо быстрее отлавливаются ошибки при кодировании, да и вообще повышается производительность труда по сравнению с "двумя компьютерами на двух человек".
Ну а третий изучает следующую задачу...
Идеологи XP? :)
По-моему, я уже как-то рассказывал, что когда в МАИ мы работали с Кроносом (советский 32-разрядный Lilith, точнее, с его в вариантом виде платы для Электроники-60), раздобытым с большим трудом, то поневоле вынуждены были использовать единственный компьютер. На дворе был, если не ошибаюсь, 1988 г. Нас в команде тогда было трое, при этом один "рулил" (писал код, не вдаваясь в детали), другой был штурманом (сидел за плечом, излагал тактический замысел), а третий отдыхал (смотрел за двумя другими, иногда что-то уточняя). Через 30-40 минут происходила смена пилота (как в командных велосипедных гонках), на его место садился штурман, а наблюдатель становился штурманом. И так по кругу. Но это для обычного режима. Когда что-то делалось особо ответственное, то смены происходили исходя из усталости (замыленности глаза) и с учетом того, у кого что лучше получается. Главным забойщиком был Игорь Егоров, главный программист в известном проекте игрового симулятора "Ил-2 Штурмовик".
№ 3259 17-03-2007 12:03 | |
Ответ на »сообщение 3258« (Geniepro)
___________________________
--Паскаль, на котором наши преимущественно писали, исключили из "элиты" по причине "моральной старости".
-- Логично было бы тогда исключить и Си - он ведь ровесник Паскаля.
Тут проблемы глубже. Кто генеральный спонсор? IBM. Какую цель ставит IBM помимо продвижения своей марки в среде подрастающей интеллектуальной элиты? Самую прагматичную -- отбор кадров: как признавались участники, регулярно в ходе финалов бывают встречи с представителями IBM, headhunter'ы работают на полную катушку.
Далее. На каждом компьютере ставится унифицированная операционная среда, которая включает в себя ОС и системы программирования "высочайше разрешенных" языков. Раз IBM, значит, никак не Windows. А что? (напоминает известный анекдот: Кто у меня родился? Мальчик? Нет? А кто?). Итак, это Linux. Для Linux из Паскалей использовался вариант Kylix, который давно фирмой Borland позабыт-позаброшен. Наши его как-то там подмазывали под новые версии Red Hat Linux, но проблемы постоянно всплывают. Формально именно это является поводом к исключению, а реально -- самому техническому комитету писать решения задач и проверять то, в чем они "не-копенгаген", как-то не хочется. Да и сами спонсоры никаких, разумеется, возражений не имеют. Им-то Паскаль Борланда на что сдался? Другое дело Eclipse, в котором сидят C/C++ и Java. Плюс что-то там Россия обнаглела совсем, медали гребет лопатой, надо и с другими поделиться, а то чемпионаты будут дискредитированы (как в свое время советская шахматная школа задавила всех). А эти русские и в Java с C++ разберутся.
Кстати, тот же КП есть в реализации для Eclipse. Но это еще нужно пробивать (причем и черех наши команды, и через функционеров и через членов технического комитета, подсобрав при этом хотя бы союзников из других стран -- что о-о-чень проблематично). В конце 2005 г. питерцы из звездных команд СПбГУ ИТМО крутили-вертели BlackBox, он им понравился. Но что толку -- пробивать-то это надо через технический комитет, а там BlackBox не пройдет (нужен под Linux, да в идеале под Eclipse). А это только GPCP/Eclipse австралийцев -- http://www.plas.fit.qut.edu.au/gpcp/IDE.aspx
P.S. Вообще-то, подробный "разбор полетов" по чемпионату 2005 г. я уже проводил: http://www.osp.ru/pcworld/2005/05/170171/
Полная версия есть на europrog.ru: http://www.europrog.ru/paper/acm2005.pdf
№ 3258 17-03-2007 11:29 | |
Ответ на »сообщение 3255« (Руслан Богатырев)
___________________________
Пусть будут Oberon/КП и Haskell.
Кстати, а почему еще и Delphi к этому не подключить, раз мы в Королевстве это обсуждаем и тут немало спецов по этому языку?
Согласен с Вами.
Кстати, конкретно ту задачку "Problem A+. Consanguine Calculations", как мне кажется, идеально было бы решать на Прологе. Хотя на Хаскелле с его list comprehensions решилось тоже довольно просто.
Паскаль, на котором наши преимущественно писали, исключили из "элиты" по причине "моральной старости".
Логично было бы тогда исключить и Си - он ведь ровесник Паскаля.
Если вернуться к самому спортивному регламенту, то лично для меня очевидно, что если есть пять часов на размышление, три участника в команде и всего один компьютер в их распоряжении, то нужна соответствующая схема коллективной разработки в этом "экстремальном программировании".
Кстати, идеологи XP (экстремального программирования) как-раз рекомендуют схему "один компьютер на две головы". Утверждается, что при этом гораздо быстрее отлавливаются ошибки при кодировании, да и вообще повышается производительность труда по сравнению с "двумя компьютерами на двух человек".
Ну а третий изучает следующую задачу...
Сожалею, но, заварив кашу, я, как обычно, "умываю руки".
Ну вот, я так и знал! :о))
Ну что ж, нужно привлекать добровольцев, или даже назначать их... :о)
№ 3257 17-03-2007 10:38 | |
Ответ на »сообщение 3256« (Руслан Богатырев)
___________________________
Заморожено оно после окончания 4-го часа (т.е. примерно в районе 4*60-240-й минуты).
Сорри, надо читать: 4*60 =240-й минуты.
Добавить свое сообщение
Отслеживать это обсуждение
Дополнительная навигация: |
|